本文转载：
排列组合有多种实现方法，下面介绍整理的一些方法。
一、最简单直接的就是递归
原理比较直接：计算一个集合的组合，首先选择一个元算，然后在剩下的集合中选择剩下的元素。看下面的源代码：
/**************************
* 计算一个集合的组合
*************************/
#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;
}
分享到：
相关推荐
在计算机算法设计中，排列和组合的概念能帮助我们理解数据的不同排列方式，为优化数据结构和提高算法效率提供思路。而二项式定理、鸽巢原理、生成函数和递推关系等则是解决更复杂问题时必须掌握的工具。这些理论不仅...
3. **算法**：排序（冒泡排序、快速排序、归并排序等）、搜索（深度优先搜索DFS、广度优先搜索BFS）、动态规划、贪心算法、回溯法等。 4. **文件操作**：如果题目涉及到读写文件，可能会用到fstream库进行输入输出...
DES（Data Encryption Standard）算法是一种经典的对称加密技术，由IBM在1970年代初期设计，后来被美国国家标准局（NIST）采纳为标准。它基于Feistel网络结构，使用64位的明文块和密钥进行操作，通过一系列复杂的...
标题中的"2016年考研终极冲刺800题—数据结构"表明这是面向数据结构科目的考研复习资料，特别强调了考研的针对性和题目数量，意在为考生提供充足和高质量的练习题。其中"终极冲刺"一词传递出强烈的紧张感和最后阶段...
《ET2016终极版》是一款专为服装行业设计的计算机辅助设计（CAD）软件，主要用于提升服装设计、打样和生产效率。这款软件集成了多种功能，旨在帮助设计师和制衣企业优化工作流程，减少错误，提高产品质量。下面我们...
无论什么样的并行计算方式，其终极目的都是为了有效利用多机多核的计算能力，并能灵活满足各种需求。相对于传统基于单机编写的运行程序，如果使用该方式改写为多机并行程序，能够充分利用...数字排列组合是个经典的算法
- **题目要求**：对于给定的 200 个四位数，如果每个数字都是偶数（0 或 2 或 4 或 6 或 8），则将其统计并按照从大到小的顺序排列。 - **核心算法**： - 数字筛选：遍历每一个四位数，检查每一位是否都是偶数。 -...
模式搜索。 朴素的模式搜索。 * n 米 纳米 比较指标。 返回索引的起点。 KMP 算法。 拉宾卡普算法。 有限自动机。 使用后缀树进行模式搜索。 使用后缀数组进行模式搜索。 最长回文子序列。 通配符模式匹配。 ——...
《DirectX游戏开发终极指南》这本书通过深入浅出的方式，为读者揭示了DirectX在游戏制作中的应用技巧和实践方法。 在压缩包文件的目录结构中，我们可以看到按照章节顺序排列的子文件夹，这些子文件夹可能包含了书中...
在IT领域，发牌程序是一种常见的模拟游戏或算法示例，尤其在开发扑克类游戏时。这个名为"发牌程序_终极应用举例"的压缩包很可能是包含了一个用于实现随机发牌功能的源代码示例。让我们深入探讨一下这个主题。 首先...
4. **结构体操作**：在"产品五个因素的比较排列"这类问题中，会使用到结构体来存储多个相关数据，并进行比较和排序。理解结构体定义、初始化及成员访问至关重要。 5. **素数判断**：素数是只有1和自身两个正因数的...
→目录面试蛋糕数组和字符串操作合并会议时间反转字符串反向单词合并已排序数组哈希和哈希表机上娱乐排列回文词云数据最高分贪婪算法苹果股票三个中的最大乘积所有其他数字的乘积就地改组排序、搜索和对数查找旋转点...
这篇资料主要涵盖了一些基础的数学概念和问题，包括数学历史、集合论、数论、概率游戏以及几何学和加密算法的知识点。以下是这些内容的详细解释： 1. 凸多边形周长与不变量：多边形周长固定时，多边形的内角和与...
"PFC源码"的提供意味着我们可以深入到软件的工作原理，了解算法细节，并可能进行自定义修改以适应特定的研究需求。源码分析可以帮助研究人员优化计算效率，改进模型精度，或者开发新的颗粒相互作用规则。 在"单轴...
由于它专注于特定领域，因此在搜索算法和信息处理上可以做得更为精细。用户在使用垂直搜索时，无需多次切换搜索渠道，就能获得全面的汽车信息，大大提高了查询效率。 一站式服务是汽车垂直搜索的终极目标。用户不仅...
3. **算法设计**：可能包括启发式搜索算法（如A*算法）来解决拼图，或者更简单的随机交换策略。 4. **事件处理**：监听用户的点击和拖动操作，更新拼图状态。 5. **状态管理**：保存和恢复游戏进度，确保拼图的正确...
对引用数据将出现次数多的字符串排列在第一位，然后依次降序排列所有数据。有两个参数，第一参数为数据区域引用，第二参数为名次，可使用ROW(a1)。 函数名称：替换 函数功能与参数：替换第N次出现的字符串的函数。...
TDK拥有最丰富的麦克风产品组合、基于运动传感器的光标控制的核心专利拥有者，适用于智能遥控器、智能电视和机顶盒的完整软件包（空鼠、手势、游戏控制）； Air Motion软件方案 嵌入式软件:AirMotion Library （AML...
这个项目，ALC-Quiz-App，是ALC 3.0版本的学习路径中的一个终极测试，旨在检验学习者对基础知识的理解。该应用利用了Android开发中的关键组件和技术，特别是与用户界面（UI）设计相关的部分。以下是对这个项目涉及的...
这个游戏的核心概念是玩家控制不同形状的方块，它们从屏幕顶部下降，玩家需要将它们排列成完整的水平线以消除得分。随着游戏的进行，方块下落的速度会逐渐加快，对玩家的反应速度和策略规划能力提出更高要求。 ...