注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

计算排列和组合[原创]  

2010-11-02 08:53:34|  分类: algorithms |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

     排列和组合在程序中十分常见,尤其是对于文本序列的处理中。本人在此介绍一下求排列和组合的基本方法。

  1. 组合

    组合简单来说就是人n个个体中取出k个个体的问题。比如以于集合{a,b,c},其所有的组合是φ {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}由数学知识可以n个原素的集合有2^n个组合,那么用程序怎么计算出所有的组合呢,考虑上面的问题,结果中对于每个元素都有在结果中和不在结果中两种情况,因此可以用二进制位来表示其有和无,虽然集合的元素是无序的,但是如果我们把原集合的元素随机的一个序列定为一个初始的序列的话,那么从右向式的01序列不是正好成为一个整数了吗?,我们用一个n位的整数的各个位与集合元素的存在与否相对应,这个数子从0到2^n-1,每个数对应唯一种组合结果且每个组合结果对应一个数字(对于计数法的基本要求就是同一数字的计数形式是一样的,不同的数字计数形式必不能一样,初学计数可以是在幼儿园了吧J.可以你是否思考过其中的许多道理吗?每个位都是相应的权值,每个位的计数乘以相应的权值,你可能已经听过10进制,2进制,8进制,16进制,60进制,可是你见过2-10混合进制的吗?为什么不会这样,哈哈,自己思考一下吧,比较简单。其实历史上对于计数法是出现过同一个数对应于不同的形式的,不过不是计数整数,而是计数分数,这种计数当时可以产生了不少麻烦,只有当时少数管理历法与测量的才能计算明白,当然他们用别人对此的不了解坑了不少农民的土地,手法就如同今天的统计局一般J)。出于上面的原理,计算组合将是十分简单的,参考代码在最后面。

  2. 排列

    既然是排列,那么元素将被默认是有序的,如果是无序的不能区分的,那还排什么序啊!我们可以除了元素之间的序列后还规定排列与排列之间的顺序,这里用的顺序是是所谓lexicographical,也就是字典顺序。比如对于abc,它的最小排序是abc,最大的排序是cba,规定字典顺序是为了能从一个序列找到所谓的下一个排序序列或是前一个排序充列。比如abc的排序从小到大是abc<acb<bac<bca<cab<cba,那么从现在的一个序列如何找到下一个序列呢,我们从序列的末尾向前数,找到第一个相临元素a[i]和a[j],使得a[i]<a[j],之后再从末尾向前找到第一个满足a[k]使a[k]>a[i],之后把a[i]与a[k]对换,之后把新的k位置和其以后位置组成的序列反置。这个算法的原理是什么呢?对于如下序列:

Current Permuation

9

3

1

2

0

5

8

7

6

4

Next Permutation

9

3

1

2

0

6

8

4

5

7

 

其如下图所示:

因为a[i]和a[j]是从尾向前数每全对满足a[i]<a[j]的连续元素,因此对于x>=j,a[x]都是递减的,因此从x开始一直到结尾,这一子段达到了最大排列,而又有a[i]<a[j],我们的算法一定是尽量改变靠右端的序列,如果右边没达到最大就不能去动左边。因为lexicographical序列起作用序列位置是从左向右逐级递减的,也就是说左边的一个位置的变化比右端变化的作用大得多,这也是字典编写的原理,查首子母就把一大堆的单词排除了,之后依次类推。因此我们一定要从后面找一个比a[i]大的a[k]放到a[i]的位置,之后重排a[i]之后的序列达到最小,这个a[k]听选取当然一定要比a[i]大,但是由于越小的字母放在前面,字典顺序越靠前,因此一定要找到比a[i]大的的最小数,这样可以在这一步中达到字典顺序最小。但是由于从a[j]开始的子序列达到了最大,因此现在的序列还不能算是先前序列的next排序,也就是说不是刚好比先前排列大的排列。由于交换a[i]与a[k]注定了如论从a[j]开始的序列如何变化都是变换后的序列比先前的大,因此我们要把从a[j]开始的序列变为最小,注意交换a[i]和a[i]后a[j]到末尾还是逐级递减的,因此要达到最小只要把它逆序就可以了。变换后的序列如上图所示。

