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

Question

Допустим, у нас есть строка «ABCD», и мы хотим извлечь букву в i-й позиции из n-й перестановки строки.

В этом примере я знаю, что есть факториал(4) = 24 перестановки, и список можно легко найти с помощью itertools.permutations, что даст следующее:

['ABCD', 'ABDC', 'ACBD', 'ACDB', 'ADBC ',' ADCB ',' BACD ',' BADC ',' BCAD ',' BCDA ',' BDAC ',' BDCA ',' CABD ',' CADB ',' CBAD ',' CBDA ',' CDAB ', 'CDBA', 'DABC', 'DACB', 'DBAC', 'DBCA', 'DCAB', 'DCBA']

Поэтому функция f, которую я ищу, должна вернуть:

f (0, n) == ['A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B ',' B ',' B ',' B ',' C ',' C ',' C ',' C ',' C ',' C ',' D ',' D ',' D ', 'D', 'D', 'D'] [n]

f (1, n) == ['B', 'B', 'C', 'C', 'D', «D», «A», «A», «C», «C», «D», «D», «A», «A», «B», «B», «D», «D ',' A ',' A ',' B ',' B ',' C ',' C '] [n]

f (2, n) == [' C ','D ',' B ',' D ',' B ',' C ',' C ',' D ',' A ',' D ',' A ',' C ',' B ',' D ', 'A', 'D', 'A', 'B', 'B','C', 'A', 'C', 'A', 'B'] [n]

f (3, n) == ['D', 'C', 'D',«B», «C», «B», «D», «C», «D», «A», «C», «A», «D», «B», «D», «A',' B ',' A ',' C ',' B ',' C ',' A ',' B ',' A '] [n]

Это довольно легко дляi == 0, у нас есть f (0, n) == "ABCD" [n // 6], но поиск шаблона при увеличении i становится все более и более сложным.

Мне все равнокак перестановки упорядочены, так что может быть легко найти общий шаблон для каждого значения i ...

Я планирую использовать это с набором из 256 элементов и факториальной (256) перестановок, поэтому вычислениеперестановки - не вариант.

Редактировать: у меня уже есть функция для этого, но она слишком медленная, и мне было интересно, можно ли найти какой-нибудь эквивалентный результат с помощью простой формулы, использующей, например, побитовые операции ...

Edit-2: вот лучшее из существующих на данный момент решение благодаря @rici:

f = [factorial(i) for i in range(256)]

def _getElt(k, i):
    """
    Returns the <i>th element of the <k>th permutation of 0..255
    """
    table = list(range(256))

    for j in range(255, 254-i, -1):
        r, k = divmod(k, f[j])
        perm[j], perm[r] = perm[r], perm[j] 
    return perm[255 - i]

Edit-3: вот еще один подход, использующий полиномиальные аппроксимации для воссоздания перестановок, поэтомудругой формулировкой проблемы может быть «как воссоздать i-й коэффициент многочлена для n-й перестановки?».

Это список из n, перестановка, коэффициент многочлена (и, наконец, перестановка, перестроенная изкоэффициенты полинома) для N = 4:

0 [0, 1, 2, 3] [Дробь (0, 1), Дробь (1, 1), Дробь (0, 1),Фракция (0, 1)] [0, 1, 2, 3]

1 [0, 1, 3, 2] [Фракция (0, 1), Фракция (-3, 4), Фракция (5, 2), фракция (-2, 3)] [0, 1, 3, 2]

2 [0, 2, 1, 3] [фракция (0, 1), фракция (11,2), фракция (-9, 2), фракция (1, 1)] [0, 2, 1, 3]

3 [0, 2, 3, 1] [фракция (0, 1)Фракция (7, 4), Фракция (1, 2), Фракция (-1, 3)] [0, 2, 3, 1]

4 [0, 3, 1, 2] [Фракция(0, 1), фракция (33, 4), фракция (-13, 2), фракция (4, 3)] [0, 3, 1, 2]

5 [0, 3, 2, 1] [Фракция (0, 1), Фракция (19, 3), Фракция (-4, 1), Фракция (2, 3)] [0, 3, 2, 1]

6 [1, 0, 2, 3] [Фракция (1, 1), Фракция (-15, 4), Фракция (7,2), фракция (-2, 3)] [1, 0, 2, 3]

7 [1, 0, 3, 2] [фракция (1, 1), фракция (-17, 3), Фракция (6, 1), фракция (-4, 3)] [1, 0, 3, 2]

8 [1, 2, 0, 3] [фракция (1, 1),Фракция (21, 4), Фракция (-11, 2), Фракция (4, 3)] [1, 2, 0, 3]

9 [1, 2, 3, 0] [Фракция (1, 1), фракция (-1, 3), фракция (2, 1), фракция (-2, 3)] [1, 2, 3, 0]

10 [1, 3, 0, 2] [Фракция (1, 1), Фракция (31, 4), Фракция (-15, 2), Фракция (5, 3)] [1, 3, 0, 2]

11 [1, 3, 2, 0] [Фракция (1, 1), Фракция (17, 4), Фракция (-5, 2), Фракция (1, 3)] [1, 3, 2, 0]

12 [2, 0, 1, 3] [Фракция (2, 1), Фракция (-17, 4), Фракция (5, 2), Фракция (-1, 3)] [2, 0, 1, 3]

13 [2, 0, 3, 1] [Фракция (2, 1), Фракция (-31, 4), Фракция (15, 2), Фракция (-5, 3)][2, 0, 3, 1]

14 [2, 1, 0, 3] [Фракция (2, 1), Фракция (1, 3), Фракция (-2, 1), Фракция (2, 3)] [2, 1, 0, 3]

15 [2, 1, 3, 0] [Фракция (2, 1), Фракция (-21, 4), Фракция (11, 2), Фракция (-4, 3)] [2, 1, 3 , 0]

16 [2, 3, 0, 1] [Фракция (2, 1), Фракция (17, 3), Фракция (-6, 1), Фракция (4, 3)] [2, 3, 0, 1]

17 [2, 3, 1, 0] [Фракция (2, 1), Фракция (15, 4), Фракция (-7, 2), Фракция (2, 3)] [2, 3, 1, 0]

18 [3, 0, 1, 2] [Фракция (3, 1), Фракция (-19, 3), Фракция (4, 1), Фракция (-2, 3)] [3, 0, 1 , 2]

19 [3, 0, 2, 1] [Фракция (3, 1), Фракция (-33, 4), Фракция (13, 2), Фракция (-4, 3)] [3, 0, 2 , 1]

20 [3, 1, 0, 2] [Фракция (3, 1), Фракция (-7, 4), Фракция (-1, 2), Фракция (1, 3)] [3, 1, 0 , 2]

21 [3, 1, 2, 0] [Фракция (3, 1), Фракция (-11, 2), Фракция (9, 2), Фракция (-1, 1)] [3, 1, 2 , 0]

22 [3, 2, 0, 1] [Фракция (3, 1), Фракция (3, 4), Фракция (-5, 2), Фракция (2, 3)] [3, 2, 0, 1]

23 [3, 2, 1, 0] [Фракция (3, 1), Фракция (-1, 1), Фракция (0, 1), Фракция (0, 1)] [3, 2, 1, 0]

Мы ясно видим, что существует симметрия: coefs [i] = [3 - coefs [23-i] [0]] + [-c для c в coefs [23-i] [1:]], поэтому это способ исследовать, но я понятия не имею, что это возможно.

Answer 1

Извините, за мой Питон.Идея состоит в том, что буква в каждой позиции повторяется (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;
    }
}

Answer 2

Вот версия вашей функции с другим порядком перестановки.Размер перестановки здесь не был равен 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 небольшим дивидендом.Я думал, что это будет быстрее, чем использование bignum дивидендов, но оказывается значительно медленнее.Тем не менее, это позволяет избежать необходимости предварительно вычислять факториалы.

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

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

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

Окончательная оптимизированная функция примерно на 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

Answer 3

Вы можете найти 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 ++ .