CODEWITHSUNDEEP
pythoncombinationspermutationdynamic-programming
Vanthewilderperson
Vanthewilderperson

Reputation: 35

finding nth combination (incremental approach) of letters (list)

What is the Pythonic way of finding the nth combination given a list of alphabets?

# a = list("abc")

Expected output (compinations):

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

Upvotes: 2

Views: 1000

Answers (4)

Blckknght
Blckknght

Reputation: 104792

As user2357112 commented on gnibbler's answer, what you want to use is a bijective number system, where the characters in your alphabet are the digits.

Here's how you can do this in code:

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)

This should work efficiently even for very large numbers or long alphabets. Its running time is proportional to the length of the output string, or the log of the integer in a base equal to the length of the alphabet.

Here's an example run:

>>> 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

Upvotes: 1

alko
alko

Reputation: 48357

With itertools, generating all the combinations along the line:

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

Demo:

>>> 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']

Update

AFAIK, @gnibbler approach won't work, as do not distinguish between 001 and 1 and similar combinations. Here is a faster way to get only n'th combination :

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])

Demo:

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

Upvotes: 4

John La Rooy
John La Rooy

Reputation: 304393

Your examples are base3 numbers.

convert n to base3 (or whatever the length of the alphabet). Then replace the "digits" with the symbols from your alphabet.

This allows you find the nth value without generating all the previous n-1 entries

Upvotes: 4

NPE
NPE

Reputation: 500773

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

(This requires Python 2.7, but can be easily rewritten for earlier versions of itertools.)

Upvotes: 1

Related Questions