创建具有固定长度

可转位非重复的组合基于此问题创建具有固定长度

Ordered Fixed Length Combination of a String

我创建的固定长度创建字符的组合的PHP算法（基本上是Java的答案的重写）

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

对于另一个问题，Create fixed length non-repeating permutation of larger set，我是通过提供一个“钥匙”，将始终把生产EXA给予（辉煌）算法，这将使排列可转位，有效地使他们adressable当给定相同的一组字符和相同的长度时，ct相同的排列。

那么，现在我基本上需要相同，但对于组合，与排列相比，在我的另一个问题。

上述算法可以用同样的方法修改吗？含义营造出宛如

public function getCombinationByIndex($length, $index);

一个函数会返回一个组合出一千可能与该算法创建的，而无需创建他们事先？

来源

2012-11-07 Florian Peschka

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

以良好的格式输出所有K指数为任何N选择K到文件。 K-index可以用更多的描述性字符串或字母来代替。
将K索引转换为排序二项式系数表中条目的正确索引。这种技术比依靠迭代的较早发布的技术要快得多。它通过使用Pascal三角形中固有的数学属性来做到这一点。
将排序后的二项式系数表中的索引转换为相应的K索引。我相信它比以前的迭代解决方案更快。
使用Mark Dominus方法来计算二项式系数，这是不太可能溢出和更大的数字作品。
该类使用.NET C＃编写，并提供了一种通过使用通用列表来管理与问题（如果有）相关的对象的方法。这个类的构造函数接受一个名为InitTable的布尔值，当true时将创建一个通用列表来保存要管理的对象。如果此值为false，则不会创建表。该表不需要创建，以使用上述4种方法。提供Accessor方法来访问表。
有一个关联的测试类，显示如何使用该类及其方法。它已被广泛测试2例，并没有已知的错误。

要了解关于此类和下载代码的信息，请参见Tablizing The Binomial Coeffieicent。

它应该是非常直接的将此类移植到php。你可能不必为了实现你的目标而移植类的通用部分。取决于您正在使用的组合的数量，您可能需要使用比4字节整数大的字大小。

来源

2012-11-07 17:20:28

创建具有固定长度

回答

相关问题