返回第k个排列

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int count = 0;
    static String res = "";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        System.out.println(getPermutation(n, k));
    }

    public static String getPermutation(int n, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        backTrack(list, k, n, "");
        return res;
    }

    static void backTrack(List<Integer> list, int k, int num, String str) {
        if (num == 0) {
            count++;
            res = "" + str;
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(0)) {
                continue;
            }
            str += list.get(i);
            list.set(i, 0);
            backTrack(list, k, num - 1, str);
            if (count == k) {
                break;
            }
            list.set(i, i+1);
            str = str.substring(0, str.length() - 1);
        }

    }
}

开始用List集合保存调用超时但本地通过，后来通过定义全局变量的方式顺利AC。值得注意的是
普通的全排列交换方法由于元素的相对位置改变不能用，需要用两次相反方向的插入法来交换与
回溯。
public class Solution {
    String result;
    int count;
    public static void main(String[] args) {
        Solution s1 = new Solution();
        System.out.println(s1.getPermutation(3,5));
    }
    public String getPermutation(int n, int k) {
        char[] str = new char[n];
        for(int i=0; i<str.length; i++){
            str[i] = (char)('1' + i);
        }
        dfs(str, 0, k);
        return result;
    }

    private void dfs(char[] s, int index, int k) {
        if(index == s.length-1){
            count++;
            if(count == k){
                result = String.valueOf(s);
            }

        }
        else{
            for(int i=index; i<s.length; i++){
                char temp = s[i];
                                //插入法
                for(int j=i; j>index; j--){
                    s[j] = s[j-1];
                }
                s[index] = temp;
                dfs(s, index + 1, k);  //回溯
                temp = s[index];
                                //插入法
                for(int j=index; j<i; j++){
                    s[j] = s[j+1];
                }
                s[i] = temp;
            }
        }
    }
}

设置一个flag数组，每个flag数组元素对应于对应数字的使用情况，若被使用，则将其对应的数组元素置为0，使用完后，将其恢复。设计一个count来对生成的组合进行计数，每生成一个组合就count++，当第k个组合合成时（count==k），即可将此结果赋值给结果res，然后返回结果。

import java.util.ArrayList;
public class Solution {
    String res = "";
    int count = 0;
    public String getPermutation(int n, int k) {
        if(n <= 0 || k <= 0)
            return "";
        int[] flag = new int[n];
        for(int i = 0; i < n; i++){
            flag[i] = i + 1;
        }
        String s = "";
        solve(flag, s,  n, k);
        return res;
    }

    public void solve(int[] flag, String s, int n, int k){
        if(s.length() == n){
            count++;
            //生成第k个组合时，赋值给res
            if(count == k){
                res += s;
            }
            return ;
        }
        for(int i = 0; i < n; i++){
            if(flag[i] == 0){
                continue;
            }
            s += i + 1;
            //数字i+1被使用，将flag[i]置为0
            flag[i] = 0;
            if(count == k) break;
            solve(flag, s, n, k);
            s = s.substring(0, s.length()-1);
            //数字i+1被从组合中移除后，将flag[i]的值恢复
            flag[i] = i + 1;
        }
    }
}

题目大意: 给一个整数n(1<=n<=9)和k,将数组[1,2,3...,n]进行全排列,返回第k个数
试过先求出全排列再返回第k个可惜超时了,因此试试其他方法
思路:观察顺序的全排列集可以发现前 n!/n 项都是以i开头,所有以i开头的的数也遵循这个规律
即n=4时,所有排列为[1234,1243,1324,1342,1423,1432,2134,...]
可以看到所有以1开头的数,除1以外也是顺序的234的排列.
因此我们每一步可以求出这一步以什么开头,递归地直到只有一个数字时返回.

public String getPermutation(int n, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1 ; i <= n ; i ++) list.add(i);
        return solution(list, k - 1);
    }

    /**
    * 传入待排列的数组和要找的索引
    **/
    public static String solution(List<Integer> list, int f) {
        int size = list.size();
        if (size == 1) return list.get(0) + "";
        int total = n1(size);
        int count = total / size;
        int index = f / count;
        String res = list.get(index) + "";
        list.remove(index);
        f %= count; // 这里的索引要变为在目标组的索引
        res += solution(list, f);
        return res;
    }

    // 计算n!
    public static int n1(int n) {
        int res = 1;
        for (int i = 2 ; i <= n ; i ++) res *= i;
        return res;
    }

