9

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

将其几乎像数字系统一样对待：

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

我将如何在此列表中找到第 i个成员？有效地，而不是通过所有这些来计算。我想在这个列表中找到第 10 亿个（例如）成员。我正在尝试在 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
4

8 回答 8

5

第三次的魅力：

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
于 2009-07-15T06:32:10.777 回答
5

底部的多基数解决方案。

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))
于 2009-07-15T06:40:49.463 回答
3

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

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

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

于 2009-07-15T06:32:57.920 回答
2

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

从索引中减去较小幂的总和。

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

于 2009-07-15T08:28:58.827 回答
2

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

def f0(x, alph='ABCDE'):
    result = ''
    ct = len(alph)
    while x>=0:
        result += alph[x%ct]
        x /= ct-1
    return result[::-1]
于 2009-07-16T23:29:30.487 回答
1 
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
于 2009-07-15T09:08:38.527 回答
1

由于我们将数字 Base(10) 转换为数字 Base(7)，同时避免输出中的所有“0”，我们将不得不调整原始数字，因此每次结果包含时我们都会跳过一一个“0”。

 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);
}
于 2009-07-15T11:42:32.320 回答
0

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

哦，正如Yarichu所指出的那样，组合有点不同，因为如果 A 代表 0，那么就没有与前导 A 的组合（尽管他说的有点不同）。看来我认为这个问题比它更微不足道。您不能只音译不同的基数，因为包含相当于 0 的数字将在序列中被跳过。

所以我的建议实际上只是starblue建议的最后一步，这本质上是Laurence Gonsalves实现的 ftw。哦，Python中没有音译（tr//或y//）操作，真可惜。

于 2009-07-15T09:21:09.267 回答