获取 1 到 n 的第 k 个排列

Question

我从网站上查了一下，这叫做单峰置换，它定义为只有一个局部最大值的序列。例如 n = 5:

是否有算法可以得到第 k 个单峰排列？

Answer 1

这里的技巧是以二进制索引序列

       1234
       ----
12345 (0000)
12354 (0001)
12453 (0010)
12543 (0011)
13452 (0100)
13542 (0101)
14532 (0110)
15432 (0111)
23451 (1000)
23541 (1001)
24531 (1010)
25431 (1011)
34521 (1100)
35421 (1101)
45321 (1110)
54321 (1111)

然后观察数字 1..4 出现在 5 之前当且仅当它们的位为 0 时。在 Python:

def kth_unimodal(n, k):  # k is 0-indexed
  left = []
  right = []
  for j in range(1, n):  # 1..n-1
    if k & (1 << (n - 1 - j)):
      right.append(j)
    else:
      left.append(j)
  left.append(n)
  left.extend(reversed(right))
  return left

获取 1 到 n 的第 k 个排列

Get the kth permutation of 1 to n

algorithm

sequence

permutation