huaxiazhihuo

 

C++代码(4)排列与组合

        书接上回,继全排列之后,接下来的任务自然是要给我们的Permutation添加上部分排列的功能。所谓的部分排列,为了便于行文的展开,我也不怕再举例,比如,针对0到4这5个数的P(3,5),其排列如下:012,013,014,021,023,024,……,234,240,241,……,431,432。可以看到,其排列编号顺序与全排列类似,任何一个部分排列有且只有一个后继排列,好比240的下一位必然是241,123的下一位必须是201,所以我们完全可以采取同样的办法来处理部分排列。
        新的Permutation要能部分排列,用户必须将P(N,M)中N,M以某种方式告知Permutation,最恰当的地方就在Permutation的构造函数中传进去,原本只接受一个参数的构造函数,现在要接收两个参数了,同时,Permutation中除了保存N,还要保存M,因此,升级后的Permutation的定义如下。
class Permutation
{
public:
    
enum {MAX_SIZE = 10};
    Permutation(
int nTotal, int nPart)
    
{
        assert(
0 < nTotal && nTotal < MAX_SIZE);
        assert(
0 < nPart && nPart <= nTotal);
        m_nPart 
= (char)nPart;
        m_nTotal 
= (char)nTotal;
        
for (char i=0; i<m_nTotal; i++)
            m_Indexs[i] 
= i;
    }

    
public:
    
bool ToNext();

    
char operator[] (int n)const
    
{
        assert(
0 <= n && n <= m_nPart);
        
return m_Indexs[n];
    }


private:
    
char m_Indexs[MAX_SIZE];
    
char m_nPart;
    
char m_nTotal;
}
;
        很明显,必须在ToNext上大做文章。如果说全排列的ToNext稍微有一点点复杂,那么部分排列的ToNext就应该是很有点复杂,算法设计起来也不难,难的是如何用代码简洁地表达出来。请大家别急着看下去,先自己思考思考,这是一个很好的锻炼机会。
        ……,省略了思考的过程,其实也没什么,只要写几个部分排列的后继,就发现了其变化规律,就是先确定要改变的元素,然后保证跟在其后的数为最小,还是举例说明,P(9,5)中42876,其后继为43012,先找到41876中第1位即2要变成3,然后取剩下来的[0125678]中的012,置放于43之后。
        先考察尾数,无非分为两种情况。
        1、只变化尾数,如P(8,4),0125,0126,0127,求其后继排列的代码最容易编写了,只要注意到[0125|3467],5变为6,6是3467中,从后往前算,最后一个比5大的元素。更有意思的是,交换5,6之后,3457依然保持升序的样子。
        2、不只改变尾数,这是因为尾数要比未参与到部分排列中的元素要大,好比P(8,4),7605的下一位为7810,注意到[7605|1234],5大过1234。因此,必须考察5之后的0了,也即倒数第2位。同样,又分为两种情况。
        1)、改变倒数第2位。其改变方式又有两种:1、交换未参与排列的元素,如[7605|1234],交换0与1;2、交换参与排列的元素,如[7645|0123],7645变成7654。
        2)、不仅仅改变倒数第2位,这是因为尾数第2位大于尾数和未参与到部分排列中的元素,好比P(8,5),23476的下一位为23501,同样又分为两种情况。
        ……,以此类推,直到找不到要参与交换的元素,部分排列完成。
