计算没有重复和没有“经典"的所有n个大小的排列.订购 [英] Computing all n-sized permutations without repetitions and without "classic" ordering

问题描述

好的，我需要在一次摄影比赛中实现这一点……我主要拥有N张图片，并且我需要生成这些图片的大小为2的排列，而无需重复，例如:

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

foo.png VS bar.png

等于

bar.png VS foo.png

bar.png VS foo.png

另一件事，我不能每次都预先生成al排列，因此我需要一个函数，给定上一个排列，它将返回我的下一个排列(如果可能的唯一排列结束，则返回NULL).

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).

我通过以下PHP函数解决了这个问题:

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;
}

因此:

$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 ) ); 
}

将输出:

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

现在，我真的很想为其添加一些熵...正如我所看到的，我的意思是，通常重复组合的第一项(0,1 0,2 0,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:每个挑战我都有约500张照片，因此不能存储位掩码或类似内容.

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

谢谢.

推荐答案

如果您希望以未排序的方式对大小k进行某些排列，则可以在基数2中有一个n位的计数器，并打印下一个值(每次都有k 1)，例如大小为3(且k = 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

因此，您的输出将为011、101和110(实际上将转换为(1,2)，(3,1)，(3,2))，这并不是您想要的，而是计数器的大小增长，这将更明智，但是使用这样的计数器会很费时间，但是如果您的图片尺寸小于20，则它足够快(因为2 ^ 20 = 1百万，这并不大).同样，通过获得100之类的数字，您可以简单地以此启动计数器并获得下一个值.而且，这可以简单地扩展以生成大小为k的排列.

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.

这篇关于计算没有重复和没有“经典"的所有n个大小的排列.订购的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！