2

基于这个问题

字符串的有序固定长度组合

我创建了一个 PHP 算法，可以创建固定长度的字符组合（基本上是对 Java-answer 的重写）

private function getCombination($length, $input) {
    $result = array();

    if ($length == 0) {
        return $result;
    }

    $first = substr($input, 0, $length);
    $result[] = $first;

    if (strlen($input) == $length) {
        return $result;
    }

    $tails = $this->getCombination($length - 1, substr($input, 1));

    foreach ($tails as $tail) {
        $tmp = substr($input, 0, 1) . $tail;

        if (!in_array($tmp, $result)) {
            $result[] = $tmp;
        }
    }

    return array_merge($result, $this->getCombination($length, substr($input, 1)));
}

对于另一个问题，创建较大集合的固定长度非重复排列，我得到了一个（出色的）算法，它可以使排列可索引，通过提供一个“键”有效地使它们可寻址，当给定时，它总是会产生完全相同的排列相同的字符集和相同的长度。

好吧，现在我基本上需要相同的组合，但与我的其他问题中的排列相反。

上面的算法可以用同样的方式修改吗？意思是创建一个类似的函数

public function getCombinationByIndex($length, $index);

这将返回使用算法创建的千种可能组合中的一种，而无需事先创建它们？

4

1 回答 1

1

我在 C# 中编写了一个类来处理处理二项式系数的常用函数，这是您的问题似乎属于的问题类型 - 假设您使用组合而不是排列。它执行以下任务：

  1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。

  2. 将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。

  3. 将已排序二项式系数表中的索引转换为相应的 K 索引。我相信它也比旧的迭代解决方案更快。

  4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

  5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可使用上述 4 种方法。提供了访问器方法来访问表。

  6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

将此类移植到 php 应该非常简单。您可能不必移植类的通用部分来实现您的目标。考虑到您正在使用的组合数量，您可能需要使用比 4 字节整数更大的字长。

于 2012-11-07T17:20:28.040 回答