搜索算法终极-排列组合算法
本文转载：
排列组合有多种实现方法，下面介绍整理的一些方法。
一、最简单直接的就是递归
?????? 原理比较直接：计算一个集合的组合，首先选择一个元算，然后在剩下的集合中选择剩下的元素。看下面的源代码：
/**************************
?* 计算一个集合的组合
?*************************/
#include<stdlib.h>
#include<assert.h>
/*************************
?* 递归: 首先选择一个元素，然后在剩下的集合中选择其余元素
?************************/
typedef struct LiStack
{
????????? char element;
????????? struct LiStack* prev;
????????? struct LiStack* next;
}LiStack;
typedef struct SqStack
{
???????? char *elements;
???????? int top;?????? /*栈指针*/
}SqStack;
//采用链式存储的栈, 双向链表:由栈顶指向栈底
void CalCombinationLi(const char Elements[], int SetLg, int k, LiStack *StackHead, LiStack *StackTail)
{//Elements:集合, SetLg:集合长度, k:要选取的元素个数, stackHead:指向栈顶, StackTail:指向栈底
?????????????????? LiStack* StackTmp;
?????????????????? LiStack* StackN;
?????????????????? int i;
?????????????????? assert(k<=SetLg);//如果要选取的元素个数超过集合长度，则出错
??????????????????
?????????????????? if(k==0)
?????????????????? {//输出该次选取的元素组合
??????????????????????????? StackTmp = StackTail;
??????????????????????????? while(StackTmp)
??????????????????????????? {
?????????????????????????????????????????????? printf("%c ",StackTmp->element);
?????????????????????????????????????????????? StackTmp = StackTmp->prev;
??????????????????????????? }
??????????????????????????? printf(""n");
??????????????????????????? return;
?????????????????? }
?????????????????? //从该集合中顺序选取一个元素[i], 因为共选取k个元素, 所以最后一个可选择的元素为[SetLg-k]
?????????????????? //然后从剩下的集合[i+1:end]中选取其余的k-1个元素
?????????????????? //这样就构成了从集合(长度为SetLg)中选取k个元素, 按字典序的组合
?????????????????? for(i=0; i<=SetLg-k; ++i)
?????????????????? {
??????????????????????????? //将元素[i]压栈
??????????????????????????? StackN = (LiStack*)malloc(sizeof(LiStack));
??????????????????????????? StackN->element = Elements[i];
??????????????????????????? StackN->next = NULL;
??????????????????????????? StackN->prev = NULL;
???????????????????????????
??????????????????????????? if(StackHead)
??????????????????????????? {
???????????????????????????????????? StackHead->prev = StackN;
???????????????????????????????????? StackN->next??? = StackHead;?????????
??????????????????????????? }
??????????????????????????? else
??????????????????????????? {
???????????????????????????????????? StackTail = StackN;??
??????????????????????????? }
??????????????????????????? StackHead = StackN;
???????????????????????????
??????????????????????????? CalCombinationLi(Elements+i+1, SetLg-i-1, k-1, StackHead, StackTail);//从剩下的集合中选取k-1个元素
???????????????????????????
??????????????????????????? //将元素[i]弹出栈
??????????????????????????? StackTmp = StackHead;
??????????????????????????? StackHead = StackHead->next;
??????????????????????????? free(StackTmp);
??????????????????????????? if(StackHead)
??????????????????????????? {
???????????????????????????????????? StackHead->prev = NULL;????????
??????????????????????????? }
??????????????????????????? else
??????????????????????????? {
???????????????????????????????????? StackHead = NULL;
???????????????????????????????????? StackTail = NULL;????
??????????????????????????? }
?????????????????? }
}
//采用顺序存储的栈
void CalCombinationSq(const char Elements[], int SetLg, int k, SqStack *stack)
{//Elements:集合, SetLg:集合长度, k:要选取的元素个数, stack:栈
???????? assert(k<=SetLg);
????????
???????? int i;
???????? if(k==0)
???????? {//输出此次选取的元素组合
?????????????????? for(i=0; i<=stack->top; i++)//从栈底到栈顶
?????????????????? {
??????????????????????????? printf("%c ",stack->elements[i]);
?????????????????? }
?????????????????? printf(""n");
?????????????????? return;
???????? }
???????? for(i=0; i<=SetLg-k; i++)
???????? {
????????????????? //将元素[i]压栈
?????????????????? stack->top++;
?????????????????? stack->elements[stack->top]=Elements[i];
??????????????????
?????????????????? CalCombinationSq(Elements+i+1, SetLg-i-1, k-1, stack);
??????????????????
?????????????????? //将元素[i]弹出栈
?????????????????? stack->top--;
???????? }
}
//测试
int main()
{
???????? char elements[] = {'a', 'b', 'c', 'd'};
???????? const int NUM = sizeof(elements) / sizeof(elements[0]);
???????? LiStack *StackHead=NULL, *StackTail=NULL;
???????? int i;
???????? SqStack *stack=(SqStack *)malloc(sizeof(SqStack));
???????? stack->elements = (char *)malloc(sizeof(elements));
???????? for(i=1; i<=NUM; i++)
???????? {
?????????????????? //CalCombinationLi(elements, NUM, i, StackHead, StackTail);
?????????????????? CalCombinationSq(elements, NUM, i, stack);
???????? }
}
排列的源程序和上面的类似，其实上面的组合输出具有顺序性，和排列的输出没有多大的区别。
二、使用位运算（算法和程序来自网络）
?????? 对于元素个数为n的集合，可以使用n为来表示每一个元素，为1表示该元素被选中，为0表示该元素未被选中。那么，计算组合C(n, k)就相当于计算出n位数中有k个1位的所有数，每一个计算出的数就表示一个选中的组合。源代码如下：
/*******************************
?* 计算一个集合的组合
?******************************/
/******************************
?* 使用位运算来实现组合计算：对于元素个数为n的集合，可以使用n位来表示每一个元素，为1表示该元素被选中，为0表示该元素
?* 未被选中。那么，计算组合C(n, k)就相当于计算出n位数中有k个1位的所有数，每一个计算出的数就表示一个选中的组合
?*****************************/
#include<iostream>
#include<cassert>
using namespace std;
typedef unsigned int unint32_t;
?
//输出数表示的组合
template <typename T>
void OutputCombination(const T elements[], int num, uint32_t combinationBits)
{
???????? for(int i=0; i<num; i++)
???????? {
?????????????????? if(combinationBits & unint32_t(1)<<i)
??????????????????????????? cout << elements[i];
???????? }
???????? cout << endl;????
}
//产生跟pre有相同的1位，且比pre大的下一个数，如果存在，返回
uint32_t NextCombination(uint32_t pre)
{
???????? uint32_t lastOne = pre & -pre;
???????? uint32_t high = pre+lastOne;
????????
???????? if(high == 0)
?????????????????? return 0;//已经达到最大值
???????? uint32_t mid = high^pre;
???????? uint32_t low = (mid>>2)/lastOne;
???????? return high | low;
}
template <typename T>
void GenAllCombination(const T elements[], int num, int k)
{
???????? assert(1<=num && num<=32 && 1<=k && k<=num);
????????
???????? //产生最小的具有k个1的数
???????? uint32_t number = (uint32_t(1)<<k) - 1;
???????? //具有k个1的最大的num位数
???????? uint32_t maxNumber = number << (num-k);
????????
???????? for(; true; number=NextCombination(number))
???????? {
?????????????????? OutputCombination(elements, num, number);
?????????????????? if(number==maxNumber)
??????????????????????????? break;
???????? }
}
//测试
int main()
{
???????? const int NUM = 5;
???????? char elements[NUM];
????????
???????? for(int i=0; i<NUM; i++)
?????????????????? elements[i] = 'a'+i;
???????? GenAllCombination(elements, NUM, 2);
}
三、（算法来自网络）
?????? 组合算法：开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没有选中。
?????? 首先初始化，将数组前n个元素置1，表示第一个组合为前n个数；然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端；当第一个“1”移动到数组的m-n位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。
?????? 例如求5中选3的组合：
?????? 1???? 1???? 1???? 0???? 0???? //1, 2, 3
?????? 1???? 1???? 0???? 1???? 0???? //1, 2, 4
?????? 1???? 0???? 1???? 1???? 0???? //1, 3, 4
?????? 0???? 1???? 1???? 1???? 0???? //2, 3, 4
?????? 1???? 1???? 0???? 0???? 1???? //1, 2, 5
?????? 1???? 0???? 1???? 0???? 1???? //1, 3, 5
?????? 0???? 1???? 1???? 0???? 1???? //2, 3, 5
?????? 1???? 0???? 0???? 1???? 1???? //1, 4, 5
?????? 0???? 1???? 0???? 1???? 1???? //2, 4, 5
?????? 0???? 0???? 1???? 1???? 1???? //3, 4, 5
源程序如下：
?????? /***********************
?* 计算一个集合的组合
?**********************/
#include<stdlib.h>
/*输出某个组合*/
void OutputCom(const char elements[], int *flags, int length)
{
???????? int i;
???????? for(i=0; i<length; i++)
???????? {
?????????????????? if(flags[i]==1)
?????????????????? {
??????????????????????????? printf("%c ",elements[i]);
?????????????????? }
???????? }
???????? printf(""n");
}
/*计算组合*/
int GenCom(const char elements[], int setLg, int k)
//elements:集合元素; setLg:集合长度; k:从集合中要选取的元素个数
{
???????? if(k>setLg || k<=0)
?????????????????? return -1;
?
???????? int i,j;?????????????????? //循环变量
???????? int has10; //是否有"10"组合的标志:1-有;0-无
???????? int bound; //第一个"10"组合的索引
???????? int num1;?????????? //"10"组合左边的"1"的个数
???????? int *flags = (int *)malloc(setLg*sizeof(int));//与元素集合对应的标志:1-被选中;0-未被选中
???????? //初始化,将标志的前k个元素置1,表示第一个组合为前k个数
???????? for(i=0; i<k; i++)
?????????????????? flags[i]=1;
???????? for(i=k; i<setLg; i++)
?????????????????? flags[i]=0;
?
???????? OutputCom(elements, flags, setLg);//输出初始化的组合
???????? /*
?????????????????? 从左到右扫描标志的"10"组合，找到第一个"10"组合后将其变为"01"组合，同时将其左边的所有"1"全部移动到数组的最左端
???????? */
???????? while(1)
???????? {
?????????????????? num1 = 0;
?????????????????? has10= 0;
?????????????????? for(i=0; i<setLg-1; i++)
?????????????????? {
??????????????????????????? if(flags[i]==1 && flags[i+1]==0)//找到第一个"10"组合
??????????????????????????? {
???????????????????????????????????? bound = i;
?
???????????????????????????????????? flags[i]=0;//将该"10"组合变为"01"组合
???????????????????????????????????? flags[i+1]=1;
?
???????????????????????????????????? for(j=0; j<num1; j++)//将其左边的所有"1"全部移动到数组的最左端
???????????????????????????????????? {
?????????????????????????????????????????????? flags[j]=1;
???????????????????????????????????? }
???????????????????????????????????? for(j=num1; j<bound; j++)
???????????????????????????????????? {
?????????????????????????????????????????????? flags[j]=0;
???????????????????????????????????? }
?
???????????????????????????????????? has10 = 1;
???????????????????????????????????? break;
??????????????????????????? }
??????????????????????????? else if(flags[i]==1)
??????????????????????????? {
???????????????????????????????????? num1++;
??????????????????????????? }
?????????????????? }
?????????????????? if(has10==0)//没有"10"组合了,代表组合计算完毕
??????????????????????????? break;
?????????????????? OutputCom(elements, flags, setLg);
???????? }
????????
???????? return 1;
}
/*测试*/
int main()
{
???????? const char elements[5]="abcde";
???????? int setLg=5;
???????? GenCom(elements, setLg, 3);
???????? return 0;
}
?
递归实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 20
char a[MAX_LENGTH]; //存储初始字符串
char r[MAX_LENGTH]; //存储组合结果
//n, 初始字符串的长度
//m, 所求组合的长度
//k, 初始集合中当前处理位置, a[k]
//index, 所求组合数组的索引, r[index]
void combination(int n, int m, int k, int index)
{
int i;
if(index == m) //输出组合结果
{
?? for(i = 0; i < m; ++i)
??? printf("%c", r[i]);
?? printf("\n");
?? return;
}
for(i = k; i < n; ++i)
{
?? r[index] = a[i];
?? combination(n, m, i + 1, index + 1);//注意第三个参数是i + 1
}
}
int main(int argc, char** argv)
{
strcpy(a, "abcde");
combination(5, 3, 0, 0);
system("pause");
return 0;
}
?