算法题/排列组合：第k个排列

题目

给出集合 [1,2,3...n]，其所有元素共有n!种排列。按大小顺序列出所有排列情况，并一一标记，给定n和k，返回第k个排列。

示例1：

输入：n=3, k=3
输出：213
解释：全排列：123, 132, 213, 231, 312, 321

示例2：

输入：n=3, k=1
输出：123

解答

Java

import java.util.Arrays;

public class Solution {
    //记录数字是否使用过
    private boolean[] used;
    // 阶乘数组
    private int[] factorial;
    private int n;
    private int k;
    public String getPermutation(int n, int k) {
        this.n = n;
        this.k = k;
        calculateFactorial(n);
        // 查找全排列需要的布尔数组
        used = new boolean[n + 1];
        Arrays.fill(used, false);
        StringBuilder path = new StringBuilder();
        dfs(0, path);
        return path.toString();
    }


    /**
     * @param index 在这一步之前已经选择了几个数字，其值恰好等于这一步需要确定的下标位置
     * @param path
     */
    private void dfs(int index, StringBuilder path) {
        if (index == n) {
            return;
        }

        // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        int cnt = factorial[n - 1 - index];
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (cnt < k) {
                k -= cnt;
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(index + 1, path);
            // 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
            // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
            return;
        }
    }

    /**
     * 计算阶乘数组
     * @param n
     */
    private void calculateFactorial(int n) {
        factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }
}

JavaScript

class Solution {
    constructor() {
        // 记录数字是否使用过
        this.used = [];
        // 阶乘数组
        this.factorial = [];
        this.n = 0;
        this.k = 0;
    }

    getPermutation(n, k) {
        this.n = n;
        this.k = k;
        this.calculateFactorial(n);
        // 查找全排列需要的布尔数组
        this.used = new Array(n + 1).fill(false);
        let path = '';
        this.dfs(0, path);
        return path;
    }

    dfs(index, path) {
        if (index === this.n) {
            return;
        }

        // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        let cnt = this.factorial[this.n - 1 - index];
        for (let i = 1; i <= this.n; i++) {
            if (this.used[i]) {
                continue;
            }
            if (cnt < this.k) {
                this.k -= cnt;
                continue;
            }
            path += i;
            this.used[i] = true;
            this.dfs(index + 1, path);
            // 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
            // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
            return;
        }
    }

    calculateFactorial(n) {
        this.factorial = new Array(n + 1);
        this.factorial[0] = 1;
        for (let i = 1; i <= n; i++) {
            this.factorial[i] = this.factorial[i - 1] * i;
        }
    }
}

Python

class Solution:
    def __init__(self):
        # 记录数字是否使用过
        self.used = []
        # 阶乘数组
        self.factorial = []
        self.n = 0
        self.k = 0

    def getPermutation(self, n, k):
        self.n = n
        self.k = k
        self.calculateFactorial(n)
        # 查找全排列需要的布尔数组
        self.used = [False] * (n + 1)
        path = ""
        self.dfs(0, path)
        return path

    def dfs(self, index, path):
        if index == self.n:
            return

        # 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        cnt = self.factorial[self.n - 1 - index]
        for i in range(1, self.n + 1):
            if self.used[i]:
                continue
            if cnt < self.k:
                self.k -= cnt
                continue
            path += str(i)
            self.used[i] = True
            self.dfs(index + 1, path)
            # 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
            # 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
            return

    def calculateFactorial(self, n):
        self.factorial = [0] * (n + 1)
        self.factorial[0] = 1
        for i in range(1, n + 1):
            self.factorial[i] = self.factorial[i - 1] * i

Go

package main

import (
	"fmt"
)

type Solution struct {
	// 记录数字是否使用过
	used      []bool
	// 阶乘数组
	factorial []int
	n, k      int
}

func main() {
	solution := Solution{}
	n := 4
	k := 9
	result := solution.getPermutation(n, k)
	fmt.Println(result)
}

func (s *Solution) getPermutation(n, k int) string {
	s.n = n
	s.k = k
	s.calculateFactorial(n)
	// 查找全排列需要的布尔数组
	s.used = make([]bool, n+1)
	path := ""
	s.dfs(0, &path)
	return path
}

func (s *Solution) dfs(index int, path *string) {
	if index == s.n {
		return
	}

	// 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
	cnt := s.factorial[s.n-1-index]
	for i := 1; i <= s.n; i++ {
		if s.used[i] {
			continue
		}
		if cnt < s.k {
			s.k -= cnt
			continue
		}
		*path += fmt.Sprint(i)
		s.used[i] = true
		s.dfs(index+1, path)
		// 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
		// 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
		return
	}
}

func (s *Solution) calculateFactorial(n int) {
	s.factorial = make([]int, n+1)
	s.factorial[0] = 1
	for i := 1; i <= n; i++ {
		s.factorial[i] = s.factorial[i-1] * i
	}
}