import java.util.*;
public class Solution {
    Map<Integer,Integer> util=new HashMap<>();
    public String getPermutation(int n, int k) {
        ArrayList<Integer> result=new ArrayList<>();
        buildUtil(n);

        backTrace(result,k-1,n,1);

        StringBuffer str=new StringBuffer();
        for(int i:result){
            str.append(i);
        }
        return str.toString();
    }
   public void backTrace(ArrayList<Integer> num,int rest,int n,int index){
        if(index==n){
            //得到剩下的最后一位
            for(int i=1;i<=n;i++){
                if(!num.contains(i)){
                    num.add(i);
                    return;
                }
            }
        }
        int a=rest/util.get(n-index);//商，有几个数字比当前数小的
        int b=rest%util.get(n-index);//余数

        a++;//最起码当前数字是a+1
        
       //临时list，用于非降序改变a的值
       ArrayList<Integer> temp = new ArrayList<>(num);
        Collections.sort(temp);
        for (int i : temp) {
            if (i <= a) {//如果比a小的数字已经存在，需要a++
                a++;
            }
        }
        num.add(a);
        backTrace(num,b,n,++index);
    }
    
    //得到并且保存阶乘，避免后续的运算
     public void buildUtil(int n){
        int temp=1;
        for(int i=1;i<=n;i++){
            temp*=i;
            util.put(i,temp);
        }
    }
}

leetcode上的一个回答

    public String getPermutation(int n, int k) {

        List<Integer> nums = new ArrayList<Integer>();
        int[] fn = new int[n+1];

        for(int i=1;i<=n;i++)
            nums.add(i);

        fn[0] = 1;
        int sum = 1;
        for(int i=1;i<=n;i++){
            sum *= i;
            fn[i] = sum;
        }

        k--;

        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++){
            int idx = k/fn[n-i];
            sb.append(String.valueOf(nums.get(idx)));
            nums.remove(idx);
            k = k - idx*fn[n-i];
        }

        return sb.toString();
    }

import java.util.ArrayList;

public class Solution {
   
   public String getPermutation(int n, int k) {
        ArrayList<String> dict = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            dict.add(Integer.toString(i));
        }

        return find(dict, k - 1, n);
    }

    public String find(ArrayList<String> dict, int k, int n) {
        if (n == 1) return dict.get(0);

        int num = count(n - 1);
        int index = k / num;
        int offset = k % num;

        String s = dict.get(index);
        dict.remove(index);
        k = offset;

        return s + find(dict, k, n - 1);
    }


    public int count(int x) {
        if (x == 1) return 1;
        return x * count(x - 1);
    }
}

import java.util.*;
public class Solution {
    public String getPermutation(int n, int k) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        for(int i=1; i<=n; i++) {
            list.add(i);
        }
        StringBuffer sb = new StringBuffer();
        int step = n-1;
        int step2 = factorial(n-1);
        while(step2 >= 1) {
        	int re = k % step2;
            int count = (k-1) / step2;
            sb.append(list.get(count));
            list.remove(count);
            if(re == 0){
            	while(!list.isEmpty())
                    sb.append(list.removeLast());
            	break;
            }
            k %= step2;
            step2 /= step;
            step--;   
        }
        return sb.toString();
    }
    
    public int factorial(int n) {
        if(n == 1 || n ==0)
            return 1;
        return n*factorial(n-1);
    }
}

