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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP-创建更大的集合的固定长度的非重复排列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2856字，纯文字阅读大概需要5分钟。

内容图文

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

我具有以下字符集：

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

内容总结

以上是互联网集市为您收集整理的PHP-创建更大的集合的固定长度的非重复排列全部内容，希望文章能够帮你解决PHP-创建更大的集合的固定长度的非重复排列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端