If you dont get C today, u will miss the boat!!! - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

If you dont get C today, u will miss the boat!!!

If you dont get C today, u will miss the boat!!!# Stock

p*e2010-04-07 07:04

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; iif (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;
}

x*o2010-04-07 07:04

2 楼

5 dollar this month

p*e2010-04-07 07:04

3 楼

到现在为止我只发现这个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*e2010-04-07 07:04

4 楼

bool noSwap(const vector &num, int k, int i) {
for(int j=k; jif(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, vectorint> > &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*82010-04-07 07:04

5 楼

对你的代码做最小改动的话，就是在for loop 前面加一行
sort(data.begin()+start, data.end());
如果sub array不是sorted，检查set[i] == set[i-1]没有意义。

【在 p*****e 的大作中提到】

p*e2010-04-07 07:04

6 楼

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*a2010-04-07 07:04

7 楼

swap之后保持有序即可
简单是不是只swap一对值，而且把中间的值都右推一位，然后最右边的值放在当前位置
递归调用后，再swap回来

【在 p*****e 的大作中提到】

a*02010-04-07 07:04

8 楼

如果有duplicates 用下面这个算法
import java.util.*;
public class PermutationsII {

public ArrayList> permuteUnique(int[] num) {

Arrays.sort(num);
ArrayList> myResult = new ArrayListInteger>>();

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 的大作中提到】