以下是参考代码,本代码使用了C++0x的功能,请在你的编译器中开启此选项

 

//test combination and Permutation

//written by saturnman

#include<iostream>

#include<vector>

#include<string>

#include<algorithm>

#include<iterator>

using namespace std;

template<class T>

void compute_combination(const vector<T>& input)

{

    unsigned int array_length = input.size();

    unsigned int num_of_combination = 1<<array_length;

    for(unsigned int is_combination=0;is_combination<num_of_combination;++is_combination)

    {

        //compute i's combination

        unsigned int is_combination_copy = is_combination;

        int bit_index = 0;

        cout<<"{ ";

        while(is_combination_copy!=0)

        {

            if(is_combination_copy%2 != 0)

            {

                cout<<input[bit_index]<<" ";

            }

            ++bit_index;

            is_combination_copy/=2; // >>1

        }

        cout<<"}"<<endl;

    }

}

template<class T>

bool compute_next_permutation(vector<T>& input)

{

    unsigned int array_length = input.size();

    bool has_next_permutation = false;

    int j  = array_length-1;

    int i  = j-1;

    while(j>0)

    {

        if(input[i]<input[j])

        {

            break;

        }

        --j;

        --i;

    }

    if(j>0)

    {

        int k = j;

        while(k+1!=array_length) //not end of array

        {

            if(input[k+1]>input[i])

            {

                ++k;

            }

            else

            {

                break;

            }

        }

        T tmp = input[i];           //swap a[i] and a[k]

        input[i] = input[k];

        input[k] = tmp;

        //reverse  array from j to end

        for(int index=0;index+j<array_length-index-1;++index)

        {

            T tmp = input[index+j];

            input[index+j] = input[array_length-index-1];

            input[array_length-index-1] = tmp;

        }

        has_next_permutation = true;

    }

    return has_next_permutation;

}

template<class T>

bool compute_previous_permutation(vector<T>& input)

{

    bool has_previous_permutation = false;

    unsigned int array_length = input.size();

    int j  = array_length-1;

    int i  = j-1;

    while(j>0)

    {

        if(input[i]>input[j])

        {

            break;

        }

        --j;

        --i;

    }

    if(j>0)

    {

        int k = j;

        while(k+1!=array_length) //not end of array

        {

            if(input[k+1]<input[i])

            {

                ++k;

            }

            else

            {

                break;

            }

        }

        T tmp = input[i];           //swap a[i] and a[k]

        input[i] = input[k];

        input[k] = tmp;

        //reverse  array from j to end

        for(int index=0;index+j<array_length-index-1;++index)

        {

            T tmp = input[index+j];

            input[index+j] = input[array_length-index-1];

            input[array_length-index-1] = tmp;

        }

        has_previous_permutation = true;

    }

    return has_previous_permutation;

}

int main()

{

    vector<string> v = {"a","b","c"};

    cout<<" v = {a b c}"<<endl;

    cout<<"***** Test Combination *****"<<endl;

    compute_combination(v);

    cout<<"***** Test Permutation *****"<<endl;

    //test next Permutation

    cout<<endl;

    do

    {

        copy(v.begin(),v.end(),ostream_iterator<string>(cout,""));

        cout<<endl;

    }while(compute_next_permutation(v));

    //test previous Permutation

    cout<<endl;

    do

    {

        copy(v.begin(),v.end(),ostream_iterator<string>(cout,""));

        cout<<endl;

    }while(compute_previous_permutation(v));

    return 0;

}

运行结果:

 v = {a b c}
***** Test Combination *****
{ }
{ a }
{ b }
{ a b }
{ c }
{ a c }
{ b c }
{ a b c }
***** Test Permutation *****

abc
acb
bac
bca
cab
cba

cba
cab
bca
bac
acb
abc

关于全排列的一个递归算法见下面链接

http://saturnman.blog.163.com/blog/static/557611200811241410214/

Ref:

《STL源码剖析》侯捷

  评论这张
 
阅读(1324)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017