先說一下，本人小菜雞，下面是我在解這題時慢慢探索的過程
我寫的很醜，大佬們鞭策小力一點
今天如果要列出1,2,3,4的所有排列
基本上就是一個四層陣列
一層代表一位
最後要排除掉有出現重複數字的組合
如1123,1232,1111,3333之類的
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
for (int k = 1; k <= 4; k++)
for (int l = 1; l <= 4; l++)
if (i != j && i != k && i != l && j != k && j != l && k != l)
cout << i << j << k << l << endl;
但是這邊每層陣列計數用的是變數 i,j,k,l
不同的變數之間其實不容易去鏈接
先改成建立一個整數陣列去存放每層的數字
int buffer[5];
for (buffer[1] = 1; buffer[1] <= 4; buffer[1]++)
for (buffer[2] = 1; buffer[2] <= 4; buffer[2]++)
for (buffer[3] = 1; buffer[3] <= 4; buffer[3]++)
for (buffer[4] = 1; buffer[4] <= 4; buffer[4]++)
if (buffer[1] != buffer[2] && buffer[1] != buffer[3] && buffer[1] != buffer[4] && buffer[2] != buffer[3] && buffer[2] != buffer[4] && buffer[3] != buffer[4])
cout << buffer[1] << buffer[2] << buffer[3] << buffer[4] << endl;
你可能會很疑惑
不管是對人生還是這一題
為什麼好端端的設變數要突然改成用陣列呢？
因為啊
層數並不是固定的啊XD
是來自使用者輸入啊XD
1,2,3,4....,n-1,n來排列
到n就需要n層陣列
但要怎麼自訂n層的陣列呢？
這時候就需要用到一個非常非常厲害的東西
在多啦A夢的口袋裡翻翻找找
神奇的【回溯法】！！！
這邊推薦一個小網站，他講的還蠻清楚的
https://hackmd.io/@qR5cY2d3Ql2AdYtLfHFxVg/B1Q0_-whQ?type=view
回朔法最主要的東西就是遞迴函數
這邊先用遞迴函數去寫
先用遞迴函數去寫寫看1,2,3,4的排列
void print4(int flo, int array[100])
{
if (flo == 4)
{
for (array[flo] = 1; array[flo] <= 4; array[flo]++)
if (array[1] != array[2] && array[1] != array[3] && array[1] != array[4] && array[2] != array[3] && array[2] != array[4] && array[3] != array[4])
{
cout << array[1] << array[2] << array[3] << array[4];
cout << endl;
}
return;
}
for (array[flo] = 1; array[flo] <= 4; array[flo]++)
print4(flo + 1, array);
}
main函數裡面：
print4(1, arra);
正常情況下就呼叫下一層迴圈
當到了自己想要的層數時就停下，然後做該做的事情(篩選出沒有重複的組合然後印出)
然後然後！
來實戰演練了哦！
如果看不懂先往下看，看完再回來這邊看(因為有篩選的動作)
void print(int flo, int n, int array[100])
{
int search;
if (flo == n)
{
for (array[flo] = 1; array[flo] <= n; array[flo]++)
{
search = 0;
for (int i = 1; i <= n; i++)
{
if (i == n)
break;
for (int j = i + 1; j <= n; j++)
{
if (array[i] == array[j])
search++;
}
}
if (search == 0)
{
for (int i = 1; i <= n; i++)
cout << array[i];
cout << endl;
}
}
return;
}
for (array[flo] = 1; array[flo] <= n; array[flo]++)
print(flo + 1, n, array);
}
main函數裡面：
int w;
cin >> w;
print(1, w, arra);
大致上是沒有什麼好變化的
只是4變成了n
然後有一個重點(看著我的眼睛)
關於篩選的問題
如果今天想要A,B,C三個數都不一樣的狀況
A!=B且A!=C且B!=C
這也是知道有三個數要比較的情況下才能這樣寫
不知道多少層的情況下要怎麼寫呢？？？
方法1(我上面實戰那邊用的就是這個)：
設立變數search
在新排出來的組合中尋找是不是有重複的
如果找到就++
最後看search
如果search依舊==0
就代表沒有人出現過一次以上
也就是每個數字都不一樣
目標達成！！！
方法2：
建立一個陣列去記錄一個數字使用的次數
不知道坐在電腦熒幕前的你有沒有了解過【桶子排序】這個東西
我感覺兩個的邏輯蠻像的
我先科普一下桶子排序(超級淺的桶子排序)
就是假設今天要排序 8,5,3,7四個數字
然後預先知道他們的範圍在1~10之間
所以先開一個陣列bucket
我們這邊先管
bucket[1]叫做1號桶子
bucket[2]叫做2號桶子，以此類推
一路設到bucket[10]共十個桶子
然後我就開始跑要排序的原始陣列了哦！！！
當我找到8的時候
我就把bucket[8]，8號桶子++
找到5的時候
就把5號桶子++
以此類推
全部+完之後
我再從小到大跑bucket陣列
當我發現bucket[3]不為0
我就輸出（bucket[3]）次的"3"
我舉個栗子（老梗不要嗆我）
bucket[5]=9
我就把"5"輸出9次
也就是555555555
換句話說就是
bucket[要印的數字]=印的次數
所以嚴格講桶子排序並不是真正意義上的排序
扯遠了！
回到篩選
一樣建立範圍的桶子
然後8出現我就bucket[8]++
一樣記錄出現次數
然後再從bucket陣列去找
如果每個桶子的數字只有0或1(代表只有出現一次或是沒出現)
那就印出來
篩選成功！
目的達成！
感謝你把它看完了
然後我要去吃午餐了，全家的小飯糰當早餐真的吃不飽
看完上面的想法先自己寫寫看再往下翻！！！
要看上面那些的程式碼的這邊是我GitHub的鏈接
先看完上面的在來看這邊吧(我寫的很亂)
補充報告！(鏈接失效了XDD)
補上新的鏈接：
然後補充一個回朔法的講解影片：
https://www.youtube.com/watch?v=nrHTtjkYEyQ
然後再補充一下我用dfs來寫的結果：
dfs的部分我現在還不太熟
等我熟了再過來補充報告！！！
補充報告！(鏈接失效了XDD)
補上新的鏈接：
然後補充一個回朔法的講解影片：
https://www.youtube.com/watch?v=nrHTtjkYEyQ
然後再補充一下我用dfs來寫的結果：
dfs的部分我現在還不太熟
等我熟了再過來補充報告！！！
你C++寫了那麼多，直接用內建的next_permutation函式就好了XD