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

我具有以下字符集：

a b c d e f g h

我想获得所有可能的排列或组合(不重复),但是在有限的(可变的)字符集上,这意味着如果我输入字符和数字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

希望您能理解我的发展方向.我目前有一个实现可以给我所有字符的排列的实现,但是我无法解决如何为这些排列实现有限的空间：

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.

| 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将唯一编码此特定选择序列.它基本上将其编码为mixed-radix数字.一位使用基数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>';
?>