求出词典索引的数值置换算法

Question

我正在寻找一个算法,给出一组数字(例如1 2 3)和一个索引(例如2)将根据字典顺序得到这些数字的第二个排列.例如,在这种情况下,算法将返回1 3 2.

Answer 1

这是Scala中的示例解决方案,我将详细解释:

/**
    example: index:=15, list:=(1, 2, 3, 4)
*/ 
def permutationIndex (index: Int, list: List [Int]) : List [Int] = 
  if (list.isEmpty) list else {
    val len = list.size     // len = 4
    val max = fac (len)     // max = 24
    val divisor = max / len // divisor = 6
    val i = index / divisor // i = 2
    val el = list (i)
    el :: permutationIndex (index - divisor * i, list.filter (_ != el)) }

由于Scala不是众所周知的,我想我必须解释算法的最后一行,除此之外,它还非常自我解释.

    el :: elist

从元素el和列表elist构造一个新列表.Elist是一个递归调用.

    list.filter (_ != el)

只是没有元素el的列表.

用一个小清单详尽地测试它:

(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n")

使用2个示例测试更大列表的速度:

scala> permutationIndex (123456789, (1 to 12).toList) 
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3)

scala> permutationIndex (123456790, (1 to 12).toList) 
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6)

结果立即出现在一台5岁的笔记本电脑上.对于12个元素的List,有479 001 600个排列,但是有100或1000个元素,此解决方案应该仍然可以快速运行 - 您只需要使用BigInt作为索引.

它是如何工作的？我制作了一个图形,可视化示例,列表(1,2,3,4)和索引15:

4个元素列表产生4个!排列(= 24).我们选择从0到4的任意索引!-1,假设为15.

我们可以可视化树中的所有排列,第一个节点来自1..4.我们分4!通过4看,每个第一节点导致6个子树.如果我们将索引15除以6,结果为2,并且索引为2的基于零的List中的值为3.因此第一个Node为3,List的其余部分为(1,2,4) .这是一个表,显示15如何导致Array/List /中的索引为2的元素:

0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23
     0      |     1    |         2         |     3
            |          | 0  1  2  3  4  5  |

我们现在减去12,即最后3个元素的单元格的第一个元素(12 ... 17),它有6个可能的排列,并且看看15个映射到3个.数字3现在导致数组索引1,是元素2,所以到目前为止的结果是List(3,2,...).

                        | 0 1 | 2 3 | 4 5 |
                        |  0  |  1  |  3  |
                              | 0 1 |

同样,我们减去2,并以2个排列结束2个剩余元素,并将索引(0,3)映射到值(1,4).我们看到,属于从顶部开始的15的第二个元素映射到值3,而最后一个步骤的剩余元素是另一个元素:

                             | 0 | 1 |
                             | 0 | 3 |
                             | 3 | 0 |

我们的结果是List(3,2,4,1)或索引(2,1,3,0).按顺序测试所有索引,它们按顺序产生所有排列.

Answer 2

这是一个简单的解决方案:

from math import factorial # python math library

i = 5               # i is the lexicographic index (counting starts from 0)
n = 3               # n is the length of the permutation
p = range(1, n + 1) # p is a list from 1 to n

for k in range(1, n + 1): # k goes from 1 to n
    f = factorial(n - k)  # compute factorial once per iteration
    d = i // f            # use integer division (like division + floor)
    print(p[d]),          # print permuted number with trailing space
    p.remove(p[d])        # delete p[d] from p
    i = i % f             # reduce i to its remainder

输出:

3 2 1

如果是列表,则时间复杂度为O(n ^ 2)p,如果是哈希表并且预先计算,则O(n)摊销.pfactorial