O（1）中是否有可能獲得m個字符長度組合的第k個元素？

你知道任何方式獲得O（1）中的第m個元素組合的第k個元素嗎？預期解決方案應適用於任何大小的輸入數據和任何m值。O（1）中是否有可能獲得m個字符長度組合的第k個元素？

讓我解釋由例如此問題（Python代碼）：

>>> import itertools 
>>> data = ['a', 'b', 'c', 'd'] 
>>> k = 2 
>>> m = 3 
>>> result = [''.join(el) for el in itertools.combinations(data, m)] 
>>> print result 
['abc', 'abd', 'acd', 'bcd'] 
>>> print result[k-1] 
abd

對於給定的數據第k個（在本實施例2-ND）M-元件組合的元件是ABD。如果不創建整個組合列表，是否可以使用該值（abd）？

我'問，因爲我的〜1,000,000m3字符的數據，這是不可能的創建完整的M-字符長度的組合子列表以獲得第k個元素。

該解決方案可以是僞代碼，或鏈接描述此問題（很可惜，我沒有找到一個）的頁面。

謝謝！

來源

2011-05-15 jack44

要做到這一點，您需要一個明確的組合訂單。 – 2011-05-15 20:10:27

不一定O（1），但以下應該是非常快：

採取原始組合算法：

def combinations(elems, m): 
    #The k-th element depends on what order you use for 
    #the combinations. Assuming it looks something like this... 
    if m == 0: 
     return [[]] 
    else: 
     combs = [] 
     for e in elems: 
      combs += combinations(remove(e,elems), m-1)

對於n初始元素和m組合長度，我們有n!/(n-m)!m!總組合。我們可以利用這一點來直接跳到我們的期望組合：

def kth_comb(elems, m, k): 
    #High level pseudo code 
    #Untested and probably full of errors 
    if m == 0: 
     return [] 
    else: 
     combs_per_set = ncombs(len(elems) - 1, m-1) 
     i = k/combs_per_set 
     k = k % combs_per_set 
     x = elems[i] 
     return x + kth_comb(remove(x,elems), m-1, k)

來源

2011-05-15 20:17:56 hugomg

第一計算r = !n/(!m*!(n-m))與元件

N量

然後地板（R/K）是第一個元素的結果的索引，

刪除它（以下向左移位一切）

待辦事項M--，N--且k = R％K

和重複直到m是0（提示當k爲0只是以下字符複製到結果）

來源

2011-05-15 20:20:42

http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

基本上，表示在階乘號碼體系中的索引，並使用其數字作爲選擇從原始序列（沒有替換）。

來源

2011-05-15 20:23:51

https://secure.wikimedia.org/wikipedia/en/wiki/Combinatorial_number_system#Ordering_combinations這難道不會幫助更多？ – 2011-05-15 20:38:03

是的。我是一個白癡。我把它看作排列，而不是組合。它們之間可能有一個簡單的映射關係，類似於從一組N個獨特元素中取出的第k個元素的第j個組合與第j個（k！）（（Nk！）'排列的第k個元素相同N個元素，但也許不是。 – 2011-05-16 09:00:38

我寫了一個類來處理常用功能與二項式係數，這是問題，你的問題似乎下落入型工作。它執行以下任務：

以良好的格式輸出所有K指數爲任何N選擇K到文件。 K-index可以用更多的描述性字符串或字母來代替。這種方法使得解決這種類型的問題非常簡單。
將K索引轉換爲排序二項式係數表中條目的正確索引。這種技術比依靠迭代的較早發佈的技術要快得多。它通過使用Pascal三角形中固有的數學屬性來做到這一點。我的論文談論這個。我相信我是第一個發現和發佈這種技術的人，但我可能是錯的。
將排序後的二項式係數表中的索引轉換爲相應的K索引。我相信它也比其他已發表的技術更快。
使用Mark Dominus方法來計算二項式係數，這是不太可能溢出和更大的數字作品。
該類使用.NET C＃編寫，並提供了一種通過使用通用列表來管理與問題（如果有）相關的對象的方法。這個類的構造函數接受一個名爲InitTable的布爾值，當true時將創建一個通用列表來保存要管理的對象。如果此值爲false，則不會創建表。該表不需要創建以執行上述4個方法。提供Accessor方法來訪問表。
有一個關聯的測試類，顯示如何使用該類及其方法。它已被廣泛測試2例，並沒有已知的錯誤。

要了解關於此類和下載代碼的信息，請參見Tablizing The Binomial Coeffieicent。

不應該很難將此類轉換爲Java，Python或C++。

來源

2012-09-25 09:32:51

O（1）中是否有可能獲得m個字符長度組合的第k個元素？

回答

相關問題