首页 > 代码库 > poj 1731 Orders

poj 1731 Orders

题目链接:http://poj.org/problem?id=1731

 

思路:

    含有重复元素的全排列问题;元素个数为200个,采用暴力枚举法。

代码:

 

#include <iostream>#include <algorithm>using namespace std;const int MAX_N = 200 + 10;void PrintPermu( int n, char P[], char A[], int cur ){    int i, j;    if ( cur == n )    {        for ( i = 0; i < n; ++i )            cout << A[i];        cout << endl;    }    else    {        for ( int i = 0; i < n; ++i )        {            if ( i == 0 || P[i] != P[i-1] )            {                int c1 = 0, c2 = 0;                for ( j = 0; j < cur; ++j )                    if ( A[j] == P[i] ) c1++;                for ( j = 0; j < n; ++j )                    if ( P[i] == P[j] ) c2++;                if ( c1 < c2 )                {                    A[cur] = P[i];                    PrintPermu( n, P, A, cur + 1 );                }            }        }    }}int main(){    char P[MAX_N], A[MAX_N];    cin >> P;    sort( P, P + strlen(P) );    PrintPermu( strlen(P), P, A, 0 );    return 0;}

 

poj 1731 Orders