Count in base 2, 3, 4 etc in Java and output all permutations

Question

I want to write a function in Java that takes as input an integer and outputs every possible permutation of numbers up to that integer. For example:

f(1)

0

f(2) should output:

00 01 10 11

f(3) should output:

000 001 002 010 011 012 020 021 022 100 .... 220 221 222

That is it should output all 27 permutations of the digits of the numbers 0, 1, 2.

f(4) should output 0000 0001 0002 0003 0010 ... 3330 3331 3332 3333

f(5) should output 00000 00001 ... 44443 44444

I have been trying to solve this problem but cannot seem to work out how to do it and keep getting confused by how many loops I need. Does anyone know how to solve this problem? Thanks in advance.

Sounds like homework. If so, you should tag it as such. Also, what have you tried? — nicholas.hauschild, Sep 12 '12 at 21:28
No this is not homework. It is part of a much bigger piece of code that I am writing for graph exploration. — tree-hacker, Sep 12 '12 at 21:28
I'm trying to understand the question. The last value that f(1) prints is 0, the last value that f(2) prints is 11. The last value that f(3) prints is 222. Does this progress to 3333, 44444, 555555, 6666666...? — Bob Kaufman, Sep 12 '12 at 21:30
You need three things: 1) one loop that counts from 0 to your last value, 2) a function to calculate your last value, 3) and a function to format each individual value. Given that, is there a particular piece that you're having trouble with? — Bob Kaufman, Sep 12 '12 at 21:32
That is the essence of software development! Look at your values, establish a pattern, come up with a function that works in the first few cases then see if it works for all cases. I'll take a crack at it, but it'll take a few minutes. EDIT: ... or we could have a look at oldrimb's solution below... — Bob Kaufman, Sep 12 '12 at 21:37
Is max argument for that method 10? If not What would be last result of f(11)? `10_10_10_10_10_10_10_10_10_10_10` (I used "_" for better readability) or maybe something like `aaaaaaaaaa` like in Hexadecimal? — Pshemo, Sep 12 '12 at 21:39
No there is no maximum argument. I have just printed out the numbers without spaces for the output but in my actual code I will use the number output and the printed output is not that important. — tree-hacker, Sep 12 '12 at 21:41
possible duplicate of [Quickest way to convert a base 10 number to any base in .NET?](http://stackoverflow.com/questions/923771/quickest-way-to-convert-a-base-10-number-to-any-base-in-net) — NominSim, Sep 12 '12 at 21:58

score 3 · Accepted Answer · edited May 23 '17 at 11:59

Just count and convert. I wrote something should help in an earlier answer here.

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 String pad;
        {
          final StringBuilder buf = new StringBuilder(digits);
          for (int n = digits; n >= 0; --n) {
            buf.append('0');
          }
          pad = buf.toString();
        }

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

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

        public String next() {
          final String rsl = Integer.toString(cursor++, radix);
          return pad.substring(0, digits - rsl.length()) + rsl;
        }

        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. You must also take care to not use too large a radix, otherwise the resulting String will contain bad characters.

The solution here is to merely call strings(n, n). Note that, depending on how large your radix or desired digit lengths are, you may wish to instead use long or even BigInteger.

Also, since it relies on Integer.toString, make sure you remember the following caveat...

If the radix is smaller than Character.MIN_RADIX or larger than Character.MAX_RADIX, then the radix 10 is used instead.

You can see the value for Character.MIN_RADIX is 2 and MAX_RADIX is 36. If you use a radix outside of this range, it will default to 10... you will need to write your own conversion with a custom extended character set for digits. The general form of such an itoa function is as follows:

    private static final char[] ALPHABET = { '0', '1', '2', '3', ... };

    public static String itoa(int value, final int radix, int width) {
      final char[] buf = new char[width];
      while (width > 0) {
        buf[--width] = ALPHABET[value % radix];
        value /= radix;
      }
      return new String(buf);
    }

Below is a working example for your usage (see result on ideone).

static Iterable<String> f(final int n) {
  return strings(n, n);
}

public static void main(final String[] argv) {
  for (int n = 1; n <= 5; ++n) {
    for (final String string : f(n)) {
      System.out.printf("%s ", string);
    }
    System.out.println();
  }
}

... which produces:

0

00 01 10 11

000 001 002 010 011 012 020 021 022 100 101 102 110 111 ...

0000 0001 0002 0003 0010 0011 0012 0013 0020 0021 0022 0023 0030 ...

00000 00001 00002 00003 00004 00010 00011 00012 00013 00014 00020 00021 00022 ...

Count in base 2, 3, 4 etc in Java and output all permutations

1 Answers1