Как произвести i-th комбинацию/перестановку без итерации

First compute the length by summing up powers of six until you exceed your index (or better use the formula for the geometric series).

Subtract the sum of smaller powers from the index.

Compute the representation to base 6, fill leading zeros and map 0 -> A, ..., 5 -> F.

Решение с множеством оснований внизу.

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

То, что вы делаете, похоже на преобразование из базы 10 (ваше число) в базу 6, с ABCDEF - ваши цифры. Единственная разница в том, что «AA» и «A» различны, что неверно, если вы считаете «A» нулевой цифрой.

Если вы добавляете следующую большую степень шести к вашему числу, а затем выполняете базовое преобразование основать 6 с использованием этих цифр и, наконец, удалить первую цифру (которая должна быть «B», то есть «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

В Perl вам нужно просто преобразовать введенный вами i из base (10) в base (длина «ABCDEF»), а затем выполнить tr / 012345 / ABCDEF / который совпадает с y / 0-5 / AF / . Конечно, у Python есть аналогичный набор функций.

О, как указал Яричу , комбинации немного отличаются, потому что если бы A представляло 0, то не было бы комбинаций с ведущим A (хотя он сказал это немного другое). Кажется, я думал, что проблема более тривиальна, чем она есть на самом деле. Вы не можете просто транслитерировать разные базовые числа, потому что числа, содержащие эквивалент 0, будут пропущено в последовательности.

Таким образом, то, что я предложил, на самом деле является только последним шагом из того, что предлагал starblue , что по сути является тем, что Лоуренс Гонсалвес реализовал ftw. Да, и в Python нет операции транслитерации ( tr // или y // ), какой позор.

Это работает (и это то, на чем я наконец остановился), и подумал, что стоит опубликовать, потому что он аккуратный. Однако это медленнее, чем большинство ответов. Могу ли я выполнить% и / в той же операции?

def f0(x, alph='ABCDE'):
    result = ''
    ct = len(alph)
    while x>=0:
        result += alph[x%ct]
        x /= ct-1
    return result[::-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);
}