發(fā)現(xiàn)一直以來我寫全排列的方法似乎有點(diǎn)山寨，2333
正規(guī)點(diǎn)的應(yīng)該是永票，對于序列a[i..m],第i個(gè)地方的的值可以是a[i..m]中的任意一個(gè)，于是枚舉k = i..m，
然后交換a[i], a[k]蚯妇，然后遞歸下去
void perm(int a[], int l, int r) {
if (l == r) {
for (int i = 0; i < r; i++) {
printf("%d ", a[i]);
}
printf("\n");
return ;
}
for (int i = l; i < r; i++) {
swap(a[l], a[i]);
perm(a, l + 1, r);
swap(a[l], a[i]);
}
}
簡單的說i位置的元素就是剩下的元素里面選一個(gè)嘛，沒啥問題暂筝。
然后呢箩言，如果有重復(fù)元素咋辦呢？按照我以前的山寨寫法就要去重了焕襟，按內(nèi)存開銷可大了陨收。
其實(shí)很簡單，對于a[i]我們在剩下的里面選鸵赖，重復(fù)的只選一次不就行了务漩！所以呢，每次選的時(shí)候我們判斷一下當(dāng)前選的a[k],在a[i..k-1]里面是否出現(xiàn)過它褪，如果出現(xiàn)過菲饼，說明a[i]這個(gè)位置我們已經(jīng)選過a[k]這個(gè)值了，不用再重復(fù)選擇了列赎。
bool check(int a[], int l, int r) {
for (int i = l; i < r; i++) {
if (a[i] == a[r]) {
return false;
}
}
return true;
}
void perm(int a[], int l, int r) {
if (l == r) {
for (int i = 0; i < r; i++) {
printf("%d ", a[i]);
}
printf("\n");
return ;
}
for (int i = l; i < r; i++) {
if (!check(a, l, i)) {
continue;
}
swap(a[l], a[i]);
perm(a, l + 1, r);
swap(a[l], a[i]);
}
}
