posts - 21,  comments - 9,  trackbacks - 0
这是一个全排列算法的C++模板, 与STL中泛型算法next_permutation的功能是一样的。

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;
        }

        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;
}

posted on 2010-08-20 10:51 崔佳星 阅读(1960) 评论(2)  编辑 收藏 引用

FeedBack:
# re: 全排列算法(Using c++ template):
2010-08-23 14:18 | 路过
交换(_swap)的方法不好,对整型没有什么问题,其它类型就....比如浮点数等等  回复  更多评论
  
# re: 全排列算法(Using c++ template):
2012-04-06 10:38 | 崔佳星
C++里的浮点数比较还是很精确的。6位以内的小数都能准确比较。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