title: Computing all n-sized permutations without repetitions and without "classic" ordering
body: <p>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:</p>
  
  <p>foo.png VS bar.png</p>
  
  <p>is equal to</p>
  
  <p>bar.png VS foo.png</p>
  
  <p>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).</p>
  
  <p>I solved this problem with the following PHP function:</p>
  
  <pre><code>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 &gt;= 0; $i-- )
      {
        // Can the current element be incremented without reaching the limit ?
        if( ++$aNextPermutation[ $i ] &gt;= $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 &gt;= $iPermutableItems || $iNextValue &gt;= $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 &lt;= $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;
  }
  </code></pre>
  
  <p>So that:</p>
  
  <pre><code>$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 ) ); 
  }
  </code></pre>
  
  <p>Will output:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>
  
  <p>Is there a way to modify (or re implement) my algorithm to have something like (for instance):</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>
  
  <p>PS: I have around 500 photos for each challenge, so storing bitmasks or things like those is not acceptable.</p>
  
  <p>Thanks.</p>