PermutationSequence [source code]
public class PermutationSequence {
static
/******************************************************************************/
class Solution {
public String getPermutation(int n, int k) {
// mark the 0-based index of 1..N
boolean[] used = new boolean[n];
// 1-based 1..N factorial lookup array: calculate in O(N)
int[] factorials = new int[n];
factorials[0] = 1;
for (int i = 1; i < factorials.length; i++)
factorials[i] = factorials[i - 1] * i;
char[] res = new char[n];
// convert to 0-based to be better handled by division and mod
k--;
for (int i = 0; i < n; i++) {
int idx = k / factorials[n - 1 - i];
res[i] = allocate (used, idx);
k %= factorials[n - 1 - i];
}
return new String (res);
}
/* Returns the unused number (1-based) index by IDX, which is its index in all UNUSED numbers
Develop with examples: easy to make mistake IDX = 2 in [1,2,3used,4used,5] */
char allocate (boolean[] used, int idx) {
int i = 0;
while (i < used.length) {
if (idx == 0 && !used[i]) {
used[i] = true;
break;
}
if (!used[i])
idx--;
i++;
}
return (char) (i + 1 + '0');
}
}
/******************************************************************************/
public static void main(String[] args) {
PermutationSequence.Solution tester = new PermutationSequence.Solution();
String[] inputs = {
"3", "1", "123",
"3", "2", "132",
"3", "3", "213",
"3", "4", "231",
"3", "5", "312",
"3", "6", "321",
};
for (int i = 0; i < inputs.length / 3; i++) {
int n = Integer.parseInt (inputs[3 * i]), k = Integer.parseInt (inputs[3 * i + 1]);
System.out.println (Printer.separator ());
String ans = inputs[3 * i + 2], output = tester.getPermutation (n, k);
System.out.printf ("%d and %d -> %s, expected: %s\n",
n, k, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
);
}
}
}
一开始感觉有点像integer跟binary之间的关系, 然后开始分析我人是怎么计算binary转换的; 但是笔算的时候想到一个问题, 这个题目其实跟binary还是有区别的: 这个问题里面, 比如当最高位确定之后, 那么下面的位置就不能继续选择这个最高位已经用过的数字了, 也就是digit之间是互斥的, 但是binary并没有这个性质; 所以两个问题之间的相似性有限, 可以用来开发思路, 但是不能盲目类推;
大概有一个思路:
5 - 1 = 4 = 2 * (2!) + 0 * (1!) -> "312"
{123}[2] = 3
{12}[0] = 1
4 - 1 = 3 = 1 * (2!) + 1 * (1!) -> "231"
{123}[1] = 2
{13}[1] = 3
起码人逻辑是有了; 但是有一个效率上的问题, 比如上面第二个例子, 当你一开始用[1]从123里面提取出来2之后, 剩下的是13, 然后你用[1]提取出来3, 问题是这个index怎么维护, 只剩下13的时候, 怎么用[1]找到3? 直接线性搜? 那么最后的复杂度不友好啊, 感觉这题最后应该是希望有一个O(N)解法的;
算了, 除了线性搜也想不到更好的办法了; 这样的做法最后的复杂度应该是N^2, 也不是完全不能接受;
最后虽然超时, 不过还是写出来了, 速度是16ms (53%). 主代码核心部分其实写的还算快, 最后就一两个小bug; 虽然是N^2的速度, 看起来其实还算不错;
一个解释思路的草稿图, 虽然实际上写的时候打的草稿比这个乱很多:
另外, 你可能认为可以用一个类似list的结构来完成allocate, 然后每当一个数字被用掉之后, 直接remove掉; 但是你要知道, 这个操作实际上是无法降低整个的复杂度的, 还是N^2, 而且remove并不是一个O(1)的操作;
另外, 回头想了一下, 我这里allocate的写法, 也就是在一个不断被allocate的array里面找到一个index among ONLY the unused, 应该是一个值得熟记的问题pattern; 感觉其他地方其实还是有可能继续碰到的;
没有editorial;
@tso said in "Explain-like-I'm-five" Java Solution in O(n):
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 the3 + (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);
}
}
比较长, 大概看了一下, 思路跟代码都是跟我的类似的, 他这个实际上也是O(N^2)的算法;
这个是这里看到的一个list的复杂度总结(要熟悉):
可以看到, get和remove当中必然有一个是O(N), 所以无论如何最后的复杂度肯定是N^2;
翻了一下, 底下其实不少人也意识到了这个问题;
@EdickCoding said in "Explain-like-I'm-five" Java Solution in O(n):
Thanks for sharing. I rewrote it to make it shorter
public class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
ArrayList<Integer> num = new ArrayList<Integer>();
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
num.add(i);
}
for (int i = 0, l = k - 1; i < n; i++) {
fact /= (n - i);
int index = (l / fact);
sb.append(num.remove(index));
l -= index * fact;
}
return sb.toString();
}
}
@yellowstone said in "Explain-like-I'm-five" Java Solution in O(n):
My idea is the same as yours.
public String getPermutation(int n, int k){
ArrayList<Integer> list = new ArrayList<Integer>();
StringBuilder sb = new StringBuilder();
for(int i=1; i<=n; i++) {
list.add(i);
}
int nth = k-1;
int divider = factorial(n-1);
while(n>1) {
int index = nth/divider;
nth = nth%divider;
sb.append(list.get(index));
list.remove(index);
divider /= n-1;
n--;
}
sb.append(list.get(0));// append last digit
return sb.toString();
}
public int factorial(int n) { // use tail recursion
return fact(n, 1);
}
private int fact(int n, int k) {
if(n==0)
return k;
else {
return fact(n-1, n*k);
}
}
他这个意思就是其实不用保存所有的阶乘, 只要保存最大的, 因为你实际上是从最大的开始用, 然后计算的过程中再慢慢除小就行了;
@Adeath said in An iterative solution for reference:
Recursion will use more memory, while this problem can be solved by iteration. I solved this problem before, but I didn't realize that using k = k-1 would avoid dealing with case k%(n-1)!==0. Rewrote this code, should be pretty concise now.
Only thing is that I have to use a list to store the remaining numbers, neither linkedlist nor arraylist are very efficient, anyone has a better idea?
The logic is as follows: for n numbers the permutations can be divided to (n-1)! groups, for n-1 numbers can be divided to (n-2)! groups, and so on. Thus k/(n-1)! indicates the index of current number, and k%(n-1)! denotes remaining index for the remaining n-1 numbers.
We keep doing this until n reaches 0, then we get n numbers permutations that is kth.
public String getPermutation(int n, int k) {
List<Integer> num = new LinkedList<Integer>();
for (int i = 1; i <= n; i++) num.add(i);
int[] fact = new int[n]; // factorial
fact[0] = 1;
for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
k = k-1;
StringBuilder sb = new StringBuilder();
for (int i = n; i > 0; i--){
int ind = k/fact[i-1];
k = k%fact[i-1];
sb.append(num.get(ind));
num.remove(ind);
}
return sb.toString();
}
@melvin.ming.gong said in An iterative solution for reference:
Thanks for your post and explanation.
I think linkedlist is as efficient as you can get in order to store the remaining numbers. Linkedlist may require counting index to get to the number, but it is more efficient than an array for removing elements. I haven't seen a better solution yet.
We can reduce the memory usage for factorial a little by using just one integer, since we are going down in factorial anyway.
I think you meant "permutations can be divided into n groups with (n - 1)! elements in each group". Thus, k / (n - 1)! is the index among current n groups, and k % (n - 1)! is the index for next iteration.
public String getPermutation(int n, int k) {
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) list.add(i);
int fact = 1;
for (int i = 2; i <= n; i++) fact *= i; // factorial
StringBuilder strBuilder = new StringBuilder();
for (k--; n > 0; n--) {
fact /= n;
strBuilder.append(list.remove(k / fact));
k %= fact;
}
return strBuilder.toString();
}
感觉这个减少空间占用的思路可能实际上会被当做Follow-Up被问到?
@hpplayer said in An iterative solution for reference:
Good solution. But I believe it is meaningless to discuss the operation on a list with at most of len 9
回头看了一下题目, 因为最后要求返回的是一个string, 实际上他们这里这个假设是有点道理的, 不过我并不支持这种思考方式;
@SergeyTachenov said in An iterative solution for reference:
LinkedListmay be efficient at removing things, but it's slow at locating things andremove(k / fact)needs to locate the element first, which is O(n). You can get instant removals when usingiterator.remove(), but I can't figure out how to apply it to this problem. As it is,LinkedListsolutions are bound to be slower thanArrayListbecause of its slower nature.
@pinkfloyda said in An iterative solution for reference:
k = k-1 is not intuitive, here is verbose code if not doing it, which is more intuitive.
e.g. 1234 for k = 6, we should keep 1 and reverse 234, note that the last state of permutation is always the reverse of the sequence.
public String getPermutation(int n, int k) {
List<Integer> num = new LinkedList<Integer>();
for (int i = 1; i <= n; i++) num.add(i);
int[] fact = new int[n]; // factorial
fact[0] = 1;
for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
StringBuilder sb = new StringBuilder();
for (int i = n; i > 0; i--) {
if(k%fact[i-1]==0) { // we already found it
int ind = k/fact[i-1]-1;
sb.append(num.get(ind));
num.remove(ind);
Collections.reverse(num); // the final state is the reverse of rest number
for(int d : num)
sb.append(d);
return sb.toString();
} else {
int ind = k/fact[i-1];
k = k%fact[i-1];
sb.append(num.get(ind));
num.remove(ind);
}
}
return sb.toString();
}
这个就是平时总结的好处了啊, 我最开始立刻就想到了转化为0based;
@lucastan said in Most concise C++ solution, minimal memory required:
string getPermutation(int n, int k) {
int i,j,f=1;
// left part of s is partially formed permutation, right part is the leftover chars.
string s(n,'0');
for(i=1;i<=n;i++){
f*=i;
s[i-1]+=i; // make s become 1234...n
}
for(i=0,k--;i<n;i++){
f/=n-i;
j=i+k/f; // calculate index of char to put at s[i]
char c=s[j];
// remove c by shifting to cover up (adjust the right part).
for(;j>i;j--)
s[j]=s[j-1];
k%=f;
s[i]=c;
}
return s;
}
写的比较复杂, 实际上还是一个类似的思路, 复杂度也是O(N^2). 他的思路首先包含了一个factorial从右到左计算的优化, 所以就不用单独存所有的factorial;
另外, 他的主算法的核心逻辑就是, 当你走到[i]的位置的时候, 你要在[i:n]的范围内找到应该放在[i]位置上面的数字; 然后把所有的[i+1:n]全都shift到右边去, 这样就可以把[i]放到这个位置来; 所以实际上他就是在[i+1:n]的范围内InPlace维护所有unused的数字; 用(n, k) = (3, 5)的例子自己算一个trace就可以了;
最后复杂度也是只能做到O(N^2), 因为这个shift操作; 想了一会儿, 好像没有好的规避的办法; 所以目前为止, 这个N^2好像是一条硬线;
discussion全都是类似的N^2解法;
submission基本波动;
Problem Description
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
- "123"
- "132"
- "213"
- "231"
- "312"
- "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Difficulty:Medium
Total Accepted:97.6K
Total Submissions:333.3K
Contributor:LeetCode
Companies
twitter
Related Topics
mathbacktracking
Similar Questions
Next PermutationPermutations