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

Question

给定任何可迭代的，例如：“ABCDEF”

将其视为数字系统，如下所示：

A 乙 C D 乙 F AA AB 交流电 广告 AE AF 学士 BB 公元前 .... FF AAA AAB ....

我将如何找到此列表中的第 i^th 成员？ 有效地，而不是通过对所有这些进行计数。 我想找到此列表中的第十亿个（例如）成员。 我正在尝试在 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))

Answer 3

您所做的接近于从基数 10（您的数字）到基数 6 的转换，其中 ABCDEF 是您的数字。 唯一的区别是“AA”和“A”不同，如果您将“A”视为零数字，则这是错误的。

如果您将 6 的下一个更大的幂添加到您的数字中，然后使用这些数字进行基数转换为基数 6，最后去掉第一个数字（应该是“B”，即“1”），您'已经得到结果了。

我只是想在这里发布一个想法，而不是一个实现，因为这个问题对我来说很像家庭作业（我确实相信这一点；这只是我的感觉）。

Answer 4

首先通过对六的幂求和来计算长度，直到超过索引（或者更好地使用几何级数的公式）。

从指数中减去较小幂的总和。

计算以 6 为基数的表示，填充前导零并映射 0 -> A、...、5-> F。

Answer 5

这是有效的（也是我最终决定的），并且认为它值得发布，因为它很整洁。 然而它比大多数答案慢。 我可以在同一操作中执行 % 和 / 吗？

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

Answer 6

alphabet = 'ABCDEF'

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

def excel_column_name_to_idx(name):
  q = len(alphabet)
  x = 0
  for letter in name:
    x *= q
    x += alphabet.index(letter)
  return x+q**len(name)//(q-1)-1

Answer 7

由于我们要从数字 Base(10) 转换为数字 Base(7)，同时避免输出中出现全“0”，因此我们必须调整原始数字，因此我们会跳过每次结果包含“0”时就为 1。

 1 => A,  or 1  in base [0ABCDEF]
 7 => AA, or 8  in base [0ABCDEF]
13 => BA, or 15 in base [0ABCDEF]
42 => FF, or 48 in base [0ABCDEF]
43 =>AAA, or 50 in base [0ABCDEF]

这是一些 Perl 代码，显示了我想要解释的内容
（抱歉，没看到这是一个Python请求）

use strict;
use warnings;
my @Symbols=qw/0 A B C D E F/;
my $BaseSize=@Symbols ;
for my $NR ( 1 .. 45) {
   printf ("Convert %3i => %s\n",$NR ,convert($NR));
}

sub convert {
   my ($nr,$res)=@_;
   return $res unless $nr>0;
   $res="" unless defined($res);
   #Adjust to skip '0'
   $nr=$nr + int(($nr-1)/($BaseSize-1));
   return convert(int($nr/$BaseSize),$Symbols[($nr % ($BaseSize))] . $res);
}

Answer 8

在perl中，您只需将输入i从base(10)转换为base(“ABCDEF”的长度)，然后执行与y相同的tr/012345/ABCDEF/ /0-5/AF/。 当然，Python 也有类似的功能集。

哦，正如 Yarichu 所指出的，这些组合有点不同，因为如果 A 代表 0，那么就不会有与领先A（虽然他说的有点不同）。 看来我认为这个问题比实际情况更微不足道。 您不能只是音译不同的基数，因为包含等价于 0 的数字将是
在序列中被跳过。

所以我的建议实际上只是 starblue 建议的最后一步，本质上就是 劳伦斯·贡萨尔维斯实现了ftw。 哦，Python 中没有音译（tr// 或 y//）操作，真是遗憾。