Question: https://oj.leetcode.com/problems/permutation-sequence/
Question Name: Permutation Sequence
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution: # @return a string def getPermutation(self, n, k): assert 1 <= n <= 9 # Get the total number of permutations total = 1 for i in xrange(n): total *= i + 1 # Adjust k to zero-based index k = k - 1 assert 0 <= k < total result = [] # The sequence o result permutation candidates = range(1, n+1) # The numbers to form the permutation remaining = total # How many possible permutations are there in # the remaining part? for position in xrange(n, 0, -1): remaining = remaining // position # Use the (k//remaining)th element and remove it from candidates result.append(str(candidates[k//remaining])) candidates.remove(candidates[k//remaining]) k %= remaining return "".join(result) |