bool Permutation::ToNext()
{
    
if (m_nPart == m_nTotal)
    
{
        
// 为全排列
        
// ……
        return;
    }

    
char nToSwap = m_nPart-1;
    
char nLeft = m_nTotal - 1;
    
if (m_Indexs[nLeft] > m_Indexs[nToSwap])    // 只改变尾数
    {
        
while (nLeft > nToSwap && m_Indexs[nLeft]>m_Indexs[nToSwap])
            nLeft
--;    
        nLeft
++;
        swap(m_Indexs[nToSwap], m_Indexs[nLeft]);    
        
return true;
    }

    
while (nToSwap > 0 && m_Indexs[nToSwap]<m_Indexs[nToSwap-1&& m_Indexs[nToSwap]>m_Indexs[nLeft])
        nToSwap
--;
    
if (nToSwap == 0)    // 部分排列业已完成
        return false;
    nToSwap
--;    // 已确定这个位置要参与交换了
    if (m_Indexs[nToSwap] > m_Indexs[nLeft]) // 同参与部分排列的元素交换
    {
        
char nReplace = m_nPart - 1;
        
while (m_Indexs[nReplace] < m_Indexs[nToSwap])
            nReplace
--;
        swap(m_Indexs[nToSwap], m_Indexs[nReplace]);
    }

    
else    // 同未参与部分排列的元素交换
    {
        
while (nLeft >= m_nPart && m_Indexs[nLeft]>m_Indexs[nToSwap])
            nLeft
--;    
        nLeft
++;
        swap(m_Indexs[nToSwap], m_Indexs[nLeft]);        
    }

    sort(m_Indexs
+nToSwap+1, m_Indexs+m_nTotal);// 后面为剩下来的最小排列数
    return true;
}
        其实,根据排列的公式P(N, M)=N*P(N-1,M-1),很容易就可以写出P(N, M)的递归函数了。
void permutation(int* pSet, int n, int m)
{
    permutationImp(pSet, n, m, m);
}


void permutationImp(int* pSet, int n, int m, int M)
{
    
if (m == 0)
    
{
        
int* pFullSet = pSet-M;
        
for (int i=0; i<M; i++)
            cout 
<< pFullSet[i] << " ";
        cout 
<< endl;
        
return;
    }

    
for (int i=0; i<n; i++)
    
{
        swap(pSet[
0], pSet[i]);
        permutationImp(pSet
+1, n-1, m-1, M);
        swap(pSet[
0], pSet[i]);
    }

}

        非常简洁明了,这真让人沮丧,相比于Permutation的ToNext的种种烦杂,它无疑极具杀伤力。同样都是在搞排列,为何递归函数可以如此的简单呢?只因编译器帮递归干了很多事情,而ToNext中,我们必须事事亲历亲为。其实这也是递归与非递归的一大差别,递归中以一点点效率和灵活来换取代码的简洁易懂,而非递归则能以各种各样的方法来获取种种灵活与效率,编程就是这样,无非是在做各种各样的妥协。此外,Permutation的输出好看一点,更具规律,严格按照我们的要求来输出,这也能稍稍地自我安慰一下吧。
        依此编号的顺序算法,好比,C(4,3),其编号为012,013,023,123,不难设计出一个Combination,而且其ToNext要比部分排列的ToNext简单得多,只要注意到组合数中小的元素必然在前面,例如只存在012的组合,不存在120、102、021等组合数,因为它们都与012为同一个组合数,参考部分排列的代码,很容易就可写出Combination的代码。24点算法涉及的组合只为C(N,2),虽然C(N,2)为C(N,M)的特例,但基于时间与空间等效率的考虑,我更倾向于重新设计一个Combination2专门用来对付C(N,2)。其实算法的设计,不过是时间与空间的交换、复杂与简单的交换、通用与专用的交换,此三项的权衡而已。下面是Combination2的代码,非常简单,我也不想说太多。
class Combination2
{
public:
    Combination2(
int count)
    
{
        assert(count 
>= 2);
        m_nCount 
= (char)count;
        m_Indexs[
0= 0;
        m_Indexs[
1= 1;
    }


public:
    
char operator[](int n)const
    
{
        assert(
0<=&& n<2);
        
return m_Indexs[n];
    }


    
bool ToNext();
private:
    
char m_Indexs[2];
    
char m_nCount;
}
;

bool Combination2::ToNext()
{
    
if (m_Indexs[0== m_nCount-1 && m_Indexs[1== m_nCount-2)
        
return false;
    
if (m_Indexs[1< m_nCount-1)
    
{
        m_Indexs[
1]++;
        
if (m_Indexs[1== m_Indexs[0])
            m_Indexs[
1]++;
    }

    
else
    
{
        m_Indexs[
0]++;
        m_Indexs[
1= 0;
    }

    
return true;
}
        至此,终于圆满解决了排列与组合的问题,但其实都没多大的作用,对于不重复集合的排列与组合,只要用公式一乘,就出来结果了。研究可重复集合的排列与组合,可能还有点作用,其设计与代码编写,也很有意思,我就不再罗嗦了。

posted on 2011-07-19 19:04 华夏之火 阅读(2583) 评论(5)  编辑 收藏 引用

评论

# re: C++代码(4)排列与组合 2011-07-19 23:41 flyinghearts

部分排列没必要自己实现:

int x[9] = { 1,2,3,4,5,6,7,8,9};
const int N = 4, M = 2;
while (true) {
for (int i = 0; i < M; ++i) std::cout << x[i] << " ";
std::cout << "\n";
std::prev_permutation(x + M, x + N);
if (!std::next_permutation(x, x + N)) break;
}

  回复  更多评论   

# re: C++代码(4)排列与组合 2011-07-20 00:13 华夏之火

@flyinghearts
请确认,prev_permutation和next_permutation只能做全排列  回复  更多评论   

# re: C++代码(4)排列与组合 2011-07-21 21:47 flyinghearts

@华夏之火

代码都给出来了,请先运行下,再下结论。

不考虑效率的话,还可以用 next_permutation搞定 部分组合

  回复  更多评论   

# re: C++代码(4)排列与组合 2011-08-03 11:08 zpkiller

楼主好久没出新文章了啊   回复  更多评论   

# re: C++代码(4)排列与组合 2011-08-04 17:59 华夏之火

@zpkiller
在赶项目,下期是24点的程序,写了一半,等项目完成后再补充  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(3)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