如何在不迭代的情况下产生第i个组合/置换

Question

给定任何可迭代的,例如:"ABCDEF"

处理它几乎像数字系统一样:

A B C D E F AA AB AC AD AE AF BA BB BC .... FF AAA AAB ....

我将如何在此列表中找到第i ^个成员？有效率,而不是通过所有这些计算.我想在这个列表中找到第十亿个(例如)成员.我正在尝试在python中执行此操作,并且我使用2.4(不是选择)可能是相关的,因为我无法访问itertools.

很好,但不是必需的:可以将解决方案推广到伪"混合基数"系统吗？

---结果---

# ------ paul -----
def f0(x, alph='ABCDE'):
    result = ''
    ct = len(alph)
    while x>=0:
        result += alph[x%ct]
        x /= ct-1
    return result[::-1]

# ----- Glenn Maynard -----
import math
def idx_to_length_and_value(n, length):
    chars = 1
    while True:
        cnt = pow(length, chars)
        if cnt > n:
            return chars, n

        chars += 1
        n -= cnt

def conv_base(chars, n, values):
    ret = []
    for i in range(0, chars):
        c = values[n % len(values)]
        ret.append(c)
        n /= len(values)

    return reversed(ret)

def f1(i, values = "ABCDEF"):
    chars, n = idx_to_length_and_value(i, len(values))
    return "".join(conv_base(chars, n, values))

# -------- Laurence Gonsalves ------
def f2(i, seq):
    seq = tuple(seq)
    n = len(seq)
    max = n # number of perms with 'digits' digits
    digits = 1
    last_max = 0
    while i >= max:
        last_max = max
        max = n * (max + 1)
        digits += 1
    result = ''
    i -= last_max
    while digits:
        digits -= 1
        result = seq[i % n] + result
        i //= n
    return result

# -------- yairchu -------
def f3(x, alphabet = 'ABCDEF'):
    x += 1 # Make us skip "" as a valid word
    group_size = 1
    num_letters = 0
    while 1: #for num_letters in itertools.count():
        if x < group_size:
            break
        x -= group_size
        group_size *= len(alphabet)
        num_letters +=1
    letters = []
    for i in range(num_letters):
        x, m = divmod(x, len(alphabet))
        letters.append(alphabet[m])
    return ''.join(reversed(letters))

# ----- testing ----
import time
import random
tries = [random.randint(1,1000000000000) for i in range(10000)]
numbs = 'ABCDEF'

time0 = time.time()
s0 = [f1(i, numbs) for i in tries]
print 's0 paul',time.time()-time0, 'sec'
time0 = time.time()
s1 = [f1(i, numbs) for i in tries]
print 's1 Glenn Maynard',time.time()-time0, 'sec'
time0 = time.time()
s2 = [f2(i, numbs) for i in tries]
print 's2 Laurence Gonsalves',time.time()-time0, 'sec'
time0 = time.time()
s3 = [f3(i,numbs) for i in tries]
print 's3 yairchu',time.time()-time0, 'sec'

时间:

s0 paul 0.470999956131 sec
s1 Glenn Maynard 0.472999811172 sec
s2 Laurence Gonsalves 0.259000062943 sec
s3 yairchu 0.325000047684 sec
>>> s0==s1==s2==s3
True

Answer 1

第三次的魅力:

def perm(i, seq):
  seq = tuple(seq)
  n = len(seq)
  max = n # number of perms with 'digits' digits
  digits = 1
  last_max = 0
  while i >= max:
    last_max = max
    max = n * (max + 1)
    digits += 1
  result = ''
  i -= last_max
  while digits:
    digits -= 1
    result = seq[i % n] + result
    i //= n
  return result

Answer 2

底部的多基础解决方案.

import math
def idx_to_length_and_value(n, length):
    chars = 1
    while True:
        cnt = pow(length, chars)
        if cnt > n:
            return chars, n

        chars += 1
        n -= cnt

def conv_base(chars, n, values):
    ret = []
    for i in range(0, chars):
        c = values[n % len(values)]
        ret.append(c)
        n /= len(values)

    return reversed(ret)

values = "ABCDEF"
for i in range(0, 100):
    chars, n = idx_to_length_and_value(i, len(values))
    print "".join(conv_base(chars, n, values))

import math
def get_max_value_for_digits(digits_list):
    max_vals = []

    for val in digits_list:
        val = len(val)
        if max_vals:
            val *= max_vals[-1]
        max_vals.append(val)
    return max_vals

def idx_to_length_and_value(n, digits_list):
    chars = 1
    max_vals = get_max_value_for_digits(digits_list)

    while True:
        if chars-1 >= len(max_vals):
            raise OverflowError, "number not representable"
        max_val = max_vals[chars-1]
        if n < max_val:
            return chars, n

        chars += 1
        n -= max_val

def conv_base(chars, n, digits_list):
    ret = []
    for i in range(chars-1, -1, -1):
        digits = digits_list[i]
        radix = len(digits)

        c = digits[n % len(digits)]
        ret.append(c)
        n /= radix

    return reversed(ret)

digits_list = ["ABCDEF", "ABC", "AB"]
for i in range(0, 120):
    chars, n = idx_to_length_and_value(i, digits_list)
    print "".join(conv_base(chars, n, digits_list))