有重复元素的全排列问题

时间:2022-09-12 19:12:34

题目描述:


设R={ r1, r2, ……, rn }是要进行排列的n个元素。其中元素r1 ,r2 ,……,rn可能相同。试设计一个算法,列出R的所有不同排列。


给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。


源代码:

<span style="font-size:18px;">#include <iostream>
#include <algorithm>
#include <cstdio>
#define maxn 500

using namespace std ;

long long ans;

bool AppearBefore(char str[],int a ,int b )//!判断str中第b个元素是否在str[a ... b-1]中出现过,若没有返回真
{
    if(b>a)
        for(int i=a; i<b; i++)
            if(str[i]==str[b])
                return true;
    return false;
}

void perm(char str[],int k,int m)//!递归函数
{
    int i;
    if(k==m)
    {
        ans++;
        for(i=0; i<=m; i++)
            printf("%c",str[i]);
        printf("\n");
        return ;
    }
    else
        for(i=k; i <= m; i++)
            if(!AppearBefore(str,k,i) ) //!判断str数组中第i个元素是否在前面元素a[k ... i-1]中出现过。// 未出现过,此过程照旧继续,若出现过,这次以i元素打头的全排列罗列跳过。
            {
                swap(str[k],str[i]);
                perm(str,k+1,m);
                swap(str[k],str[i]);
            }

}

int main()
{
    char str[maxn];
    int n,i;

    cin>>n;

    ans=0;
    for(i=0; i<n; i++)
        cin>>str[i];

    perm(str,0,n-1) ;

    printf("%lld\n",ans);


    return 0;
}
</span>


参考网站2

参考网站2