p*****e
发帖数: 537 | 1 我是用swap 来做permutation这个题的，但是如果input是有dup的，那么output也可能
会有dup。大家帮我看看问题出在哪儿？
vector> permutationHelper(vector& data, int start){
vector> rt;
if (start == data.size()-1) {
rt.push_back(data);
return rt;
}
for (int i=start; i
if (i != start && data[i] == data[start]) continue;
if (i > start && data[i] == data[i-1]) continue;
vector set = data;
swap(set, start, i);
vector> perm = permutationHelper(set, start+1);
rt.insert(rt.end(), perm.begin(), perm.end());
}
return rt;
} | p*****e
发帖数: 537 | 2 到现在为止我只发现这个case有dup：{1, 1, 2, 2, 3, 3, 4},
permutation {2, 3, 4, 1, 1, 3, 2}被产生了两次：
第一次：1 1 2 2 3 3 4 (swap 0, 2) --> 2 1 1 2 3 3 4 (swap 1, 4) --> 2 3 1 2
1 3 4 (swap 2, 6) --> 2 3 4 2 1 3 1 (swap 3, 6) --> 2 3 4 1 1 3 2
第二次：1 1 2 2 3 3 4 (swap 0, 2) --> 2 1 1 2 3 3 4 (swap 1, 4) --> 2 3 1 2
1 3 4 (swap 2, 6) --> 2 3 4 2 1 3 1 (swap 3, 4) --> 2 3 4 1 2 3 1 (swap 4, 6
) --> 2 3 4 1 1 3 2
前三个swap都是一样的，后面的不一样。
用swap产生permutation怎么才能写对啊？ | T*******e
发帖数: 4928 | 3 bool noSwap(const vector &num, int k, int i) {
for(int j=k; j
if(num[j]==num[i]) return true; //see if any element from num[k] to
num[i-1] is equal to num[i]. If equal, that means someone equal to num[i]
has already taken this seat before. That possibility has been covered.
}
return false;
}
void permutationUniqueHelper(vector num, int n, int k, vector
int> > &res) {
if(k==n) {
res.push_back(num);
} else {
for(int i=k; i<=n; ++i) { //i<=n, n is index, vSize-1.
if(noSwap(num, k, i)) continue; // i!=k && num[i]==num[i-1]
doesn't work because permutation already disturbed the order in process
swap(num[k], num[i]);
permutationUniqueHelper(num, n, k+1, res);
//swap(num[k], num[i]); //if you use vector &num, then you
will need this line.
}
}
}
vector > permuteUnique(vector &num) {
vector > res;
int vSize=num.size();
if(vSize==0) return res;
permutationUniqueHelper(num, vSize-1, 0, res);
return res;
}
【在 p*****e 的大作中提到】
: 我是用swap 来做permutation这个题的，但是如果input是有dup的，那么output也可能
: 会有dup。大家帮我看看问题出在哪儿？
: vector> permutationHelper(vector& data, int start){
: vector> rt;
: if (start == data.size()-1) {
: rt.push_back(data);
: return rt;
: }
:
: for (int i=start; i
| l*********8
发帖数: 4642 | 4 对你的代码做最小改动的话，就是在for loop 前面加一行
sort(data.begin()+start, data.end());
如果sub array不是sorted， 检查set[i] == set[i-1]没有意义。
【在 p*****e 的大作中提到】
: 我是用swap 来做permutation这个题的，但是如果input是有dup的，那么output也可能
: 会有dup。大家帮我看看问题出在哪儿？
: vector> permutationHelper(vector& data, int start){
: vector> rt;
: if (start == data.size()-1) {
: rt.push_back(data);
: return rt;
: }
:
: for (int i=start; i
| p*****e
发帖数: 537 | 5 It works! Thanks a lot!
to
【在 T*******e 的大作中提到】
: bool noSwap(const vector &num, int k, int i) {
: for(int j=k; j: if(num[j]==num[i]) return true; //see if any element from num[k] to
: num[i-1] is equal to num[i]. If equal, that means someone equal to num[i]
: has already taken this seat before. That possibility has been covered.
: }
: return false;
: }
: void permutationUniqueHelper(vector num, int n, int k, vector: int> > &res) {
| l*****a
发帖数: 14598 | 6 swap之后保持有序即可
简单是不是只swap一对值，而且把中间的值都右推一位，然后最右边的值放在当前位置
递归调用后，再swap回来
【在 p*****e 的大作中提到】
: 我是用swap 来做permutation这个题的，但是如果input是有dup的，那么output也可能
: 会有dup。大家帮我看看问题出在哪儿？
: vector> permutationHelper(vector& data, int start){
: vector> rt;
: if (start == data.size()-1) {
: rt.push_back(data);
: return rt;
: }
:
: for (int i=start; i
| a**********0
发帖数: 422 | 7 如果有duplicates 用下面这个算法
import java.util.*;
public class PermutationsII {
public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> myResult = new ArrayList
Integer>>();
ArrayList temp1 = new ArrayList();
for(int i = 0; i<= num.length-1; i++)
temp1.add(num[i]);
myResult.add(temp1);
while(nextPermutation(num)){
ArrayList temp = new ArrayList();
for(int i = 0; i<= num.length-1; i++)
temp.add(num[i]);
myResult.add(temp);
}
return myResult;
}
public boolean nextPermutation(int[] num) {
int k = -1;
int l = -1;
int swap;
for(int i =0; i<= num.length-2; i++){
if(num[i]
k = i;
}
if(k == -1){
return false;
}
for(int i =k; i<= num.length-1; i++){
if(num[k]
l = i;
}
swap = num[k];
num[k] = num[l];
num[l] = swap;
for(int front = k+1, end = num.length-1; front < end; front ++, end-
-){
swap = num[front];
num[front] = num[end];
num[end] = swap;
}
return true;
}
【在 p*****e 的大作中提到】
: 我是用swap 来做permutation这个题的，但是如果input是有dup的，那么output也可能
: 会有dup。大家帮我看看问题出在哪儿？
: vector> permutationHelper(vector& data, int start){
: vector> rt;
: if (start == data.size()-1) {
: rt.push_back(data);
: return rt;
: }
:
: for (int i=start; i
|
|
