创建较大集合的固定长度非重复排列

我知道这个话题被广泛讨论，但我似乎找不到任何适合我需求的实现。

我有以下字符集：

abcdefgh

我想获得所有可能的排列或组合（不重复），但在有限（可变）字符集上，意思是如果我输入字符和数字2，结果应该是这样的

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

我希望你明白我的意思。我目前有一个实现，可以给我排列all字符，但我不知道如何实现空间有限对于这些排列：

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

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

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

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.

where |S|是 S 中当前元素的数量。

我们实际上可以将这个选择序列编码为一个整数。一种方法是更改​​算法：

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 是输入中的字母数）。

当然，我们也可以再次解码，在 PHP 中，会是这样的：

// 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映射到唯一的结果。）

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

$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>';
?>