Как получить <i> -й элемент <n> -й перестановки последовательности напрямую (без какой-либо рекурсии)?

Вы можете найти n-ю перестановку, повторяя евклидово деление (частное и остаток, иначе divmod) и отслеживая, какие буквы вы выбираете. Затем вы можете выбрать i-ю букву из этой перестановки.

Пусть S будет копией начальной строки, L - длиной этой строки, а P - количеством перестановок (L!). T будет n-й перестановкой S, построенной шаг за шагом. Пример: S = "ABCD", L = 4 и P = 24. Для примера возьмем n = 15. T в конце должен быть "CBDA".

Установите P = P/L. Вычислите divmod(n, P), пусть q будет частным (n/P), а r остатком (n%P). Удалите q-ю букву из S и добавьте ее в T. Установить n = r, уменьшить L и повторять до L = 0.
Пример:
1) P = 24/4 = 6, q = 15/6 = 2, r = 15%6 = 3, S = "ABD", T = "C", n = r = 3, L = 3.
2) P = 6/3 = 2, q = 3/2 = 1, r = 3%2 = 1, S = "AD", T = "CB", n = r = 1, L = 2.
3) P = 2/2 = 1, q = 1/1 = 1, r = 1%1 = 0, S = "A", T = "CBD", n = r = 0, L = 1.
4) P = 1/1 = 1, q = 0/1 = 0, r = 0%1 = 0, S = "", T = "CBDA", n = r = 0, L = 0.

Поскольку вам нужна только буква i, вы можете остановиться, когда длина T равна i+1, и взять эту последнюю букву.

Я не буду пытаться кодировать это на Python, потому что прошло слишком много времени с тех пор, как я прикасался к Python, но вот демонстрация на C++.

Простите за мой Python. Идея в том, что буква в каждой позиции повторяет (number_of_pos - pos)! раз.

Например. ABCD, буква в первой позиции будет повторять 3! раз. Итак, разделив n на этот факториал, мы теперь, какая буква стоит на первой позиции. Чтобы найти букву во второй позиции, нам нужно удалить эту букву из набора (вместо этого назначить 0) и обновить n с помощью n - n % 3!, чтобы теперь индекс буквы во второй позиции. Применяя этот индекс, мы должны позаботиться о том, чтобы не считать буквы, стоящие на первой позиции.

Сложность - O(kPosCount * kPosCount).

#include <array>
#include <iostream>

const int kPosCount = 4;
const std::array<int, kPosCount> factorial = { 1,1,2,6 };
const std::array<int, kPosCount> kLetters = { 'A', 'B', 'C', 'D' };

char f(int pos, int n) {
    assert(pos < kPosCount);
    std::array<int, kPosCount> letters = kLetters;

    int res = 0;
    for (int i = 0; i <= pos; ++i) {
        const int letter = n / factorial[kPosCount - i - 1];
        int j = 0;
        for (int stillThere = 0; j < kPosCount; ++j) {
            if (letters[j] != 0) {
                if (stillThere == letter) {
                    break;
                }
                ++stillThere;
            }
        }
        letters[j] = 0;
        res = j;
        n %= factorial[kPosCount - i - 1];
    }
    return kLetters[res];
}

int main() {
    const int kMaxN = factorial.back() * kPosCount;
    for (int i = 0; i < kPosCount; ++i) {
        for (int j = 0; j < kMaxN; ++j) {
            std::cout << f(i, j) << " ";
        }
        std::cout << std::endl;
    }
}

Вот версия вашей функции с другим порядком перестановки. Я не устанавливал здесь размер перестановки 256, поэтому вы должны указать его в качестве первого аргумента.

def elt(n,k,i):
  """Returns element i of permutation k from permutations of length n"""
  perm = [*range(n)]
  for j in range(i+1):
    k, r = divmod(k, n-j)
    perm[j], perm[j+r] = perm[j+r], perm[j]
  return perm[i]

Это имеет два отличия от вашего кода.

Во-первых, цифры вырезаются из индекса справа налево, что означает, что все модули bignum divmods являются модулями divmods с небольшим делимым. Я думал, что это будет быстрее, чем использование больших дивидендов, но оказалось, что это значительно медленнее. Однако он позволяет избежать предварительного вычисления факториалов.

Во-вторых, вместо того, чтобы выполнять серию pop из середины таблицы, которая будет иметь квадратичную сложность, потому что операция pop - O (n), я просто меняю местами каждый элемент с некоторым прямым элементом. Это значительно быстрее, хотя большая арифметика доминирует в вычислениях.

Фактически, elt(n,k,i) выполняет первые шаги i в тасовке Фишера-Йетса range(n), используя разложение k по смешанной основе в качестве случайных значений при случайном тасовании. Поскольку перетасовка F-Y дает разные результаты для каждой возможной последовательности случайных значений, а разложение k на смешанное основание дает разную последовательность для каждого другого значения k, будут сгенерированы все перестановки.

Вот как выглядит порядок для n = 4:

>>> print('\n'.join(' '.join(str(elt(4, k, i)) for i in range(4))
                    for k in range(factorial(4))))
0 1 2 3
1 0 2 3
2 1 0 3
3 1 2 0
0 2 1 3
1 2 0 3
2 0 1 3
3 2 1 0
0 3 2 1
1 3 2 0
2 3 0 1
3 0 2 1
0 1 3 2
1 0 3 2
2 1 3 0
3 1 0 2
0 2 3 1
1 2 3 0
2 0 3 1
3 2 0 1
0 3 1 2
1 3 0 2
2 3 1 0
3 0 1 2

Чтобы действительно ускорить работу функции, я повторно ввел предварительно вычисленные факториалы (как локальную переменную, которая расширяется по мере необходимости). Я также микрооптимизировал внутренний цикл, удалив как можно больше арифметических операций, что означало выполнение перетасовки F-Y сзади вперед. Это приводит к еще одному порядку перестановки; см. ниже пример.

Окончательная оптимизированная функция примерно на 15% быстрее, чем версия, о которой идет речь (то есть на выполнение простого теста требуется около 85% времени).

def elt_opt(n, k, i, fact=[1]):
    """Returns element i of permutation k from permutations of length n.
       Let the last argument default.
    """
    while len(fact) < n: fact.append(fact[-1]*len(fact))
    perm = list(range(n))
    for j in range(n-1, n-2-i, -1):
        r, k = divmod(k, fact[j])
        perm[j], perm[r] = perm[r], perm[j]
    return perm[n-i-1]

Порядок перестановки:

>>> print('\n'.join(' '.join(str(elt_opt(4, k, i)) for i in range(4))
                    for k in range(factorial(4))))
0 3 2 1
0 3 1 2
0 1 3 2
0 1 2 3
0 2 3 1
0 2 1 3
1 0 2 3
1 0 3 2
1 3 0 2
1 3 2 0
1 2 0 3
1 2 3 0
2 0 3 1
2 0 1 3
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 2 1
3 0 1 2
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0