9

"ABCDEF" のように、任意のイテラブルを指定します。

それを数値システムのように扱うと、次のようになります。

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

このリストでi番目のメンバーを見つけるにはどうすればよいでしょうか? それらすべてを数え上げるのではなく、効率的に。このリストで 10 億番目 (たとえば) のメンバーを見つけたいと思います。私はpythonでこれをやろうとしていて、私はitertoolsにアクセスできないので関連するかもしれない2.4を使用しています(選択ではありません)。

ナイスですが、必須ではありません。疑似「混合基数」システムのソリューションを一般化できますか?

- - 結果 - -

# ------ 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" を 0 桁と見なすと間違っています。

次に大きい 6 の累乗を数字に足し、これらの数字を使用して基数を 6 に変換し、最後に最初の数字 (「B」、つまり「1」) を取り除くと、結果が出ました。

質問は宿題のような匂いがするので、ここに実装ではなくアイデアを投稿したいだけです（私は疑いの利益を与えます;それは私の気持ちです）。

于 2009-07-15T06:32:57.920 に答える
2

最初に、指数を超えるまで 6 の累乗を合計して長さを計算します (または等比級数の公式を使用することをお勧めします)。

インデックスからより小さい累乗の合計を引きます。

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

数値 Base(10) から数値 Base(7) に変換しているため、出力ですべての「0」を回避しながら、元の数値を調整する必要があるため、結果に含まれるたびに 1 ずつスキップします。 「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 に答える
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 に答える
0

perl では、入力 i を base(10) から base("ABCDEF" の長さ) に変換してからtr/012345/ABCDEF/、 と同じ a を実行しy/0-5/A-F/ます。確かに Python にも同様の機能セットがあります。

ああ、 Yarichuが指摘したように、A が 0 を表す場合、先行する A との組み合わせは存在しないため、組み合わせは少し異なります (彼は少し違うと言っていましたが)。問題はもっと些細なことだと思っていたようです。0 に相当する数字を含む数字はシーケンスでスキップされるため、異なる基数を単に音訳することはできません。

つまり、私が提案したのは、実際にはstarblueが提案した最後のステップにすぎません。これは本質的に、Laurence Gonsalvesが実装したものです。ああ、Python には文字変換 ​​(tr//または) 操作がありません。残念です。y//

于 2009-07-15T09:21:09.267 に答える