SCAU 算法課的題

8594?有重復元素的排列問題（優先做）

時間限制:1000MS? 內存限制:1000K
提交次數:1610 通過次數:656

題型: 編程題???語言: G++;GCC;VC

?

Description

設集合R={r1,r2,...,rn}是要進行排列的n個元素，其中r1,r2,...,rn可能相同。
試著設計一個算法，列出R的所有不同排列。
即，給定n以及待排的n個可能重復的元素。計算輸出n個元素的所有不同排列。

輸入格式

第1行是元素個數n，1<=n<=15。接下來的1行是待排列的n個元素，元素中間不要加空格。

輸出格式

程序運行結束時，將計算輸出n個元素的所有不同排列。最后1行中的數是排列總數。（說明：
此題，所有計算出的排列原本是無所謂順序的。但為了容易評判，輸出結果必須唯一！
現做約定：所有排列的輸出順序如課本例2-4的程序段的輸出順序，區別僅是這道題是含
重復元素。）

?

輸入樣例

4
aacc

?

輸出樣例

aacc
acac
acca
caac
caca
ccaa
6

?

?

構造函數F（be, en）表示要對這個區間進行全排列
那么F(be, en)的結果相當于第一位是誰誰誰的 + F(be + 1, en)的結果
如果可以重復，那么第一位沒有限定
但是這題有重復，那么和第一位換過的元素就不能再次換
就相當于第一位只能出現a、b、c、d、e.....只能一次

?

?

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
char str[222];
int ans;
bool is[22][222];
void fun(int be, int en) {if (be == en) {ans++;printf("%s\n", str + 1);return;}is[be][str[be]] = true;fun(be + 1, en);for (int i = be + 1; i <= en; ++i) {if (is[be][str[i]]) continue;is[be][str[i]] = true;swap(str[be], str[i]);fun(be + 1, en);swap(str[be], str[i]);}memset(is[be], false, sizeof is[be]);
}
void work() {int lenstr;scanf("%d", &lenstr);scanf("%s", str + 1);fun(1, lenstr);printf("%d\n", ans);
}int main() {
#ifdef localfreopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endifwork();return 0;
}

?