-
Notifications
You must be signed in to change notification settings - Fork 21
/
Permutation Sequence.java
executable file
·199 lines (168 loc) · 5.58 KB
/
Permutation Sequence.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
M
tags: Math, Backtracking
TODO: what about regular DFS/backtracking to compute the kth? dfs(rst, list, candiate list, k)
k是permutation的一个数位。而permutation是有规律的。
也就是说,可以根据k的大小来判断每一个数位的字符(从最大数位开始,因为默认factorio从最大数位开始变化)。
于是先求出n!, 然后 k/n!就可以推算出当下这一个数位的字符。然后分别把factorio 和 k减小。
另外, 用一个boolean[] visited来确保每个数字只出现一次。
这个方法比计算出每个permutation要efficient许多。
```
/*
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.
Hide Tags Backtracking Math
Hide Similar Problems (M) Next Permutation (M) Permutations
*/
/*
Correct solution is to reduce k, and manipulate the sequence
http://www.jiuzhang.com/solutions/permutation-sequence/
Thoughts:
k is the sum of possibilities.
Based on attempt1, attempt2, we understand that each digit leads a differnet sets of possibilities. The total is n!
For example,
factorio = # of a paticular set of possibilities, and remain = (k / factorio) means how any sets are there.
If remain == 0, that means factorio has more possibiities than k (factorio > k) so there is nothing changed on 1st
char position. For example, if given [1,2,3], then the string will end up as '1xx'.
With the above fact, we can find out each char by calculate k vs. factorio.
Note, each round, the factorio itself need to reduced.
*/
public class Solution {
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
StringBuffer sb = new StringBuffer();
boolean[] visited = new boolean[n];
//Largest possible number of posibilities, n!
int factorio = 1;
for (int i = 1; i < n; i++) {
factorio *= i;
}
//Put k into 0-base
k = k - 1;
for (int i = 0; i < n; i++) {
int index = k / factorio;
k = k % factorio;
for (int j = 0; j < n; j++) {
if (!visited[j]) {
if (index == 0) {
visited[j] = true;
sb.append((char)('0' + j + 1));
break;
} else {
index--;
}
}
}
if (i < n - 1) {
factorio = factorio / (n - i - 1);
}
}
return sb.toString();
}
}
/*
Based on attempt1, we can actually find every index in front by calling getPermutation(n,k) recursivly
Still timeout
*/
public class Solution {
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
ArrayList<Integer> nums = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
int frontInd = 0;
for (; frontInd < nums.size(); frontInd++) {
//find max # of permutations that's less than k, and start permutation with that perticular n at index 0.
int factorio = 1;
for (int i = 1; i < n; i++) {
factorio = factorio * i;
}
int startInd = frontInd;
int numPermute = factorio;
while (numPermute < k) {
numPermute += factorio;
startInd++;
}
if (startInd != frontInd) {
int temp = nums.get(startInd);
nums.remove(startInd);
nums.add(frontInd, temp);
k = k - numPermute;
n--;
}
}
StringBuffer sb = new StringBuffer();
for (int num : nums) {
sb.append(num);
}
return sb.toString();
}
}
/*
Attempt1: timeout
based on k[1 ~ k], find the max x that has x! < k, where x = [1 ~ n]
then swap (x + 1) and 1, start permutation, and find the (k - x!)th
*/
public class Solution {
public String rst = "";
public int index = 0;
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = i + 1;
}
//find max # of permutations that's less than k, and start permutation with that perticular n at index 0.
int factorio = 1;
for (int i = 1; i < n; i++) {
factorio = factorio * i;
}
int startInd = 0;
int numPermute = factorio;
while (numPermute + factorio < k) {
numPermute += factorio;
startInd++;
}
if (startInd != 0) {
int temp = nums[startInd];//findMax return value in [1 ~ n], and we need index
nums[startInd] = nums[0];
nums[0] = temp;
k = k - numPermute;
}
permute("", k, nums);// startInd + 1 is in [1 ~ n]
return rst;
}
public void permute(String s, int k, int[] nums) {
if (rst.length() != 0) {
return;
}
if (s.length() == nums.length) {
index++;
if (index == k) {
rst = s;
}
return;
}
for (int i = 0; i < nums.length; i++) {
if (!s.contains(nums[i] + "")) {
permute(s + nums[i], k, nums);
}
}
}
}
```