排列

• 2020 年 5 月 10 日
• 筆記
• STL

排列 （next_premutation的應用）

next_premutation（）

• STL中提供下一個 排列組合的函數 按照字典序返回 組合值
• 返回值： 如果有 下一個排列組合 返回 true ，沒有 返回 false
• 作用對象：通常是 數組 中的元素
• 時間複雜度：O(n)
• 排列的範圍：[first,last) 包含 first，不包含 last
• 注意： 在使用是通常是 先初始化一個最小 序列 （可以用sort 先排列一下），與之配套的循環 是 do while 先做操作，然後在 while 判斷是不是有下一個循環，因為 使用一次 next_premutation() 之後 就已經吧 下次的排列 放進原數組中去了 ，那麼最開始的初始化 （也算一種序列）就給 丟失了。

模板題

排列2

Problem Description

Ray又對數字的列產生了興趣：
現有四張卡片，用這四張卡片能排列出很多不同的4位數，要求按從小到大的順序輸出這些4位數。

Input

每組數據佔一行，代表四張卡片上的數字（0<=數字<=9），如果四張卡片都是0，則輸入結束。

Output

對每組卡片按從小到大的順序輸出所有能由這四張卡片組成的4位數，千位數字相同的在同一行，同一行中每個四位數間用空格分隔。
每組輸出數據間空一行，最後一組數據後面沒有空行。

Sample Input

1 2 3 4
1 1 2 3
0 1 2 3
0 0 0 0 

Sample Output

1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321

1123 1132 1213 1231 1312 1321
2113 2131 2311
3112 3121 3211

1023 1032 1203 1230 1302 1320
2013 2031 2103 2130 2301 2310
3012 3021 3102 3120 3201 3210

思路

• 創建一個 數組 每次輸入 1,2,3,4 下標的元素 然後將數組中元素排序，根據 next_premutation() 的返回值 來結束
• do 中的處理 可以把 每個元素的值 組合成 四位數字 放在一個數組裡然後 輸出 （需要一個計數器 ）
• 換行 的操作
  • 第一個：千位數相同 換行 ： 根據 創造出來的 b[i+1]==b[i] 進行判斷
  • 第二個： 每一組數據 換行 ，但是 最後一組數據不換行，可以在 輸出 全排列之前 輸出換行 ，這樣最後一組數據 之後就不會輸出換行

程式碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[5],b[30];
int main()
{
    int flag=0;
    while(cin>>a[1]>>a[2]>>a[3]>>a[4])
    
    {
        if(a[1]==0 && a[2]==0 && a[3]==0 && a[4]==0) break;
        else if(flag) cout<<endl;
        sort(a+1,a+5);
        int t=0;
        memset(b,0,sizeof(b));
        do{
            b[++t]=a[1]*1000+a[2]*100+a[3]*10+a[4];
        }while(next_permutation(a+1,a+5));
        
        for(int i=1;i<=t;i++)
        {
            if(b[i]<1000) continue;
            if(b[i+1]/1000 == b[i]/1000)  cout<<b[i]<<" ";
            else cout<<b[i]<<endl;
        }
        flag=1;
    }
    return 0;
}