計算字母排列的第n個6個字符

我一直在研究幾天，試圖找出解決這個問題的方法。如果需要的話，我會很樂意爲某人諮詢時間來解決這個問題。計算字母排列的第n個6個字符

我目前使用Python itertools來生成一個32個字符的6個字符的排列。通過下面的命令：

gen = itertools.permutations('ABCDEFGHJKLMNPQRSTUVWXYZ23456789',6)

從文檔，該功能產生「R-長度元組，所有可能的排序，沒有重複的元素」。

您可以使用該庫通過以下命令來獲取產生排列的片（本例中抓住第10個排列，0-10：

gen2 = itertools.islice(gen,0,10)

當遍歷結果第二代，我得到正是我想要的：

('A', 'B', 'C', 'D', 'E', 'F') 
('A', 'B', 'C', 'D', 'E', 'G') 
('A', 'B', 'C', 'D', 'E', 'H') 
('A', 'B', 'C', 'D', 'E', 'J') 
('A', 'B', 'C', 'D', 'E', 'K') 
('A', 'B', 'C', 'D', 'E', 'L') 
('A', 'B', 'C', 'D', 'E', 'M') 
('A', 'B', 'C', 'D', 'E', 'N') 
('A', 'B', 'C', 'D', 'E', 'P') 
('A', 'B', 'C', 'D', 'E', 'Q')

這是偉大的，但我真正的願望是能夠選擇任意的排列和置換列表抓住它（而不必存儲所有可能的排列值），如果我的計算。在生成6個字符時是正確的上面列出的字母順序有652,458,240種可能的組合。所以我希望能夠做到像10,353,345排列。問題是，如果你使用上面的islice函數來獲取這個排列，那麼在返回給你之前，它必須迭代整個排列集合達到10,353,345個元素。正如你可以想象的，這是非常低效的，需要很長時間才能返回。

我的問題是，實現所需計算的算法是什麼？我已經在階乘分解和基本n轉換方面做了相當多的研究，但一直無法找到任何解釋如何實現接近我想要的東西或我可以修改以實現此結果的算法的任何內容。

任何幫助將不勝感激！

來源

2014-02-22 Jordan

@jonrsharpe OP似乎已經知道了。 – thefourtheye

這顯然不是重複的。 OP知道http://stackoverflow.com/questions/12007820/better-ways-to-get-nth-element-from-an-unsubscriptable-iterable中提出的解決方案，但由於效率問題，它完全不適用於他的問題原因。這可能需要幾年時間。 – hivert

你在看什麼在組合算法中被稱爲unrank。考慮按固定順序排列的集合S的元素列表，unrank_S(i)返回列表中的第i個元素，而不計算列表。所以你的S這裏是Perm(n, k)：所有k的列表 - 一組大小爲n的集合。如你所知，這套的尺寸是n!/k!。要做到這一點的方法之一是使用Factoradic numbers

這裏是一個Python unrank算法：

def factorial(n): 
    if n == 0: return 1 
    return n*factorial(n-1) 

def unrank(S, k, i): 
    S = list(S) # make a copy to avoid destroying the list 
    n = len(S) 
    nb = factorial(n) // factorial(n-k) 
    if i >= nb: 
     raise IndexError 
    res = [] 
    while k > 0: 
     nb = nb // n 
     pos = i // nb # the factoradic digits 
     i = i % nb  # the remaining digits 
     res.append(S[pos]) 
     del S[pos] 
     k = k-1 
     n = n-1 
    return res

然後

[unrank(range(5), 2, i) for i in range(20)] 
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3]]

和

unrank(list('ABCDEFGHJKLMNPQRSTUVWXYZ23456789'),6, 128347238)\ 
['G', 'L', 'E', 'H', 'T', 'R']

當然，你可能想使用更好的方法計算階乘，或者甚至將其緩存在預先計算的數組中以避免衝突投它。

來源

2014-02-22 16:45:39 hivert

我沒有太多時間給你完整的解決方案，但下面的想法可以提供一些思路。

你需要找到ň^日排列服用個字符的時間。
讓我們修復第一名字符。然後還剩下25個其他角色。
其餘字符的排列總數爲P = C * 5！。

所以用A作爲第一個字符，你可以有P排列。如果P小於否，則A不能在第一位。

現在保持乙在排列首位，總數至乙在第一個地方是2 * P。

說你拿着ķ^日字符在首位，這樣的排列，直到ķ^{日的總人數}性格都ķ* P，與ķ* P小於ñ，並在保持後K + 1 ^th字符，（K + 1）* P，超過N。所以你需要的字符串需要有K + 1 ^th字符在第一位。

所以你必須找到N-K * P剩餘的排列。剩餘的25個字符和5個地方。所以同樣的問題減少到1個字符少，1個地方更少，更少的排列找到。
因此，以類似的方式解決所有地方。

來源

2014-02-22 16:47:41

計算字母排列的第n個6個字符

回答

相關問題