只需一个周期即可对排列和非排列进行排列 [英] Rank and unrank permutations with just one cycle

问题描述

我想在给定的len的情况下按字典顺序对排列进行排序和取消排序.

I want to rank and unrank permutations with one cycle in lexicographical order with a given len.

一个循环的排列是您可以在此循环中访问每个元素的地方.

A permutation with one cycles is where you can visit in this cycle each element.

p:=(2,3,1)是一个循环的排列.排名1.

p:= (2,3,1) is a permutation with one cycle. Has rank 1.

p:=(3,1,2)也具有1个周期，但排名为2，因为按字典顺序排列的排列的第一部分更大，因此排名也更高.

p:= (3,1,2) has 1 cycle too, but rank 2, because the permutation is lexicographical greater the frist so it becomes a greater rank.

p:=(1,2,3)是一个带有3个周期的排列.(1)，(2)，(3)

p:= (1,2,3) is a permutation with 3 cycles. (1),(2),(3)

我如何按字典顺序有效地对(用一个周期排列的排列进行排列)和不按顺序(对一个周期排列的排列进行排列)排序?我不知道该如何存档.

How can I efficently rank (permutation with one cycle to rank) and unrank (rank + len to permutation with one cycle) in lexicographical order? I have no idea how to archive this.

推荐答案

我发现了排名的解决方案.我们知道长度为 n 的排列具有 n-1 ！一个周期的排列.基于这些知识，我们可以得出以下解决方案.

I discovered a solution for ranking. We know that a permutations of length n has n-1! permutations with one cycle. Due to this knowledge we can come to the following solution.

排名:示例 2341

我们开始用给出(n-1 [position])的1个位置来计算等级！作为温度值.然后，我们计算 2 的索引为0，因为 1 掉落到索引中会创建周期(1).为了完成对第一个位置的计算，我们需要将元素的 index 与 tempvalue 相乘，从而得到0作为 temprank_0 .现在，我们对剩余位置继续执行此步骤，以添加 temprank_0 + temprank_1 + temprank_2 + temprank_4 = 0

We start to calculating the rank with the 1 position this gives (n-1[position])! as tempvalue. Then we calculating the index of the 2 which is 0, because 1 is falling out through it creates the cycle (1). To complete the calculating for the first position we need to multiply the index of the element with the tempvalue, which leads to 0 as temprank_0. Now we continue this steps for the remaining positions to add temprank_0+temprank_1+temprank_2+temprank_4 = 0

未排序:排列len 4的 4 :

Unranking: 4 for permutation len 4:

我们将等级除以(n-2 [postion + 1])！，从而将 2 引为 1234 的索引，不要创建循环，因此排列的1位置是 4 .然后我们从 4 减去 2倍(n-2)！.这个我们继续两次.所以我们有 412 .因此，最后我们只添加剩余值 3 ，我们得到排列 4123 .

We divide the rank through (n-2[postion+1])! which leads 2 which is the index of 1234 which dont create a cycle so the 1 position of the permutation is 4 . Then we subtract 2 times (n-2)!from 4. This we continue this twice. So we have 412. So in the end we add just the remaining value 3 end we get the permutation 4123 .

这篇关于只需一个周期即可对排列和非排列进行排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！