I am working on a programming project part of which involves coloring
a map of SIX (6) countries using FOUR (4) colors. To focus on the
second part of a map coloring problem - finding "legal" colrings (no
adjacent countries can be the same color) - I seek to generate all
possible combinations of 6 countries colored with 4 colors.

I am having trouble creating a specific algorithm to generate ALL
possible combinations of 4 colors applied to the 6 countries. What's
needed is an algorithm that can do this and is assured of generating
ALL possible combinations. The algorithm does NOT need to solve the
map coloring problem it just needs to generate all *potential*
solutions which will then be searched and validated. Pseudo code,
C/C++ or Java code would be perfect.

Many thanks for your help!  -David

---

Clarification of Question by darsenault-ga on 19 Sep 2002 17:49 PDT

Clarification:

Suppose the 6 countries are: A B C D E F
and the 4 colors are: red green blue yellow

The idea is to find all combinations of country-color pairs
(A red) (B green) (C blue) (D red) (E yellow) (F blue) one potential solution
(A green) (B red) (C blue) (D green) (E red) (F blue) 2nd potential solution
(A blue) (B green) (C blue) (D blue) (E yellow) (F red) ...
..... etc.

Hello Darsenault,

There are a few ways to do this. Perhaps the most simple is a set of
nested loops. Something like the following...

  for i1 = 1 .. 4 do
    for i2 = 1 .. 4 do
      for i3 = 1 .. 4 do
        for i4 = 1 .. 4 do
          for i5 = 1 .. 4 do
            for i6 = 1 .. 4 do
              print (i1, i2, i3, i4, i5, i6)
            next i6
          next i5
        next i4
      next i3
    next i2
  next i1

which should print something like
1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 1 3
1 1 1 1 1 4
1 1 1 1 2 1
...
4 4 4 4 3 4
4 4 4 4 4 1
4 4 4 4 4 2
4 4 4 4 4 3
4 4 4 4 4 4
Replace the numbers with color names as appropriate. Put the values
into an array or call a "pass or fail" function to determine if the
combination is a good one or not.

You could do something similar with recursion.
Start with...
  combo ("", 0)
and a function like...
  combo ( prefix, depth ) 
    begin
    for i = 1 .. 4 do
      if (depth = 6) then
        print (prefix & i)
      else
        combo (prefix & i, depth+1)
      end if
    next i
    end

Where & represents some form of concatenation (e.g., string). The
output should be the same as mentioned above.

Another way to think about the problem is the series of possible six
digit numbers in base 4. Each digit is a value between zero and three.
With one digit, four values are possible. With two digits, sixteen
values are possible. With six digits, 4096 combinations. There are
some programming languages such as Ada where you can print numbers in
any base. This same problem reduces to something like...
  for I := 0..4095 loop
    Integer_Io.Put(I, Base => 4);
    Text_Io.New_Line;
  end loop;

You can take the same values (zero through 4095) and divide by four
(w/ remainder) five times to get the six digits for processing.

For other references on possible combination generators

A visual basic application to generate combiations of characters
  http://www.freevbcode.com/ShowCode.Asp?ID=2221

C and Pascal source code of a variety of permutation and combinational
sequences
  http://www.theory.cs.uvic.ca/~cos/dis/programs.html

A java combination generator w/ sample main program
  http://www.merriampark.com/comb.htm

Please let me know if you need further information on this topic.
  --Maniac

Maniac - Thank you very much for the fast and excellent response! You
hit the nail on the head. The set of nested loops is just what I was
stuck on. Thanks again!