第十二天：《LeetCode一天一例》-----n个不同的数组成n!个序列，找出第k个（又名Permutation Sequence）（python实现）

古城微笑少年丶 2022-03-06 15:05 164阅读 0赞

# n!个序列中找第k个 #

>         题目：  给定一个n = 7， 代表（1， 2， 3， 4， 5， 6， 7）。它们能组成7！个不同的序列。。在给定一个k值，找出第k个序列。。由于7！ = 5040。 我们不可能全写出来。。我们来看一下当n = 3 时，总共有六种：（1， 2， 3）， （1， 3， 2）， （2， 1， 3）， （2， 3， 1）， （3， 1， 2）， （3， 2， 1）。。不知大家有没有看出什么规律？

### 解析： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70][]

看一下上图，这是我写的当n = 4 的时候，总共有24中，每个框中有六种，后面以4， 5， 6打头的这里不写了。为啥同一个打头的只有六种，有什么决定的呢？   就是有后面的剩余的三个数的组合。。因为三个数有六种组合。。所以给定k值，我们先判断它属于哪个组？ 它属于哪个组，它的第一位就是几。。同理，确定了分组，再在分组中确定第二位，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1][]

同一分组内，除去第一位，不就是三个数的组合，再用同样的方法确定第二位的值 ，以此类推。。。。

### Python代码实现 ###

def find_n_k(n, k):
    
        # 首先进行累乘，算出当n等于几，有多少种组合
        fact = [0]*(n+1)  # 这里面
        fact[0] = 1  # 不从零个数开始  底下的for直接从1开始，然后到n
        for i in range(1, n+1):
            fact[i] = fact[i-1] * i
        # print(fact)  #[1, 1, 2, 6, 24, 120, 720, 5040]  可以看到第一个(实际第2个)位置是1，也就是一个数只有一种组合，
        #  第二个位置是2  也就是两个数有两种组合。  第三个位置时6，也就是说三个数有6中组合
    
    
        temp = [0]*n
        for i in range(1, n+1):
            temp[i-1] = i
    
        result = []
        k -= 1
        # 下面是核心思想
        for i in range(1, n):
    
            index = k // fact[n-i]
    
            result.append(temp[index])
    
            temp.remove(temp[index])
            k -= (index*fact[n-i])
        result.append(temp[0])
        return result
    
    
    if __name__ == '__main__':
    
        n = 4   # 则总共有7!种组合
        k = 12   # 我们要在7!种找到第k个组合输出
        result = find_n_k(n, k)
        print('第{}个序列为:{}'.format(k, result))

### 结果输出： ###

![20190321100151233.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220302/3963a9c0a0c8460e8d5a627820bfe3b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1]: /images/20220302/171383bfdde2427bb4c76ad7ba24b772.png
[20190321100151233.png]: /images/20220302/0b94ad89d24c464a933ccc59a40eecdd.png