Ранжирование и расстановка перестановок с дубликатами

Question

Я читаю о перестановках, и мне интересны методы ранжирования / отмены разметки.

Из реферата статьи:

Функция ранжирования для перестановок по nСимволам присваивается уникальное целое число в диапазоне [0, n!- 1] каждому из n!Перестановки.Соответствующая функция unranking является обратной: задано целое число от 0 до n!- 1, значение функции - это перестановка, имеющая этот ранг.

Я сделал ранжирование и отменил функцию в C ++, используя next_permutation.Но это не практично для n> 8.Я ищу более быстрый метод, и factoradics кажутся довольно популярными.Но я не уверен, что это также работает с дубликатами.Так, что было бы хорошим способом ранжировать / отменять перестановки с дубликатами?

Answer 1

Для больших n-s вам нужна библиотека произвольной точности, например GMP .

это мой предыдущий пост о функции unranking, написанной на python, я думаю, что она читаема, почти как псевдокод, в комментариях также есть объяснение: Приведен список элементов в лексикографическом порядке (т. Е. [' a ',' b ',' c ',' d ']), найдите n-ю перестановку - среднее время для решения?

исходя из этого, вы должны быть в состоянии выяснить функцию ранжирования, это в основном та же логика;)

Answer 2

Я напишу половину вашего вопроса в этом ответе - «unranking». Цель состоит в том, чтобы найти лексикографически K-ю перестановку упорядоченной строки [abcd ...].

Для этого нам нужно понять факториальную систему счисления (factoradics). Факторная система счисления использует факторные значения вместо степеней чисел (двоичная система использует степени 2, десятичная дробь использует степени 10) для обозначения значений места (или базы).

Значения мест (базовые) -

5!= 120    4!= 24    3!=6    2!= 2    1!=1    0!=1 etc..

Цифра в нулевом месте всегда равна 0. Цифра на первом месте (с основанием = 1!) Может быть 0 или 1. Цифра на втором месте (с основанием 2!) Может быть 0,1 или 2 и так далее. Вообще говоря, цифра на n-м месте может принимать любое значение от 0 до n.

Первые несколько чисел, представленные как факторадика-

0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200

Существует прямая связь между n-й лексикографической перестановкой строки и ее факторическим представлением.

Например, вот перестановки строки «abcd».

0  abcd       6  bacd        12  cabd       18  dabc
1  abdc       7  badc        13  cadb       19  dacb
2  acbd       8  bcad        14  cbad       20  dbac
3  acdb       9  bcda        15  cbda       21  dbca
4  adbc       10  bdac       16  cdab       22  dcab
5  adcb       11  bdca       17  cdba       23  dcba

Мы можем увидеть образец здесь, если внимательно наблюдать. Первая буква меняется после каждой 6-й (3!) Перестановки. Вторая буква меняется после 2 (2!) Перестановок. Третья буква меняется после каждой (1!) Перестановки, а четвертая буква меняется после каждой (0!) Перестановки. Мы можем использовать это соотношение для непосредственного нахождения n-й перестановки.

Как только мы представляем n в фактическом представлении, мы рассматриваем каждую цифру в нем и добавляем символ из данной строки в вывод. Если нам нужно найти 14-ю перестановку «abcd». 14 в факторе -> 2100.

Начните с первой цифры -> 2, строка - это «abcd». Предполагая, что индекс начинается с 0, возьмите элемент в позиции 2 из строки и добавьте его в вывод.

Output                    String
  c                         abd
  2                         012

Следующая цифра -> 1.Строка теперь «abd». Снова вставьте символ в позицию 1 и добавьте его в вывод.

Output                    String
 cb                         ad
 21                         01

Следующая цифра -> 0. Строка «ad». Добавьте символ в позицию 1 к выводу.

Output                   String
 cba                        d
 210                        0

Следующая цифра -> 0. Строка - «d». Добавьте символ в позиции 0 к выводу.

Выходная строка cbad '' 2100

Чтобы преобразовать данное число в Факториальную систему счисления, последовательно делите число на 1,2,3,4,5 и так далее, пока частное не станет равным нулю. Напоминания на каждом этапе образуют фактическое представление.

Например, для перевода 349 в факторический,

              Quotient        Reminder       Factorial Representation
349/1            349               0                             0
349/2            174               1                            10
174/3            58                0                           010
58/4             14                2                          2010
14/5             2                 4                         42010
2/6              0                 2                        242010

Факторное представление 349 - 242010.

Answer 3

Один из способов - ранжировать и отменять выбор индексов по определенной группе равных чисел, например,

def choose(n, k):
    c = 1
    for f in xrange(1, k + 1):
        c = (c * (n - f + 1)) // f
    return c

def rank_choice(S):
    k = len(S)
    r = 0
    j = k - 1
    for n in S:
        for i in xrange(j, n):
            r += choose(i, j)
        j -= 1
    return r

def unrank_choice(k, r):
    S = []
    for j in xrange(k - 1, -1, -1):
        n = j
        while r >= choose(n, j):
            r -= choose(n, j)
            n += 1
        S.append(n)
    return S

def rank_perm(P):
    P = list(P)
    r = 0
    for n in xrange(max(P), -1, -1):
        S = []
        for i, p in enumerate(P):
            if p == n:
                S.append(i)
        S.reverse()
        for i in S:
            del P[i]
        r *= choose(len(P) + len(S), len(S))
        r += rank_choice(S)
    return r

def unrank_perm(M, r):
    P = []
    for n, m in enumerate(M):
        S = unrank_choice(m, r % choose(len(P) + m, m))
        r //= choose(len(P) + m, m)
        S.reverse()
        for i in S:
            P.insert(i, n)
    return tuple(P)

if __name__ == '__main__':
    for i in xrange(60):
        print rank_perm(unrank_perm([2, 3, 1], i))

Answer 4

Java, от https://github.com/timtiemens/permute/blob/master/src/main/java/permute/PermuteUtil.java (мой публичный домен, минус проверка ошибок):

public class PermuteUtil {
 public <T> List<T> nthPermutation(List<T> original, final BigInteger permutationNumber)  {
        final int size = original.size();

        // the return list:
        List<T> ret = new ArrayList<>();
        // local mutable copy of the original list:
        List<T> numbers = new ArrayList<>(original);

        // Our input permutationNumber is [1,N!], but array indexes are [0,N!-1], so subtract one:
        BigInteger permNum = permutationNumber.subtract(BigInteger.ONE);

        for (int i = 1; i <= size; i++) {
            BigInteger factorialNminusI = factorial(size - i);

            // casting to integer is ok here, because even though permNum _could_ be big,
            //   the factorialNminusI is _always_ big
            int j = permNum.divide(factorialNminusI).intValue();

            permNum = permNum.mod(factorialNminusI);

            // remove item at index j, and put it in the return list at the end
            T item = numbers.remove(j);
            ret.add(item);
        }

        return ret;
  }
}