Ранговые и неиспользуемые перестановки всего за один цикл

Question

Я хочу ранжировать и разблокировать перестановки с одним циклом в лексикографическом порядке с данным len.

Перестановка с одним циклом - это то место, где вы можете посетить в этом цикле каждый элемент.

p:= (2,3,1) - перестановка с одним циклом. Имеет ранг 1.

p:= (3,1,2) также имеет 1 цикл, но ранг 2, потому что перестановка лексикографически больше, чем фрист, поэтому она становится более высокой.

p:= (1,2,3) - перестановка с 3 цикла (1),(2),(3)

Как эффективно ранжировать (перестановка с одним циклом для ранжирования) и отменять (ранг + длина до перестановки с одним циклом) в лексикографическом порядке? Я понятия не имею, как архивировать это.

Answer 1

Я нашел решение для ранжирования. Мы знаем, что перестановки длины n имеют n-1! перестановки с одним циклом. Благодаря этим знаниям мы можем прийти к следующему решению.

Рейтинг: пример 2341

Мы начинаем вычислять ранг с позиции 1, которая дает (n-1[position])! as tempvalue. Затем мы вычисляем индекс 2, который равен 0, потому что 1 выпадает через него, создает цикл (1). Чтобы завершить вычисление для первой позиции, нам нужно умножить index элемента на tempvalue, что приводит к 0 как temprank_0. Теперь мы продолжаем эти шаги для оставшихся позиций, чтобы добавить temprank_0+temprank_1+temprank_2+temprank_4 = 0

Unranking: 4 для перестановки len 4:

Мы делим ранг на (n-2[postion+1])!, что приводит 2, что это индекс 1234, который не создает цикл, поэтому 1 позиция перестановки равна 4. Затем мы вычитаем 2 times (n-2)! из 4. Это мы продолжаем это дважды. Итак, у нас есть 412. Таким образом, в конце мы добавляем только оставшееся значение 3. В конце мы получаем перестановку 4123.

.