找到字母（列表）的第n個組合（增量法）

給出字母列表找到第n個組合的Python方法是什麼？找到字母（列表）的第n個組合（增量法）

# a = list("abc")

預期輸出（compinations）：

# a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, and so on... (until the nth)

來源

2013-12-07 Vanthewilderperson

你所說的「第n」是什麼意思？你看過itertools powerset配方嗎？ – mgilson

我保留所有組合的數量，所以當我有所需數量的組合時，我會終止循環 – Vanthewilderperson

powerset的問題在於它在（'a'，'b'，'c'）之後中斷但我確實想在（'a'，'b'，'c'）之後繼續到（'a'，'a'，'a'，'a'）等等 – Vanthewilderperson

隨着itertools，生成所有組合沿線：

def powerprod(iterable): 
    s = list(iterable) 
    for r in itertools.count(1): 
     for c in itertools.product(s, repeat=r): 
      yield c

演示：

>>> map(''.join, itertools.islice(powerprod('eht'), 34)) 
['e', 'h', 't', 'ee', 'eh', 'et', 'he', 'hh', 'ht', 'te', 'th', 'tt', 'eee', 'eeh', 'eet', 'ehe', 'ehh', 'eht', 'ete', 'eth', 'ett', 'hee', 'heh', 'het', 'hhe', 'hhh', 'hht', 'hte', 'hth', 'htt', 'tee', 'teh', 'tet', 'the']

更新

AFAIK，@gnibbler方法將不起作用，因爲不區分001和1以及類似的組合。這裏有一個更快的方式得到的只有第n個組合：

from itertools import product, islice 

def max_sum_n_pow_lower_x(x, n): 
    """ returns tuple of number of summand and maximal sum 
     of form `n` + `n`**2 + `n`**3 not greater than `x` """ 
    i, c, s = 1, 0, 0 
    while s < x: 
     i *= n 
     c += 1 
     s += i 
    return c-1, s-i 

def get_nth_pow(iterable, n): 
    l = list(iterable) 
    repeat, start_from = max_sum_n_pow_lower_x(n, len(l)) 
    prod = itertools.product(l, repeat=repeat+1) 
    return ''.join(list(islice(prod, n-start_from))[-1])

演示：

>>> get_nth_pow('eht', 34) 
'the'

來源

2013-12-07 19:50:38 alko

除了'產品'以外，一旦你有了幾何級數的總和，你可以從'n'中減去它，然後*然後*可以使用基本擴展。 – DSM

@DSM可能是的，我想過了。但我現在有點累了:) – alko

它也可以處理max int的「4125383079316」嗎？似乎引發了一個錯誤 – Vanthewilderperson

import itertools 

def gen_combinations(alphabet): 
    n = 1 
    while True: 
    for item in itertools.combinations_with_replacement(alphabet, n): 
     yield ''.join(item) 
    n += 1 

print list(itertools.islice(gen_combinations("abc"), 20))

（這需要Python 2.7，但可以很容易地改寫爲早期版本itertools的。）

來源

2013-12-07 19:49:58 NPE

不會生成正確的組合，對於「eht」和n = 34，最後一個組合應該是「the」，這不匹配 – Vanthewilderperson

你的例子是base3號。

將n轉換爲base3（或任何字母的長度）。然後用您的字母表中的符號替換「數字」。

這可以讓你找到的第n個值，而不會產生以前所有的N-1項

來源

2013-12-07 19:50:09

我該怎麼做 - 實施留給讀者？：p –

這是一個非常聰明的方法。榮譽。我喜歡。 – mgilson

這些不是基數3的數字。它們是[*雙射*基3]（http：//en.wikipedia。org/wiki/Bijective_numeration），因爲012與12不同。 – user2357112

由於user2357112評論gnibbler的答案，你想用什麼是bijective number system，其中的人物在你的字母表是數字。

這裏是你如何可以在代碼中做到這一點：

import math 

def get_bijective_val(n, alphabet): 
    base = len(alphabet) 
    digits = [] 
    while n: 
     remainder = math.ceil(n/base)-1 
     digits.append(n - remainder*base) 
     n = remainder 
    digits.reverse() 
    return "".join(alphabet[digit-1] for digit in digits)

這應該即使是非常大的數字或字母長的工作效率。它的運行時間與輸出字符串的長度成正比，或者基數中的整數的長度等於字母表的長度。

下面是一個例子來看：

>>> for i in range(40): 
    print(i, get_bijective_val(i, "eht")) 


0 
1 e 
2 h 
3 t 
4 ee 
5 eh 
6 et 
7 he 
8 hh 
9 ht 
10 te 
11 th 
12 tt 
13 eee 
14 eeh 
15 eet 
16 ehe 
17 ehh 
18 eht 
19 ete 
20 eth 
21 ett 
22 hee 
23 heh 
24 het 
25 hhe 
26 hhh 
27 hht 
28 hte 
29 hth 
30 htt 
31 tee 
32 teh 
33 tet 
34 the 
35 thh 
36 tht 
37 tte 
38 tth 
39 ttt

來源

2013-12-07 21:06:11 Blckknght

找到字母（列表）的第n個組合（增量法）

回答

相關問題