Computing all n-sized permutations without repetit

Question

Ok guys, i need to implement this for a photo contest ... i have a main set of N pictures, and i need to generate the permutations of size 2 of those pics without having repetitions, for instance:

foo.png VS bar.png

is equal to

bar.png VS foo.png

Another thing, i can not pre generate al permutations each time, so i need a function that, given the previous permutation, will return me the next one (or NULL if the possible unique permutations are over).

I solved this problem with the following PHP function:

function getNextPermutation( $aPermutableItems, $iPermutationSize, $aPreviousPermutation = NULL )
{
  $aNextPermutation = $aPreviousPermutation;
  $iLastIndex       = $iPermutationSize - 1;
  $iPermutableItems = count($aPermutableItems);

  // Any previous permutation ?
  if( $aPreviousPermutation )
  {
    // Loop the elements backwards
    for( $i = $iLastIndex; $i >= 0; $i-- )
    {
      // Can the current element be incremented without reaching the limit ?
      if( ++$aNextPermutation[ $i ] >= $iPermutableItems )
      {
        // Increment the previous element
        $iPrevValue = ++$aNextPermutation[ $i - 1 ];
        // Reset the current element with the value of the previous plus one
        $iNextValue = $aNextPermutation[ $i ] = $iPrevValue + 1;
        // Skip the previous element because it was just incremented
        $i--;
        // If one of the two elements reached the limit, we are in the exit condition
        if( $iPrevValue >= $iPermutableItems || $iNextValue >= $iPermutableItems )
          return FALSE;
      }
      // Limit still to be reached for the i-th element, skip previous ones
      else
        break;
    }
  }
  // Am i able to generate the first permutation ?
  else if( $iPermutationSize <= $iPermutableItems )
    $aNextPermutation = range( 0, $iLastIndex );
  // Permutation impossible to generate because we don't have enough elements in the main set
  else
    $aNextPermutation = FALSE;

  return $aNextPermutation;
}

So that:

$iPerm  = 0;
$aPrev  = NULL;
$aItems = array( 0, 1, 2, 3, 4 );

while( ($aPrev = getNextPermutation( $aItems, 2, $aPrev )) != FALSE )
{
  echo sprintf( "%2d : %s\n", $iPerm++, implode( ', ',  $aPrev ) ); 
}

Will output:

0 : 0, 1
1 : 0, 2
2 : 0, 3
3 : 0, 4
4 : 1, 2
5 : 1, 3
6 : 1, 4
7 : 2, 3
8 : 2, 4
9 : 3, 4

Now, i'd really like to add some entropy to it ... what i mean is, as you can see, the first item in combinations is often repeated ( 0,1 0,2 0,3 ), and in my case this is not good because i would see the same picture for 4 continuos permutations.

Is there a way to modify (or re implement) my algorithm to have something like (for instance):

0 : 0, 1
1 : 1, 2
2 : 0, 3
3 : 3, 4
4 : 0, 2
5 : 1, 3
6 : 0, 4
7 : 2, 3
8 : 2, 4
9 : 1, 4

Obviously i can't just shuffle the array of permutations, because as i wrote, i do not have the whole permutations array, but only the previous permutation that will give my the next one once my algorithm is applied.

PS: I have around 500 photos for each challenge, so storing bitmasks or things like those is not acceptable.

Thanks.

Answer 1

Create an array with k ones and N-k zeroes. Then use C++ std::next_permutation like algorithms which work as follows:

1. Go from left and find rightmost one preceeded by zero.
2. Put one in place of zero and sort the rest of array.

For example, Start with 0 0 0 0 1 1 1

Find rightmost one in place 5, move it to place 4: 0 0 0 1 0 1 1

Sort the rest: 0 0 0 1 0 1 1

Find rightmost one in place 6, move it to place 5: 0 0 0 1 1 0 1

Sort the rest: 0 0 0 1 1 0 1

Find rightmost one in place 7, move it to place 6: 0 0 0 1 1 1 0

Sort the rest: 0 0 0 1 1 1 0

Find rightmost one in place 4, move it to place 3: 0 0 1 0 1 1 0

Sort the rest: 0 0 1 0 0 1 1

And so on...

Answer 2

If you want some permutation of size k in unsorted manner, you can have a counter of n bits in base 2, and print the next value (which has k 1) each time, for example counter of size 3 (and k=2):

000
001
010
011
100
101
110

So, your output will be 011, 101 and 110 (in fact will be converted to (1,2),(3,1),(3,2)) it's not exactly what you want but when the counter size grows, it will be more sensible, but it's time consuming using such a counter, but if your picture sizes is smaller than 20 it's fast enough (because 2^20 = 1 million which is not big). Also by getting number like 100, you will simply can initiate your counter with this and get next value. Also this simply extensible to generate permutations of size k.