Алгоритм нахождения числовой перестановки по заданному лексикографическому индексу

Question

Я ищу алгоритм, который с учетом набора чисел (например, 1 2 3) и индекса (например, 2) даст мне вторую перестановку этих чисел согласно лексикографическому порядку.Например, в этом случае алгоритм вернет 1 3 2.

Answer 1

Вот пример решения в Scala, которое я подробно объясню:

/**
    example: index:=15, list:=(1, 2, 3, 4)
*/ 
def permutationIndex (index: Int, list: List [Int]) : List [Int] = 
  if (list.isEmpty) list else {
    val len = list.size     // len = 4
    val max = fac (len)     // max = 24
    val divisor = max / len // divisor = 6
    val i = index / divisor // i = 2
    val el = list (i)
    el :: permutationIndex (index - divisor * i, list.filter (_ != el)) }

Поскольку Scala не так хорошо известна, я думаю, что мне нужно объяснить последнюю строку алгоритма, котораякроме того, довольно самоочевиден.

    el :: elist

создает новый список из элемента el и списка elist.Элист это рекурсивный вызов.

    list.filter (_ != el)

- это просто список без элемента el.

Проверьте это исчерпывающе с небольшим списком:

(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n")

Проверьте скорость большего списка с 2 примерами:

scala> permutationIndex (123456789, (1 to 12).toList) 
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3)

scala> permutationIndex (123456790, (1 to 12).toList) 
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6)

Результат появляется сразу на 5лет ноутбукСуществует 479 001 600 перестановок для Списка из 12 элементов, но с 100 или 1000 элементами это решение все равно должно работать быстро - вам просто нужно будет использовать BigInt в качестве индекса.

Как это работает?Я сделал графическое изображение, для визуализации примера, список (1, 2, 3, 4) и индекс 15:

Список из 4 элементов производит 4!перестановки (= 24).Мы выбираем произвольный индекс от 0 до 4! -1, скажем, 15.

Мы можем визуализировать все перестановки в дереве с первым узлом из 1..4.Мы делим 4!на 4 и видим, что каждый первый узел ведет к 6 поддеревьям.Если мы разделим наш индекс 15 на 6, результат будет 2, а значение в нашем нулевом списке с индексом 2 равно 3. Итак, первый узел - 3, а остальная часть нашего списка - (1, 2, 4),Вот таблица, показывающая, как 15 приводит к элементу с индексом 2 в массиве / списке / что угодно:

0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23
     0      |     1    |         2         |     3
            |          | 0  1  2  3  4  5  |

Теперь мы вычтем 12, первый элемент ячейки (12 ... 17)для последних 3 элементов, которые имеют 6 возможных перестановок, и посмотрите, как 15 отображается на 3. Число 3 теперь ведет к индексу массива 1, который был элементом 2, поэтому результат пока равен List (3, 2, ...).

                        | 0 1 | 2 3 | 4 5 |
                        |  0  |  1  |  3  |
                              | 0 1 |

Опять же, мы вычитаем 2 и заканчиваем двумя оставшимися элементами с 2 перестановками и индексом (0, 3), сопоставляя значения (1, 4).Мы видим, что второй элемент, принадлежащий 15 сверху, соответствует значению 3, а оставшийся элемент для последнего шага - другой:

                             | 0 | 1 |
                             | 0 | 3 |
                             | 3 | 0 |

Наш результат - List (3, 2, 4, 1) или индексы (2, 1, 3, 0).Проверка всех индексов по порядку показывает, что они дают все перестановки по порядку.

Answer 2

Вот простое решение:

from math import factorial # python math library

i = 5               # i is the lexicographic index (counting starts from 0)
n = 3               # n is the length of the permutation
p = range(1, n + 1) # p is a list from 1 to n

for k in range(1, n + 1): # k goes from 1 to n
    f = factorial(n - k)  # compute factorial once per iteration
    d = i // f            # use integer division (like division + floor)
    print(p[d]),          # print permuted number with trailing space
    p.remove(p[d])        # delete p[d] from p
    i = i % f             # reduce i to its remainder

Выход:

3 2 1

Сложность по времени составляет O (n ^ 2), если p является списком, и O (n) амортизируется, если p является хеш-таблицей и factorial предварительно вычислено.

Answer 3

Ссылка на упомянутую статью: http://penguin.ewu.edu/~trolfe/#Shuffle

/* Converting permutation index into a permutation
 * From code accompanying "Algorithm Alley: Randomized Shuffling",
 * Dr. Dobb’s Journal, Vol. 25, No. 1  (January 2000)
 * http://penguin.ewu.edu/~trolfe/#Shuffle
 *
 * Author:  Tim Rolfe
 *          RolfeT@earthlink.net
 *          http://penguin.ewu.edu/~trolfe/
 */
#include <stdio.h>
#include <stdlib.h>

// /5843030/algoritm-nahozhdeniya-chislovoi-perestanovki-po-zadannomu-leksikograficheskomu-indeksu

// Invert the permutation index --- generate what would be
// the subscripts in the N-dimensional array with dimensions
// [N][N-1][N-2]...[2][1]
void IndexInvert(int J[], int N, int Idx)
{  int M, K;

   for (M=1, K=N-1; K > 1; K--)   // Generate (N-1)!
      M *= K;
   for ( K = 0; M > 1; K++ )
   {  J[K] = Idx / M;   // Offset in dimension K
      Idx = Idx % M;    // Remove K contribution
      M /= --N;         // next lower factorial
   }
   J[K] = Idx;          // Right-most index
}

// Generate a permutation based on its index / subscript set.
// To generate the lexicographic order, this involves _shifting_
// characters around rather than swapping.  Right-hand side must
// remain in lexicographic order
void Permute (char Line[], char first, int N, int Jdx[])
{  int Limit;

   Line[0] = first;
   for (Limit = 1; Limit < N; Limit++)
      Line[Limit] = (char)(1+Line[Limit-1]);

   for (Limit = 0; Limit < N; Limit++)
   {  char Hold;
      int Idx = Limit + Jdx[Limit];
      Hold = Line[Idx];
      while (Idx > Limit)
      {  Line[Idx] = Line[Idx-1];
         Idx--;
      }
      Line[Idx] = Hold;
   }
}

// Note:  hard-coded to generate permutation in the set [abc...
int main(int argc, char** argv)
{  int   N = argc > 1 ? atoi(argv[1]) : 4;
   char *Perm  = (char*) calloc(N+1, sizeof *Perm);
   int  *Jdx   = (int*)  calloc(N, sizeof *Jdx);
   int   Index = argc > 2 ? atoi(argv[2]) : 23;
   int   K, Validate;

   for (K = Validate = 1; K <= N; K++)
      Validate *= K;
   if (Index < 0 || Index >= Validate)
   {  printf("Invalid index %d:  %d! is %d\n", Index, N, Validate);
      return -1;   // Error return
   }
   IndexInvert(Jdx, N, Index);
   Permute (Perm, 'a', N, Jdx);
   printf("For N = %d, permutation %d in [0..%d] is %s\n",
          N, Index, Validate-1, Perm);
   return 0;       // Success return
}

Answer 4

Поскольку вы не указали, на каком языке вы хотите его получить, вот реализация на python .

Вам нужно только получить n-й элемент последовательности.

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

Обратите внимание, что это может быть не самый быстрый способ сделатьэто, но определенно легко.Для быстрого см. Ответ киборга.