2015-07-29 1 views
2

Я знаю об алгоритме (его можно найти в Интернете), чтобы ранжировать перестановку, т. Е. Получить перестановку, возвратить целочисленный индекс в список лексикографически отсортированных перестановок, но я не знаю unrank алгоритм что делает обратное: с учетом индекса i возвращает i-ю перестановку в этом лексикографическом порядке.Перестановочные блокировки

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

+3

См http://math.stackexchange.com/questions/60742/finding-the -n-th-lexicographic-permutation-of-a-string –

+0

Посмотрите на this нить. Это то, что вы ищите? –

+0

И вот https://stackoverflow.com/a/8958309/312172 - еще один, с графикой. :) –

ответ

0

Предположим, вы переставляете буквы (a, b, c).

Есть 3 1 = 6 перестановок. Из них третий начинается с a и лексикографически предшествует другой третьей, начиная с b, предшествующей последней третьей, начиная с c.

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

Каждая из этих половин имеет только один элемент (последняя буква).

Итак, учитывая набор из трех элементов и индекс между нулем и пятью (скажем, 3), мы можем разделить (с напоминанием) на размер каждой «третьей», чтобы получить первую букву. Сейчас:

  • набор имеет размер п = 3
  • есть N = 6 перестановок
  • есть N = 3 группы перестановок, которые начинаются с каждым из п элементов
  • каждая группа имеет! размер n!/n = (n-1)! = 6/3 = 2 элемента

Чтобы определить индекс первого элемента, мы разделить на 2 с остатком:

3 & разделить; 2 = 1 бэр 1

Так как наш набор (а , b, c), это говорит о том, что первая буква - b.

Теперь мы можем удалить букву b из набора и использовать напоминание в качестве нового индекса. Мы получаем множество (а, с) и индекс 1. Повторно применяя алгоритм,

  • множество имеет размер п = 2
  • есть п! = 2 Перестановки
  • есть п = 2 группы перестановок, которые начинаются с каждого из n элементов
  • Каждая группа имеет размер n!/n = (n-1)! = 2/2 = 1 элемент

Чтобы определить индекс первого элемента, мы разделим на 1 с остатком:

1 & разделить; 1 = 1 бэр 0

Так как наш набор (а , c), это говорит о том, что второе письмо равно c.

Третий комплект сводится к Singleton a, и это наша третья буква.

Перестановка с индексом 3 равна b, c, a.

Давайте проверим это:

0 abc 
1 acb 
2 bac 
3 bca <-- correct! 
4 cab 
5 cba 

Таким образом, помещая это в реальном алгоритме и обобщающей:

public string NthPerm(string set, int n) 
{ 
    var res = ""; 
    while (set.Length > 0) 
    { 
     var setSize = Math.Factorial(set.Length-1); 
     var index = n/setSize; 

     res.Concat(set[index]); 

     set = index > 0 ? set.Substring(0, index) : "" + 
       index < set.Length-1 ? set.Substring(index+1) : ""; 

     n = n % setSize; 
    } 
    return res; 
}