algorithm - 生成与其反转次数配对的排列列表

Question

我正在寻找一种生成集合的所有排列的算法。为方便起见，集合始终为 [0, 1..n]。有很多方法可以做到这一点，而且不是特别难。

我还需要的是每个排列的反转次数。 执行此操作的最快(就时间复杂度而言)算法是什么？

我希望有一种方法可以在不增加复杂性的情况下生成那些产生反转次数的排列作为副作用。

该算法应该生成列表，而不是数组，但如果它在速度方面有足够大的差异，我会接受基于数组的算法。

加分(......没有分数......)如果它是功能性的并且是用纯语言实现的。

Answer 1

有Steinhaus–Johnson–Trotter algorithm这允许在排列生成期间轻松保持反转计数。维基摘录:

Thus, from the single permutation on one element,
1
one may place the number 2 in each possible position in descending
order to form a list of two permutations on two elements,
1 2
2 1
Then, one may place the number 3 in each of three different positions
for these three permutations, in descending order for the first 
permutation 1 2, and then in ascending order for the permutation 2 1:
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3

在递归的每一步，我们都将最大 数插入到较小 数列表中。很明显，这次插入增加了 M 个新的反转，其中 M 是插入位置(从右数)。例如，如果我们有 3 1 2 列表(2 个反转)，将插入 4

3 1 2 4  //position 0, 2 + 0 = 2 inversions
3 1 4 2  //position 1, 2 + 1 = 3 inversions
3 4 1 2  //position 2, 2 + 2 = 4 inversions
4 3 1 2  //position 3, 2 + 3 = 5 inversions

伪代码:

function Generate(List, Count)
   N = List.Length
   if N = N_Max then
      Output(List, 'InvCount = ': Count)
   else
      for Position = 0 to N do
         Generate(List.Insert(N, N - Position), Count + Position)

附言递归方法在这里不是强制性的，但我怀疑它对于函数式的家伙来说是很自然的

P.P.S 如果您担心插入到列表中，请考虑 Even's speedup section仅使用相邻元素的交换，并且每次交换递增或递减反转计数 1。