计算全排列：给你几个字母，计算这几个字母的所有排列组合。比如给你{A,B,C}，你算出： {ABC, ACB, BAC, BCA, CAB, CBA}

提示，用递归比较容易。  评测一下自己算法的功力把。

共享不要算法 呵呵

搞不出来

//字母个数N
unsigned long ulResult=1;
for(int i=1; i<=N; i++)
{
   ulResult*=i;
}

是这样么

是不是公式  Result=N*(N-1)*(N-2)*...*1

:mad::mad::mad::mad:

[ Last edited by amziwei on 2005-10-26 at 22:48 ]

回楼上，不是算出排列组合的个数，而是要把所有排列组合打印出来。

试一下,错误之处,望高人指点.
void PrintCombi(const CString & strCombi, const CString & strAlphabet)
{
        //strCombi     已组合过的字母
        //strAlphabet 未组合的字母

        if ( strAlphabet.GetLength() == 1 )
        {
                printf("%s,", strCombi + strAlphabet );
                return ;
        };

        for(int i = 0; i < strAlphabet.GetLength(); i++ )
        {
                CString strSubCombi    = strCombi + strAlphabet.GetAt( i );               
                CString strSubAlphabet = strAlphabet;
                strSubAlphabet.Delete( i );

                PrintCombi( strSubCombi, strSubAlphabet );
        }

        return ;
}

int main(int argc, char* argv[])
{       
        CString strAlphabet ="ABCD";
        PrintCombi( "", strAlphabet );
        return 0;
}

脸丢大了

I think bigbox's algorithm is correct.  

There is a possible bug in C++:  I think the way PrintCombi( "", strAlphabet ); to call PrintCombi(const CString & strCombi, const CString & strAlphabet) is probably wrong.  "" cannot be a "const CString &".

这是我刚工作时写过的一个全排列算法的C++模板, 与STL中泛型算法next_permutation是一样的，我曾经用我的和STL的在windows和Linux下都做过测试，时间是一模一样的。这个算法应该是最优的了，没有一点无用的步骤（我是说算法，不是我的代码，我编程能力一般）它不仅能从头至尾把所有排列打印出来，还可以从任意位置打印，比如三个数123的全排列, 用我的模板可以从213开始，下一个字典序是231。当然，如果给定几个没排序的数字或字母，最好是先排序，再打印。

template < typename T >
bool _next_permutation( T *first, T *last );
#define N 8
int main(int argc, char* argv[])
{
        int i;
        int y = 1;//序号
        char a[N];
        for ( i=0; i<N; i++ )
        {
                a[i] = i + 1 + 64 + 32;
        }

/*        a[0] = 'd';
        a[1] = 'c';
        a[2] = 'h';
        a[3] = 'g';
        a[4] = 'f';
        a[5] = 'e';
        a[6] = 'b';
        a[7] = 'a';
        _next_permutation( &a[0], &a[N] );*/
        long t0 = time( NULL );
        do
        {
                cout << y << "　--->　";
                for ( i = 0; i<N; i++ ) cout << a[i];
                cout << endl;

                y++;
        }while( _next_permutation( &a[0], &a[N] ) );
        long t1 = time( NULL ) - t0;
        cout << t1 << endl;//当N为8时耗时130秒，与泛型算法next_permutation用时一样

        return 0;
}

template < typename T >
bool _next_permutation( T *first, T *last )
{
        int i;
        int j;
        int x = -1;
        int rang = last - first;
       
        for ( i=0; i<rang-1; i++ )
        {
                if ( *( first+i ) <= *( first+i+1 ) )
                {
                        x = i;
                }
        }

        if ( x != -1 )
        {
                for ( i=x; i<rang; i++ )
                {
                        if ( *( first+x ) <= *( first+i ) )
                        {
                                j = i;
                        }
                }

                _swap( *( first+x ), *( first+j ) );

                for ( i=x+1; i<rang; i++ )
                {
                        if ( i != rang + x - i )
                        {
                                int nSwap = rang + x - i;
                                _swap( *( first+i ), *( first+ ( rang+x-i ) ) );
                        }
                        if ( ( i + 1 ) * 2 > rang + x )
                        {
                                break;
                        }
                }
        }

        if ( -1 == x ) return false;
        else return true;
}

template < typename T >
void _swap( T &a, T &b )
{
        a = a + b;
        b = a - b;
        a = a - b;
}

引用:

Originally posted by WinHack at 2005-10-26 05:52 PM:
计算全排列：给你几个字母，计算这几个字母的所有排列组合。比如给你{A,B,C}，你算出： {ABC, ACB, BAC, BCA, CAB, CBA}

提示，用递归比较容易。  评测一下自己算法的功力把。

用递归效率应该是最低的了吧？