How can I find all of the permutations consisting of 1 element from a variable number of arrays of variable length?

Question

I have an array U of arrays D that vary in length. I need to be able to return all permutations of array indices that would select a different permutation consisting of 1 element from each set. I also require that this alorithm gets represented as an object that only remembers the last permutation, and returns the next permutation with a get_next method.

For instance, U = [array_of_size_n1, array_of_size_n2, array_of_size_n3] There would be n1*n2*n3 permutations, each 3 elements long.

Edit: the number of sets also varies.

Answer 1

So ... what about this isn't straightforward?

You want an iterator. You want it to iterate over the last array. When it gets to the end of that array, increment its current position in the second-last array and go back to the start of the last array.

psuedocode using C#s yield return syntax:

foreach n1 in a1
    foreach n2 in a2
        foreach n3 in a3
            yield return (n1, n2, n3)

EDIT: If the number of sets varies, you could use some form of recursion:

function next(list)
    firstArray = list.first
    iterator = iterator(list.rest)
    if !iterator
        foreach i in firstArray
            yield return i
    else
        foreach i in firstArray
            while (iterator.hasNext)
                yield return (i, iterator.next)

Consider the behaviour when a list of length 1 is passed in, then consider the behaviour for a list of length 2, and satisfy yourself that it does in fact work.

Answer 2

You could just keep a counter for your individual position in each array. In your get_next method increase the counter for one and mod it by the length of the array. Then you just increase the next counter every time the previous one rolls over to 0;

if (pos3 == array_of_size_n3 -1)
{
   if (pos2 == size_of_array_2 -1)
   {
       pos1 = (pos1 + 1) % size_of_array_1

   }
   pos2 = (pos2 + 1) % size_of_array_2
}
pos3 = (pos3 + 1) % size_of_array_3

print array1[pos1], array2[pos2], array3[pos3]

EDIT: In the case the number of arrays varies, hold your position variables in an array. Actually that would probably be better anyway. That way you can refer to the pos variable in the same way you refer to the array itself.

Answer 3

To tack on to what Anon said, you don't just loop over them. You maintain state in your class so that you know what your last index was for each array. The logic is the same, but you don't run in a continuous loop. The pseudo-code logic would be:

get_next()
{
  oldn3 = this.n3;
  oldn2 = this.n2;
  oldn1 = this.n1;

  if(this.n3 == this.a3.Count)
     this.n3 = 0;
  else
     this.n3++;

  if(oldn3 > this.n3)
    if(this.n2 == this.a2.Count)
      this.n2 = 0;
    else
      this.n2++;

  if(oldn2 > this.n2)
    if(this.n1 == this.a1.Count)
      this.n1 = 0;
    else
      this.n1++;

  if(oldn1 > this.n1)
    return NO_MORE_PERMS;

  return [n1,n2,n3];  
}

getCurrent()
{
  return [n1,n2,n3];
}

Answer 4

If you're using python, this is part of the standard library: itertools.product. But assuming you're not, here's a pseudocode version.

// Create an initialised array of indexes.
int[] index0(arrays) {
    // We require all arrays to be non-empty.
    for a in arrays {
        assert len(a) != 0;
    }
    return new int[len(arrays)];
}

// Increment the indices. Returns false when the indices wrap round to the start.
bool next_index(indices, arrays) {
    for (i = len(indices) - 1; i >= 0; --i) {
        indices[i] += 1
        if indices[i] < len(arrays[i]) {
            return true;
        }
        indices[i] = 0;
    }
    return false;
}

You can use it like this (assuming none of your arrays are empty). This example prints out every combination of elements from the arrays.

indices = index0(arrays); 
{
    for (i = 0; i < len(arrays); ++i) {
        print arrays[i][indices[i]];
    }
    print
} while next_index(indices);