創建具有固定長度

可轉位非重複的組合基於此問題創建具有固定長度

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

創建具有固定長度

回答

相關問題