Complex Java Permutation Generation Problem

Question

I am trying to work out the best way to generate all possible permutations for a sequence which is a fixed number of digits and each digit has a different alphabet.

I have a number of integer arrays and each one can have different length and when generating the permutations only the values of the array can occupy the position in the final results.

A specific example is an int array called conditions with the following data:

conditions1 = {1,2,3,4}
conditions2 = {1,2,3}
conditions3 = {1,2,3}
conditions4 = {1,2}
conditions5 = {1,2}

and I want to create a 5 column table of all the possible permutations - this case 144 (4x3x3x2x2). Column 1 can only use the values from conditions1 and column 2 from conditions2, etc.

output would be :

1,1,1,1,1
1,1,1,1,2
1,1,1,2,1
1,1,1,2,2
1,1,2,1,1
.
.
through to 
4,3,3,2,2

It's been too long since since I've done any of this stuff and most of the information I've found relates to permutations with the same alphabet for all fields. I can use that then run a test after removing all the permutations that have columns with invalid values but sounds inefficient.

I'd appreciate any help here.

Z.

write some code, you will face problems, then ask questions - isn't it easier that way? — Nishan
– Nishan, Commented Apr 2, 2011 at 13:48
I did write some code. The problem is the code works well when each of the conditions is the same length. But when I try differing lengths as above it breaks down. — Zoran
– Zoran, Commented Apr 2, 2011 at 15:52
Then show the code, and we can help you change it to do the right thing. (By the way, permutations is not the right word (since you don't change the order) - variation would fit better.) — Paŭlo Ebermann
– Paŭlo Ebermann, Commented Apr 2, 2011 at 16:34

Mike Samuel · Accepted Answer · 2011-04-02 15:55:42Z

1

Look ma, no recursion needed.

Iterator<int[]> permutations(final int[]... conditions) {
  int productLengths = 1;
  for (int[] arr : conditions) { productLengths *= arr.length; }
  final int nPermutations = productLengths;
  return new Iterator<int[]>() {
    int index = 0;
    public boolean hasNext() { return index < nPermutations; }
    public int[] next() {
      if (index == nPermutations) { throw new NoSuchElementException(); }
      int[] out = new int[conditions.length];
      for (int i = out.length, x = index; --i >= 0;) {
        int[] arr = conditions[i];
        out[i] = arr[x % arr.length];
        x /= arr.length;
      }
      ++index;
      return out;
    }
    public void remove() { throw new UnsupportedOperationException(); }
  };
}

Wrapping it in an Iterable<int[]> will make it easier to use with a for (... : ...) loop. You can get rid of the array allocation by doing away with the iterator interface and just taking in as argument an array to fill.

answered Apr 2, 2011 at 15:55

Mike Samuel

121k30 gold badges230 silver badges255 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Zoran Over a year ago

Thanks Mike. So much better. That works great. Just a quick question, do you mind explaining the theory behind the out[i] = arr[x % arr.length]; and x /= arr.length; lines as they are pretty much the guts of it.

Mike Samuel Over a year ago

@Zoran, even though it's not a recursive algorithm, you can think about it recursively. If I have n elements in the first array, and o * p * q permutations from the rest of the arrays, then I can reduce the problem by picking one of the n using the remainder (%) and then dividing to get an index to use with the remaining arrays.

Collectives™ on Stack Overflow

Complex Java Permutation Generation Problem

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related