现在的位置: 首页 > 综合 > 正文

[转]对一组数穷尽所有排列

2013年10月10日 ⁄ 综合 ⁄ 共 1583字 ⁄ 字号 评论关闭

        对一组数穷尽所有排列,还有更直接的方法。将一个排列看作一个长整数,则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数,从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3,并令其对应的长整数为124653。要寻找比长整数124653更大的排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中的6比它的前一位数字4大,这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列,不能立即调整得太大,如本例中将数字6与数字4交换得到的排列126453就不是排列124653的下一个排列。为了得到排列124653的下一个排列,应从已经考察过的那部分数字中选出比数字大,但又是它们中最小的那一个数字,比如数字5,与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字。5与4交换后,得到排列125643。在前面数字1,2,5固定的情况下,还应选择对应最小整数的那个排列,为此还需将后面那部分数字的排列顺序颠倒,如将数字6,4,3的排列顺序颠倒,得到排列1,2,5,3,4,6,这才是排列1,2,4,6,5,3的下一个排列。按以上想法编写的程序如下。

【程序】
# include <stdio.h>;
# define SIDE_N        3
# define LENGTH        3
# define VARIABLES        6
int A,B,C,D,E,F;
int *pt[]={&A,&B,&C,&D,&E,&F};
int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
int side_total[SIDE_N];
main{}
{        int i,j,t,equal;
        for (j=0;j<VARIABLES;j++)
                *pt[j]=j+1;
        while(1)
        {        for (i=0;i<SIDE_N;i++)
                {        for (t=j=0;j<LENGTH;j++)
                                t+=*side[i][j];
                        side_total[i]=t;
                }
                for (equal=1,i=0;equal&&i<SIDE_N-1;i++)
                        if (side_total[i]!=side_total[i+1]        equal=0;
                if (equal)
                {        for (i=1;i<VARIABLES;i++)
                                printf(“%4d”,*pt[i]);
                        printf(“/n”);
                        scanf(“%*c”);
                }
                for (j=VARIABLES-1;j>;0;j--)
                        if (*pt[j]>;*pt[j-1])        break;
                if (j==0)        break;
                for (i=VARIABLES-1;i>;=j;i--)
                        if (*pt[i]>;*pt[i-1])        break;
                t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;
                for (i=VARIABLES-1;i>;j;i--,j++)
                {        t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t;        }
        }
}

抱歉!评论已关闭.