最开始用暴力全排序的方法，直接超时，但是感觉在本地测试，速度没那么慢，毕竟1<n<=9;
暴力不行只能另想办法。
第一个数一定是123...n，所以第一位以1开头的数有（n-1）！种可能，
所以第二位以某个数开头有（n-2）!中可能
同理...
所以我们求每一位上的值是多少？
第一位是多少呢？
k/(n-1)!
第二位是多少呢？
k=k%(n-1)!
k/(n-2)!
同理一直算到最后一位数。
下面给出代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Solution {
    public  String getPermutation(int n, int k) {
        k--;//我们算法中是k从0开始，题意从1开始，所以我们要k--;
        int num[]=new int[n];
        int cnt=1;
        for(int i=0;i<n;i++)
        {
            num[i]=i+1;//初始化{1,2,3,...,n}
            cnt*=(i+1);//求n!
        }
        char[] cs=new char[n];//保存每一位结果
        for(int i=0;i<n;i++)
        {
            cnt/=(n-i);
            int selected=k/cnt;
            cs[i]=(char) ('0'+num[selected]);
            for(int j=selected;j<n-1-i;j++)
            {
                num[j]=num[j+1];
            }
            k%=cnt;
        }
        return new String(cs);
    }



}

I'm sure somewhere can be simplified so it'd be nice if anyone can let me know. The pattern was that:

say n = 4, you have {1, 2, 3, 4}

If you were to list out all the permutations you have

1 + (permutations of 2, 3, 4)

2 + (permutations of 1, 3, 4)

3 + (permutations of 1, 2, 4)

4 + (permutations of 1, 2, 3)

We know how to calculate the number of permutations of n numbers... n! So each of those with permutations of 3 numbers means there are 6 possible permutations. Meaning there would be a total of 24 permutations in this particular one. So if you were to look for the (k = 14) 14th permutation, it would be in the

3 + (permutations of 1, 2, 4) subset.

To programmatically get that, you take k = 13 (subtract 1 because of things always starting at 0) and divide that by the 6 we got from the factorial, which would give you the index of the number you want. In the array {1, 2, 3, 4}, k/(n-1)! = 13/(4-1)! = 13/3! = 13/6 = 2. The array {1, 2, 3, 4} has a value of 3 at index 2. So the first number is a 3.

Then the problem repeats with less numbers.

The permutations of {1, 2, 4} would be:

1 + (permutations of 2, 4)

2 + (permutations of 1, 4)

4 + (permutations of 1, 2)

But our k is no longer the 14th, because in the previous step, we've already eliminated the 12 4-number permutations starting with 1 and 2. So you subtract 12 from k.. which gives you 1. Programmatically that would be...

k = k - (index from previous) * (n-1)! = k - 2*(n-1)! = 13 - 2*(3)! = 1

In this second step, permutations of 2 numbers has only 2 possibilities, meaning each of the three permutations listed above a has two possibilities, giving a total of 6. We're looking for the first one, so that would be in the 1 + (permutations of 2, 4) subset.

Meaning: index to get number from is k / (n - 2)! = 1 / (4-2)! = 1 / 2! = 0.. from {1, 2, 4}, index 0 is 1

so the numbers we have so far is 3, 1... and then repeating without explanations.

{2, 4}

k = k - (index from pervious) * (n-2)! = k - 0 * (n - 2)! = 1 - 0 = 1;

third number's index = k / (n - 3)! = 1 / (4-3)! = 1/ 1! = 1... from {2, 4}, index 1 has 4

Third number is 4

{2}

k = k - (index from pervious) * (n - 3)! = k - 1 * (4 - 3)! = 1 - 1 = 0;

third number's index = k / (n - 4)! = 0 / (4-4)! = 0/ 1 = 0... from {2}, index 0 has 2

Fourth number is 2

Giving us 3142. If you manually list out the permutations using DFS method, it would be 3142. Done! It really was all about pattern finding.

public class Solution { public String getPermutation(int n, int k) { int pos = 0;
    List<Integer> numbers = new ArrayList<>(); int[] factorial = new int[n+1];
    StringBuilder sb = new StringBuilder(); // create an array of factorial lookup int sum = 1;
    factorial[0] = 1; for(int i=1; i<=n; i++){ sum *= i;
        factorial[i] = sum;
    } // factorial[] = {1, 1, 2, 6, 24, ... n!} // create a list of numbers to get indices for(int i=1; i<=n; i++){
        numbers.add(i);
    } // numbers = {1, 2, 3, 4} k--; for(int i = 1; i <= n; i++){ int index = k/factorial[n-i];
        sb.append(String.valueOf(numbers.get(index)));
        numbers.remove(index);
        k-=index*factorial[n-i];
    } return String.valueOf(sb);
}