Google Answers Logo
View Question
 
Q: Progr. Problem: arrange N groups of N colored stones with no duplicates in a row ( No Answer,   0 Comments )
Question  
Subject: Progr. Problem: arrange N groups of N colored stones with no duplicates in a row
Category: Computers > Algorithms
Asked by: jh963-ga
List Price: $7.50
Posted: 04 Feb 2005 10:36 PST
Expires: 05 Feb 2005 13:42 PST
Question ID: 468815
Here's one for all you math / word problem wizards out there.

(While this might sound like a homework problem, it's actually a
conceptualization of
a problem I'm trying to solve at work.)

Assume that you have N groups of N different colored stones (e.g., 4 groups of 4 
different colors, 8 groups of 8 different colors).  Just to make the
description easier
let's say we have 4 groups of 4 different colors: so we have 4 red, 4
blue, 4 green,
and 4 yellow stones.

Put all the stones into a pile and randomly break that 1 pile into 4
piles of 4 stones
each.  Each pile will now have a random number of red, blue, green,
and yellow stones
in it.  Let each pile be the stones for 1 column.

Your job is to arrange each pile / column of stones into a 4 by 4 matrix so that no
color APPEARS TWICE IN THE SAME ROW.

Here's an example.

Pile 1: R B G G			// All these must appear in column 1
Pile 2: R B B Y			// All these must appear in column 2
Pile 3: G Y Y Y			// All these must appear in column 3
Pile 4: R R B G			// All these must appear in column 4

Here is 1 possible arrangement:

R Y G B
B R Y G
G B Y R
G B Y R

Note that each color only appears ONCE in each row.

What I want is either a program or an algorithm that can be easily turned into a
program that solves this problem in the general case.  The input to
the program will
be N piles of N different colored stones.  The output of the program should be a 
2-dimensional array similar to the answer to the example program.

One other thing: the solution should be efficient.  A brute force
approach on a 4 x 4
arrangement wouldn't take much time, but my real goal is to have an
efficient solution
to the 8 by 8 case.  Brute force on the 8 x 8 case would take too long.  I want the
WORST case on the 8 x 8 case to be under 2 seconds on a modern Windows machine.

J.
Answer  
There is no answer at this time.

Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy