0

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.

Improve this question
4
  • Is this supposed to be homework (real or self-imposed)? Yes, recursion has a natural 'fit', in a couple of different ways. Please note that you're going to want more than one actual method, even if just as helpers (but only one should be exposed). What about using the Collections classes, and possibly dealing with Generics? Commented Nov 20, 2012 at 0:09
  • Why do your current efforts seem suboptimal, and what did you try towards a recursive approach? Commented Nov 20, 2012 at 0:16
  • @Clockwork-Muse: This isn't homework. I've been messing around with a hardware gate simulator (a personal learning project), and I'm looking to test all possible combinations on pin inputs on a gate. Helper functions are A Good Thing, in my book. Commented Nov 20, 2012 at 0:36
  • @arne.b: I can't articulate my answer to the first question. My efforts have all just had an inelegant feel to them. As for recursion, I'm letting that idea percolate for a while. Commented Nov 20, 2012 at 0:37

3 Answers 3

Reset to default
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 }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Neat. It's more general than what I was originally looking for, which is also good. Thanks!
0

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.

Improve this answer

1 Comment

I'll have to think about this one for a while. Thanks.
0

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;
}
Improve this answer

1 Comment

Very similar to what I came up with myself. Thanks for the confirmation of the idea.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.