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

Question

我知道这个话题有很多讨论，但我似乎找不到适合我需要的任何实现。

我有以下一组字符:

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

Answer 1

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

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

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