Предположим, вы переставляете буквы (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;
}
См http://math.stackexchange.com/questions/60742/finding-the -n-th-lexicographic-permutation-of-a-string –
Посмотрите на this нить. Это то, что вы ищите? –
И вот https://stackoverflow.com/a/8958309/312172 - еще один, с графикой. :) –