获取 1 到 n 的第 k 个排列
Get the kth permutation of 1 to n
我从网站上查了一下，这叫做单峰置换，它定义为只有一个局部最大值的序列。例如 n = 5:
12345
12354
12453
12543
13452
13542
14532
15432
23451
23541
24531
25431
34521
35421
45321
54321
是否有算法可以得到第 k 个单峰排列？
这里的技巧是以二进制索引序列
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
我从网站上查了一下，这叫做单峰置换，它定义为只有一个局部最大值的序列。例如 n = 5:
12345
12354
12453
12543
13452
13542
14532
15432
23451
23541
24531
25431
34521
35421
45321
54321
是否有算法可以得到第 k 个单峰排列？
这里的技巧是以二进制索引序列
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