Counting up with no repeating digits in a number

Question

I'm trying to optimize my programm counter. It depends on the size of the number (from 3 to 10 digits, with no repeats) - i.g. 012, 013,214,etc. My 1st solution were for loops, something like this:

private void sample() {
        int[] varValue = new int[3];
        innerloop: for (int a = 0; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                if (a == b)
                    continue;
                for (int c = 0; c < 10; c++) {
                    if (c == b)
                        continue;
                    if (c == a)
                        continue;
                    varValue[0] = a;
                    varValue[1] = b;
                    varValue[2] = c;

                    int EqOne = varValue[0] * 100 + varValue[1] * 10 + varValue[2];

                    if (EqOne == 432) {
                        System.out.println(varValue[0]);
                        System.out.println(varValue[1]);
                        System.out.println(varValue[2]);
                        break innerloop;
                    }

                }
            }

        }
    }

or for 10 digits (https://gist.github.com/TrollerN/6a0e470c539c57fd4cd73086cf6eb41b)

Then I could add those a, b, c to the int[] or ArrayList and work with it. It was ok, but with 10 different digits it ment 10 for loops with if statments + I had to create 8 different methods - one for each number of digits.

I was also trying to create ArrayList of 10 digits (0,1,2,3,4,5,6,7,8,9), shuffle it, and return 3-10 digits, but it's could make never-ending loop for 9-10 digits numbers.

My next "great" idea (no, honestly that one was the stupidest so far :D) was to save ArrayList of combinations to file, for each case, and then load the needed one and go through it to find solution.

I was thinking about createing some method which will take the number of digits ("so it knows how many loops it needs") and/or last solution so it knows were to start.

EDIT: I've modified the question with sample method. Of Course the int EqOne and If statment are much more complex, but it technicaly shows what I wanted to achieve - at least I hope :P

What I was looking for was a method, that will create as many loops and as big array/arraylist as needed?

Answer 1

Assuming you want numbers of the given length, not strings, one way to do it is to remember which digits are currently in use using a boolean[10], so they can be skipped fast.

Then keep the digits in an array and increment last digit like you would a normal number. When it rolls over, you increment the second-last digit, and so forth, resetting the trailing digits to unused numbers.

Example: If current number is 1097, it goes like this:

Digits  In Use               Description
1097    0 1 _ _ _ _ _ 7 _ 9
1097    0 1 _ _ _ _ _ _ _ 9  Clear in-use of last digit
1098    0 1 _ _ _ _ _ _ _ 9  Increment last digit
1098    0 1 _ _ _ _ _ _ 8 9  Mark in-use
=======================================================
1098    0 1 _ _ _ _ _ _ _ 9  Clear in-use of last digit
1099    0 1 _ _ _ _ _ _ _ 9  Increment last digit, but it's in use
109?    0 1 _ _ _ _ _ _ _ 9  Rollover, so go to previous digit
109?    0 1 _ _ _ _ _ _ _ _  Clear in-use
10??    0 1 _ _ _ _ _ _ _ _  Rollover, so go to previous digit
10??    _ 1 _ _ _ _ _ _ _ _  Clear in-use
11??    _ 1 _ _ _ _ _ _ _ _  Increment digit, but it's in use
12??    _ 1 _ _ _ _ _ _ _ _  Increment digit
12??    _ 1 2 _ _ _ _ _ _ _  Mark in-use
120?    0 1 2 _ _ _ _ _ _ _  Set to first unused digit, and mark in-use
1203    0 1 2 3 _ _ _ _ _ _  Set to first unused digit, and mark in-use
=======================================================

As you can see, the logic makes it go from 1097 to 1098 to 1203.

Here is the logic for that. See IDEONE for running example.

final class UniqueDigitCounter {
    private int[]     digits;
    private boolean[] inUse = new boolean[10];
    public UniqueDigitCounter(int digitCount) {
        if (digitCount < 1 || digitCount > 10)
            throw new IllegalArgumentException("Invalid digit count: " + digitCount);
        this.digits = new int[digitCount];
        for (int i = 0; i < digitCount; i++) {
            this.digits[i] = i;
            this.inUse[i] = true;
        }
    }
    public long next() {
        if (this.digits == null)
            return -1; // end of sequence
        long value = 0;
        for (int i = 0; i < this.digits.length; i++)
            value = value * 10 + this.digits[i];
        for (int i = this.digits.length - 1; ; i--) {
            if (i == -1) {
                this.digits = null; // end of sequence
                break;
            }
            int digit = this.digits[i];
            this.inUse[digit] = false;
            if ((digit = nextDigit(digit + 1)) != -1) {
                this.digits[i] = digit;
                while (++i < this.digits.length)
                    this.digits[i] = nextDigit(0);
                break;
            }
        }
        return value;
    }
    private int nextDigit(int minDigit) {
        for (int digit = minDigit; digit < 10; digit++)
            if (! this.inUse[digit]) {
                this.inUse[digit] = true;
                return digit;
            }
        return -1;
    }
}

Answer 2

It's difficult to generate the list you're after directly since you're not allowing repeating digits. I think the easiest way to do this would be to first get all the n-length combinations in lexicographic order, then get all permutations of each of the combinations. That is, for the n = 2 case, you would generate "01", "02", ... , "78", "79", "89", and then would get all of the permutations of each of those.

Here's a quick program I put together that should get you what you're after:

public static List<String> getCombinations (String digits, int n) {

  List<String> out = new ArrayList<String>();
  for ( int k = 0; k < digits.length (); ++k ) {
    if ( n == 1 )
      out.add (digits.charAt (k) + "");
    else {
      for ( String s : getCombinations (digits.substring (k + 1), n - 1) ) {
        out.add (digits.charAt (k) + s);
      }
    }
  }

  return out;
}


public static List<String> getPermutations (String s, String prefix) {

  List<String> out = new ArrayList<String>();

  if ( s.length () == 1 ) {
    out.add (prefix + s);
  }
  else {
    for ( int i = 0; i < s.length (); ++i ) {
      out.addAll (getPermutations (prefix + s.charAt (i), s.substring (0, i) + s.substring (i + 1)));
    }
  }

  return out;
}


public static List<String> getPermutations (List<String> combinations) {
  List<String> out = new ArrayList<String>();
  for ( String s : combinations )
    out.addAll (getPermutations (s, ""));

  return out;
}


public static void main (String[] args) {

  List<String> combinations = getCombinations ("0123456789", 3);

  List<String> permutations = getPermutations (combinations);

  for ( String s : permutations ) {
    System.out.println (s);
  }

}