Java Algoirthm number of Combinations of variables (Similar to Bit String Algoirthm)

Question

I have a problem I'm trying to solve in Java and I cannot figure out the algorithm that I'm going to need to follow. This problem is similar to the Bit String problem (how many bit strings are there of length x), but with some added difficulty. I'm not even sure the algorithm for solving the normal bit string problem anyway.

So here's my actual problem: I have 5 variables. Say Q W X Y Z. Each variable can take one of 3 values (so like bit string can take 1 or 0, but this can take say 0, 1, or 2). I need to generate all possible combinations of this "bit string".

So one combination may be 00000 another may be 10002, another could be 22222, etc. I need to print out all combinations of this "bit string"

I'm really stumped on how to solve this problem or even come up with a decent algorithm.

Thanks for the help! Much appreciated.

Answer 1

Try this:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Generator implements Iterable<String> {

    private int len;
    public Generator(int len) {
        this.len = len;
    }

    public Iterator<String> iterator() {
        return new Itr(len);
    }

    private class Itr implements Iterator<String> {
        private int[] a;
        private boolean done;

        public Itr(int len) {
            a = new int[len];
            done = false;
        }

        @Override
        public String next() {
            if (done) throw new NoSuchElementException();
            String s = getString();
            step(a.length - 1);
            return s;
        }

        @Override
        public boolean hasNext() { return !done; }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private void step(int index) {
            if (a[index] == 2) {
                if (index == 0) {
                    done = true;
                    return;
                }
                a[index] = 0;
                step(index - 1);
            } else
                a[index]++;
        }

        private String getString() {
            StringBuilder s = new StringBuilder();
            for (int i : a)
                s.append(i);
            return s.toString();
        }
    }

}

Then you could do something like this:

Generator g = new Generator(2 /* length of resulting strings */);
for (String s : g)
    System.out.println(s);

Output:

00
10
20
01
11
21
02
12
22

Basically, all we're doing here is counting upwards in base-3 until we reach 222...222 (where the number of 2s is specified when instantiating a Generator). Hope this helps!

Answer 2

You need to consider the math behind it. It makes things a lot easier when you've understood how to enumerate these strings. This will yield an obvious way not only of generating the strings, but also allow you to "random access" them, i.e. you can also write a get(int num) method that will produce the numth element.

The math is pretty simple, it only involves modulo operations (%) and divisions, and it really pays off when you figure this out yourself.

As a simple first preparation, assume that you have n decimal digits.

• Given a number x, how do you get the nth digit?
• Given n digits, how do you get the number x?

After you have figured this out, try to abstract from having 10 digits. Say, practise counting in binary. Then in ternary, which will be your solution for 3 digits.

Answer 3

To achieve this, you could just count up to your maximum value (22222 in your example) using a radix of 3. The BigInteger class supports output and instantiation with an arbitrary radix. The BigInteger class, however, does not support zerofill which is why I added this myself. Here is the resulting solution:

public static void main( String[] args ) {
    System.out.println( new BitStrings().generateBitStrings( new BigInteger( "2222", 3 ) ) );
}

public List<String> generateBitStrings( BigInteger maxValue ) {
    final String format = "%0" + maxValue.toString( 3 ).length() + "d";
    BigInteger current = BigInteger.ZERO;
    final List<String> result = new ArrayList<String>( maxValue.intValue() );
    do {
        result.add( String.format( format, Long.valueOf( current.toString( 3 ) ) ) );
        current = current.add( BigInteger.ONE );
    } while(current.compareTo( maxValue ) <= 0);
    return result;
}

Output:

[0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0200, 0201, 0202, 0210, 0211, 0212, 0220, 0221, 0222, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1021, 1022, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1121, 1122, 1200, 1201, 1202, 1210, 1211, 1212, 1220, 1221, 1222, 2000, 2001, 2002, 2010, 2011, 2012, 2020, 2021, 2022, 2100, 2101, 2102, 2110, 2111, 2112, 2120, 2121, 2122, 2200, 2201, 2202, 2210, 2211, 2212, 2220, 2221, 2222]

Hope this answers your question.

Answer 4

This should be a relatively easy problem to solve.

Essentially, you're merely computing the set of strings Σ^5 where Σ = { 0, 1, 2 }.

static Iterable<String> strings(final int radix, final int digits) {
  return new Iterable<String>() {

    public Iterator<String> iterator() {
      return new Iterator<String>() {

        private final int hi = (int) Math.pow(radix, digits);
        private int cursor;

        public boolean hasNext() {
          return cursor < hi;
        }

        public String next() {
          int v = cursor++;
          int n = digits;
          final char[] buf = new char[n];
          while (n > 0) {
            buf[--n] = (char) (v % radix + '0');
            v /= radix;
          }
          return new String(buf);
        }

        public void remove() {
          throw new UnsupportedOperationException();
        }
      };
    }
  };
}

... which can be used as follows:

for (final String val : strings(3, 5)) {
  System.out.println(val);
}

Basically, we generate the numbers in the interval [0, 3^5), where 3 is our radix and 5 our desired string length, and then convert the numbers into ternary form. 0 becomes 00000, 3^5 becomes 100000.