创建较大集合的固定长度的非重复排列 [英] Create fixed length non-repeating permutation of larger set

问题描述

我知道这个话题已经讨论了很多，但是我似乎找不到适合我需求的实现方式.

I know this topic is much discussed but I can't seem to find any implementation that fits my needs.

我有以下字符集:

a b c d e f g h

a b c d e f g h

我想获得所有可能的排列或组合(不重复)，但使用一组有限(可变)的字符，这意味着如果我输入字符和数字2，结果应该看起来像

I want to get all possible permutations or combinations (non repeating), but on a limited (variable) set of characters, meaning if I input the characters and the number 2, the results should look like

ab ba ac ca ad da ae ea af fa ag ga ah ha
bc cb bd db be eb bf fb bg gb bh hb
cd dc ce ec cf fc cg gc ch hc
de ed df fd dg gd dh hd
ef fe eg ge eh he
fg gf fh hf
gh hg

希望您能理解我的发展方向.我目前有一种实现方式，可以为我提供所有字符的排列，但是我无法为如何为这些排列实现有限的空间而烦恼:

I hope you understand where I'm going with this. I currently have an implementation that gives me the permutations of all characters, but I can't wrap my head around how to implement a limited space for those permutations:

public function getPermutations($letters) {
    if (strlen($letters) < 2) {
        return array($letters);
    }

    $permutations = array();
    $tail = substr($letters, 1);

    foreach ($this->getPermutations($tail) as $permutation) {
        $length = strlen($permutation);

        for ($i = 0; $i <= $length; $i++) {
            $permutations[] = substr($permutation, 0, $i) . $letters[0] . substr($permutation, $i);
        }
    }

    return $permutations;
}

推荐答案

如果一次只需要一个元素，则可以通过分别生成每个元素来节省内存.

If you only need one element at a time, you can save on memory by generating each element individually.

如果我们想在您的一组预期输出中生成一个随机字符串，则可以使用以下算法:

If we wanted to generate a random string in your set of expected outputs, we could use this algorithm:

Given a set of characters S, and a desired output length K:
  While the output has less than K characters:
    Pick a random number P between 1 and |S|.
    Append the P'th character to the output.
    Remove the P'th character from S.

其中|S|是S中当前的元素数.

where |S| is the current number of elements in S.

我们实际上可以将此选择序列编码为整数.一种方法是这样更改算法:

We can actually encode this sequence of choices into an integer. One way to do that is to change the algorithm as such:

Given a set of characters S, and a desired output length K:
  Let I = 0.
  While the output has less than K characters:
    I = I * (|S| + 1).
    Pick a random number P between 1 and the number of elements in S.
    I = I + P.
    Append the P'th character to the output.
    Remove the P'th character from S.

运行此算法后，值I将唯一编码此特定选择序列.它基本上将其编码为混合基数号；一位使用基数N，下一位使用N-1，依此类推，直到最后一位为基数N-K + 1(N是输入中的字母数).

After running this algorithm, the value I will uniquely encode this particular sequence of choices. It basically encodes this as a mixed-radix number; one digit uses base N, the next uses N-1, and so on until the last digit which is base N-K+1 (N being the number of letters in the input).

自然，我们也可以再次对其进行解码，而在PHP中，将是这样的:

Naturally, we can also decode this again, and in PHP, that would be something like this:

// Returns the total number of $count-length strings generatable from $letters.
function getPermCount($letters, $count)
{
  $result = 1;
  // k characters from a set of n has n!/(n-k)! possible combinations
  for($i = strlen($letters) - $count + 1; $i <= strlen($letters); $i++) {
    $result *= $i;
  }
  return $result;
}

// Decodes $index to a $count-length string from $letters, no repeat chars.
function getPerm($letters, $count, $index)
{
  $result = '';
  for($i = 0; $i < $count; $i++)
  {
    $pos = $index % strlen($letters);
    $result .= $letters[$pos];
    $index = ($index-$pos)/strlen($letters);
    $letters = substr($letters, 0, $pos) . substr($letters, $pos+1);
  }
  return $result;
}

(请注意，为简单起见，这种特定的解码算法与我之前描述的编码算法并不完全对应，但是保留了将给定的$index映射到唯一结果的理想属性.)

(Note that for simplicity, this particular decoding algorithm does not correspond exactly to the encoding algorithm I previously described, but maintains the desirable property of a given $index mapping to a unique result.)

要使用此代码，您需要执行以下操作:

To use this code, you would do something like this:

$letters = 'abcd';
echo '2 letters from 4:<br>';
for($i = 0; $i < getPermCount($letters, 2); $i++)
  echo getPerm($letters, 2, $i).'<br>';

echo '<br>3 letters from 4:<br>';
for($i = 0; $i < getPermCount($letters, 3); $i++)
  echo getPerm($letters, 3, $i).'<br>';
?>

这篇关于创建较大集合的固定长度的非重复排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！