CODEWITHSUNDEEP
algorithmsequencepermutation
ChuNan
ChuNan

Reputation: 1141

Get the kth permutation of 1 to n

I checked from website, this is called unimodal permutation, which defines as a sequence that has only one local maximum. For example n = 5:

12345
12354
12453
12543
13452
13542
14532
15432
23451
23541
24531
25431
34521
35421
45321
54321

Is there an algorithm to get the kth unimodal permutations?

Upvotes: 0

Views: 725

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

The trick here is to index the sequence in binary

       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)

and then observe that the numbers 1..4 appear before the 5 if and only if their bit is 0. In 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

Upvotes: 8

Related Questions