How to populate a Java array with variable subarrays?

Question

I'd like to write a Java method that operates something like this:

input 1, output { {0}, {1} }
input 2, output { {0, 0}, {0, 1}, {1, 0}, {1, 1} }
input 3, output { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, ... {1, 1, 1} }
...

(I use 0 and 1 in the example for concision; the lowest-level subelements might be HIGH and LOW, 'A' and 'Z', or any two other distinct values.)

This feels like a good candidate for recursion, but that's just a feeling at this point. All of my efforts so far have seemed suboptimal.* Any thoughts on a good approach, other than using a different language?

^{* For example: Loop over 0 to (2^input)-1; interpret the number as an [input]-digit binary value; use the binary digits to generate the subarray. Bleah.}

EDIT: Present generalized iterative solution

public enum Item {

   ITEM1, ITEM2, ...;  // As many as needed

   private static final int ITEM_COUNT = values().length;

   public static Item[][] allCombinationsOfSize(int comboSize) {

      int arraySize = (int) Math.pow(ITEM_COUNT, comboSize);
      Item array[][] = new Item[arraySize][];

      for ( int n = 0 ; n < arraySize ; ++n ) {
         array[n] = nthSubarray(n, comboSize);
      }

      return array;
   }

   private static Item[] nthSubarray(int n, int comboSize) {

      Item combo[] = new Item[comboSize];

      for ( int i = comboSize - 1 ; i >= 0 ; --i ) {
         combo[i] = Item.values()[n % ITEM_COUNT];
         n /= ITEM_COUNT;
      }

      return combo;
   }
}

I believe that allCombinationsOfSize is the method I'm looking for. I still have a sneaking suspicion that I'm missing something more elegant. Nevertheless, the above allows me to write this in my JUnit test ...

for ( Signal signals[] : Signal.allCombinationsOfSize(pinCount) ) {
   assertEquals(
      cls.getSimpleName() + " result",
      expectedResultFor(cls, signals),
      actualResultFor(cls, signals)
   );
}

... which is fairly straightforward.

Answer 1

Here is a recursive solution:

class Test {
  private static Object[][] createArray(int n, Object[] values)
  {
    Object[][] result = null;
    int m = values.length;
    if (n == 1)
    {
      result = new Object[m][1];
      for (int i = 0; i < m; ++i)
        result[i][0] = values[i];
    }
    else
    {
      Object[][] array = createArray(n - 1, values);
      int l = array.length;
      result = new Object[m * l][n];
      for (int i1 = 0; i1 < m; ++i1)
      {
        for (int i2 = 0; i2 < l; ++i2)
        {
          int i = i1 * l + i2;
          for (int j = 0; j < n; ++j)
            result[i][j] = j == 0 ? values[i1] : array[i2][j - 1];
        }
      }
    }
    return result;
  }

  private static void printArray(Object[][] array)
  {
    System.out.println("{");
    for (int i = 0; i < array.length; ++i)
    {
      System.out.print("  {");
      for (int j = 0; j < array[0].length; ++j)
        System.out.printf(" %s", array[i][j].toString());
      System.out.println(" }");
    }
    System.out.println("}");
  }

  public static void main(String[] args) {
    Object[] values = {'a', 'b', 'c'};
    for (int n = 1; n <= 3; ++n)
    {
      System.out.printf("n = %d:\n", n);
      Object[][] array = createArray(n, values);
      printArray(array);
      System.out.println();
    }
  }
}

Output:

n = 1:
{
  { a }
  { b }
  { c }
}

n = 2:
{
  { a a }
  { a b }
  { a c }
  { b a }
  { b b }
  { b c }
  { c a }
  { c b }
  { c c }
}

n = 3:
{
  { a a a }
  { a a b }
  { a a c }
  { a b a }
  { a b b }
  { a b c }
  { a c a }
  { a c b }
  { a c c }
  { b a a }
  { b a b }
  { b a c }
  { b b a }
  { b b b }
  { b b c }
  { b c a }
  { b c b }
  { b c c }
  { c a a }
  { c a b }
  { c a c }
  { c b a }
  { c b b }
  { c b c }
  { c c a }
  { c c b }
  { c c c }
}

Answer 2

The decision is based on the code - List of all binary combinations for a number in Java

public static void main(String args[]) throws Exception {
    int value = 4;
    populate(value);
}
public static List<List<Integer>> populate(int value) {
    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    for (int i = 0; i < Math.pow(2, value); i++) {
        List<Integer> intermediate = new ArrayList<Integer>();
        StringBuilder binary = new StringBuilder(Integer.toBinaryString(i));
        for (int j = binary.length(); j < value; j++) {
            binary.insert(0, '0');
        }
        System.out.println(binary);
        for (int k=0; k<binary.length(); k++)
        {
            intermediate.add(Integer.valueOf("" + binary.charAt(k)));
        }
        ret.add(intermediate);
    }
    System.out.println(ret);
    return ret;
}

Answer 3

The recursive approach should work. This should give you a rough idea.

    public class Main {     

        public static void main(String[] args) throws Exception {
            final int input = 6;

            final byte[] array = new byte[input];

            final List<byte[]> arrays = recurse (array, input - 1);

            for (final byte[] a : arrays) {
                print(a);
            }
        }

        private static void print(final byte[] array) {
            final StringBuilder buf = new StringBuilder ("{");

            for(final byte b : array) {
                if (buf.length() > 1) {
                    buf.append (", ");                  
                }
                buf.append (b);
            }

            buf.append ("}");

            System.out.println(buf);
        }

        private static List<byte[]> recurse(byte[] array, int input) {
            if (input > 0) {                
                final List<byte[]> subArr1 = recurse (array, input - 1);
                array[array.length - input - 1] = 1;
                final List<byte[]> subArr2 = recurse (array, input - 1);

                return sumList (subArr1, subArr2);
            }
            else {
                final byte[] arr1 = Arrays.copyOf(array, array.length);
                final byte[] arr2 = Arrays.copyOf(array, array.length);
                arr2[array.length - 1] = 1;

                return Arrays.asList(arr1, arr2);
            }           
        }

        private static List<byte[]> sumList(List<byte[]> subArr1,
                List<byte[]> subArr2) {
            final List<byte[]> result = new ArrayList<byte[]> (subArr1.size() + subArr2.size());

            result.addAll(subArr1);
            result.addAll(subArr2);

            return result;
        }
    }

And a fiddle for it.