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. |