在任意大小的缓冲区中生成排列和组合
4.73/5 (8投票s)
一篇关于以新颖简单的方式快速生成所有可能的排列和组合的文章
引言
在本文中，我将解释一种不使用经典数学概念就能生成排列和组合的算法。在编程方面，我引入了一个多尺寸缓冲区，使该算法能够有效地处理任何生成的序列大小。所有这些都封装在一个我命名为CStrCombin的 C++ 类中。
CStrCombin 类在数学计算、密码生成器软件、单词生成器等许多领域都非常有用。我在一个演示程序中测试了这个类，并取得了良好的结果。我还将此算法的执行时间与一些执行相同功能的软件进行了比较，发现使用CStrCombin要快得多。
许可证
本文讨论的算法和CStrCombin类完全由我创作。但是，它们**仅限非商业用途**。您可以随意使用代码，只要您不声称是自己的。如果您将其用于您的产品，我希望收到通知。
本作品采用知识共享署名-相同方式共享 2.5 版许可协议授权。
背景
-
无重复的排列（排列）
排列是对象按不同顺序的排列。排列的顺序很重要。排列的表示法是
nPr。n是对象的总数（字符），r是要选择的对象数。r也称为可以容纳所选对象生成序列的位数。我们始终有n>=r。举个例子：
字符集是{A,B,C,D}（n=4）。我们想在n=4中获得所有r=3的排列。因此，结果是BCD, ACD, CBD, ABD, CAD, BAD, BDC, ADC, DBC, ABC, DAC, BAC, CDB, ADB, DCB, ACB, DAB, CAB, CDA, BDA, DCA, BCA, DBA, CBA.
4P3= 24
-
重复排列
计算方法是
nr。n可以小于r。举个例子：
字符集是{A,B,C,D}（n=4）
我们想在n=4中获得所有r=2的重复排列。因此，结果是DD, CD, BD, AD, DC, CC, BC, AC, DB, CB, BB, AB, DA, CA, BA, AA.
42 = 16
-
组合
组合是唯一的元素的无序集合。给定
S，所有可能的唯一元素的集合，组合是S的元素的一个子集。组合中元素的顺序不重要（包含相同元素但顺序不同的两个列表被视为相同的组合）。此外，组合中不允许重复元素（每个元素唯一出现一次）；这通常被称为“不放回/无重复”。
举个例子：
字符集是{A,B,C,D}（n=4）
我们想在n=4中获得所有r=3的组合。因此，结果是BCD, ACD, ABD, ABC.
4C3= 4
算法基础
我们的起点是用户给定的一个字符集。此外，用户还指定了将容纳所需组合/排列的位数。该算法能够生成带/不带重复的排列和组合。进行的第一步对于这三种可能的目标都相同。作为第一步，我们为集合中的每个字符分配一个数字，该数字代表集合中的索引。例如如下所示
collection | A 0 C 0 E F G 7 " J K L 9 N O , T R 7 ; U V # X Y Z ... @
---------- + ------------------------------------------------------------------------------------
index | 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 ... FF
正如您所注意到的，索引值是一个无符号整数值，占用 1 个字节。此算法最多支持 256 个字符。从这一点开始，索引值将始终以十六进制形式处理。
为了简化解释，让我们有一个包含 4 个字母和 3 个位置的集合。所以我们的分配如下
collection | A B C D +---+---+---+
---------- + --------------- The generation sequence have | ? | ? | ? |
index | 00 01 02 03 to be composed of 3 places +---+---+---+
| LSB RSB
LSB: Left Side Byte
RSB: Right Side Byte
第二步是初始化生成机制。这里是算法的主要思想。如果我们想生成排列/组合，我们就必须计算LSB LSB LSB和RSB RSB RSB之间的所有数字。这意味着00 00 00和03 03 03。完成此操作后，我们必须记住索引值只是对给定实际字符的替换。因此，当我们得到数字00 00 00时，它会自动映射到字符串AAA，而03 03 03映射到DDD。很容易推断出，在00 00 00和03 03 03之间计算出的数字，并且其中一个或多个元素不对应于先前选择的索引之一，将不会在我们感兴趣的排列/组合搜索中。
排列/组合是通过以下操作选择的
- 带重复的排列是所有收集的序列
- 无重复的排列是所有不包含任何重复元素的收集序列
- 组合是所有无重复的排列，其中序列的元素索引是排序的
在接下来的部分中，我们将了解如何创建应用上述算法的CStrCombin类。
CBuffer 定义
CBuffer 类定义如下
class CBuffer
{
public:
int m_size; // size of the unsigned integer buffer in bytes
unsigned char* m_buf; // buffer where data is stored
CBuffer(int,int); // constructor version 1
CBuffer(int); // constructor version 2
~CBuffer(void);
void operator++ ();
bool operator< (CBuffer&);
bool operator== (CBuffer&);
bool operator<= (CBuffer&);
};
使用最大缓冲区值初始化 CBuffer
构造函数版本 1 允许我们创建一个用精确值初始化的缓冲区。此值基于一个整数，该整数是给定字符集中最大的索引。
下面定义了这个构造函数
CBuffer::CBuffer(int hex,int places) //init with max value
{
m_size=places;
m_buf=new unsigned char[m_size];
for(int i=0;i<m_size;i++)
m_buf[i]=hex;
}
请注意，缓冲区数据由m_buf指向。
使用空缓冲区值初始化 CBuffer
要创建包含 0 的缓冲区，我们可以使用构造函数 2
CBuffer::CBuffer(int places)//init null buffer
{
m_size=places;
m_buf=new unsigned char[m_size];
for(int i=0;i<m_size;i++)
m_buf[i]=0;
}
从 0 计数到定义的最大值
这是通过++运算符完成的
//increment the CBuffer value by 1
void CBuffer::operator++ ()
{
for(int i=0;i<m_size;i++)
{
if(m_buf[i]!=0xff)
{
m_buf[i]++;
return;
}
else
m_buf[i]=0;
}
throw "Buffer overflow !"; //throw an exception when having an error
}
比较函数
CBuffer对象之间的比较可能很有用，尤其是与<=操作。因此，让我们编写相应的运算符。为此，我们需要编写<运算符和==运算符。这些将被<=运算符调用。代码如下
bool CBuffer::operator< (CBuffer& obj)
{ //obj and the current object must have the same m_size !
for(int i=m_size-1;i>=0;i--)
{
if(obj.m_buf[i]>m_buf[i])
return true;
else
if(obj.m_buf[i]<m_buf[i])
return false;
}
return false;
}
bool CBuffer::operator== (CBuffer& obj)
{ //obj and the current object must have the same m_size !
for(int i=m_size-1;i>=0;i--)
if(obj.m_buf[i]!=m_buf[i])
return false;
return true;
}
bool CBuffer::operator<= (CBuffer& obj)
{
if(*this<obj || *this==obj)
return true;
else
return false;
}
清理内存
在销毁缓冲区之前，我们可以像这样删除指向的数据
CBuffer::~CBuffer(void)
{
delete []m_buf;
}
现在我们能够创建任何大小的缓冲区。这项工作将在CStrCombin类中使用。
CStrCombin 定义
CStrCombin类定义如下
class CStrCombin //59.57 µs resolution in 3GHz P4 processor.
{
public:
struct stack_cell
{
unsigned char* buf;
struct stack_cell* prev;
};
private:
#define m_StrSize 256
//CStrCombin supports a maximum of 256 characters set
//from which the generation sequence is built
int m_mode;
//combWithoutRep: generates combinations without repetition ( n P r )
//combWithRep: generates combinations with repetition ( n power r )
//combComb: generates combinations with repetition ( n C r )
char m_str[m_StrSize+1]; //buffer for holding collection characters
int m_places; // generation sequence size in bytes
stack_cell* m_pHead;
//refers to a stack head used for saving numbers in memory
unsigned long long m_combNbr; //contains the number of sequences found
unsigned long long m_combTime; //contains the duration of processing
public:
enum RepetitionMode
{
combWithoutRep=1, // nPr mode
combWithRep, // n power r mode
combComb // nCr mode
};
CStrCombin();
~CStrCombin();
void SetGenMode(int);
void SetGenStr(char*);
void SetGenPlaces(int);
void GenAndSaveCombToFile(char*);
void push(unsigned char*);
void pop(HANDLE);
unsigned long long GetCombFoundNbr();
unsigned long long GetCombTime();
};
在接下来的部分中，我们将看到如何使用不同的类成员来生成组合/排列。
CStrCombin 初始化
通过类构造函数，我们将不同的数据成员设置为默认值
CStrCombin::CStrCombin():m_mode(0),m_places(0),m_pHead(NULL),
m_combNbr(0),m_combTime(0)
{ }
SetGenMode
它允许我们选择算法将使用的计算模式。我们有 3 种选择
combWithRep：如果选择此选项，算法将计算带重复的排列combWithoutRep：如果选择此选项，算法将计算无重复的排列combComb：如果选择此选项，算法将计算组合
函数代码如下
//called first
void CStrCombin::SetGenMode(int mode)
{
// sets the calculation mode.
if( mode == combWithRep || mode == combWithoutRep || mode == combComb)
m_mode=mode;
else
throw "Illegal mode value !";
}
这必须在其他成员函数之前调用。
SetGenStr
它保存将用于构建生成序列的序列。
函数代码如下
//called after SetGenMode
void CStrCombin::SetGenStr(char* str)
{
// saves the character set sequence
if(!str)
throw "Illegal string address !";
if(!strlen(str))
throw "Illegal string value !";
memset(m_str,0,m_StrSize+1);
strcpy(m_str,str);
}
这必须在SetGenMode之后调用。
SetGenPlaces
此函数设置位数。代码如下
//called after SetGenStr
void CStrCombin::SetGenPlaces(int places)
{
// sets the generation sequence size in bytes
if( m_mode != combWithRep && m_mode != combWithoutRep &&
m_mode != combComb)
throw "Illegal mode value !";
if ( places<=0 || ( (m_mode==combWithoutRep || m_mode == combComb)
&& strlen(m_str)<places) )
throw "Illegal places value !";
m_places=places;
}
GenAndSaveCombToFile
它计算并生成组合或排列。然后将其保存到指定文件中。此函数使用CBuffer类。
代码如下
//called after SetGenPlaces
void CStrCombin::GenAndSaveCombToFile(char* path)
{
// this is the calculation function
m_combTime=GetTickCount();
HANDLE hFile=CreateFile(path,GENERIC_WRITE,0,NULL,
CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
if(hFile==INVALID_HANDLE_VALUE)
throw "Unable to create file";
// init the max range and the start value
CBuffer maxRge(strlen(m_str)-1,m_places);
CBuffer counter(m_places);
for(counter;counter<=maxRge;counter++)
{//00
bool save=true;
for(int i=0;i<counter.m_size;i++)
if(counter.m_buf[i]>=strlen(m_str))
{
save=false;
break;
}
if(m_mode == combWithoutRep || m_mode == combComb)
{
for(int i=0;i<counter.m_size-1;i++)
for(int j=i+1;j<counter.m_size;j++)
if(counter.m_buf[i]==counter.m_buf[j])
{
save=false;
goto _skip;
}
if(m_mode == combComb)
for(int i=0;i<counter.m_size-1;i++)
for(int j=i+1;j<counter.m_size;j++)
if(counter.m_buf[j]<counter.m_buf[i])
{
save=false;
goto _skip;
}
}
_skip:
if(!save) continue;
//add value to linked list ...
push(counter.m_buf);
m_combNbr++;
}//00
//save value from linked list to file ...
while(m_pHead)
pop(hFile);
CloseHandle(hFile);
m_combTime=GetTickCount()-m_combTime;
}
push
//adds a value to the top of the stack
void CStrCombin::push(unsigned char* str)
{
stack_cell* pTmp=m_pHead;
m_pHead=new stack_cell;
m_pHead->prev=pTmp;
m_pHead->buf=new unsigned char[m_places];
memcpy(m_pHead->buf,str,m_places);
}
pop
//saves and removes the value at the top of the stack
void CStrCombin::pop(HANDLE hFile)
{
if(m_pHead)
{
stack_cell* pTmp=m_pHead->prev;
char* str=new char[m_places+3];
memset(str,0,m_places+3);
for(int i=0;i<m_places;i++)
str[i]=m_str[m_pHead->buf[i]];
strcat(str,"\r\n");
delete []m_pHead->buf;
delete m_pHead;
m_pHead=pTmp;
DWORD dw;
SetFilePointer(hFile,0,0,FILE_END);
WriteFile(hFile,str,strlen(str),&dw,NULL);
}
}
GetCombFoundNbr
"FONT-WEIGHT: 400">//found combinations number
unsigned long long CStrCombin::GetCombFoundNbr()
{
return m_combNbr;
}
GetCombTime
"FONT-WEIGHT: 400">// elapsed calculation time
unsigned "FONT-WEIGHT: 400">long long CStrCombin::GetCombTime()
{
return m_combTime;
}
现在CStrCombin类已准备就绪。在下一节中，我们将看到所暴露技术的概念证明：一个使用CStrCombin的具体示例。
示例
现在我们将以一个例子来测试CStrCombin类。该代码查找ABCD序列的所有带重复的排列，并将结果存储在一个文件中。
#include "stdafx.h"
#include <iostream>
#include "StrCombin.h"
#include <windows.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
try
{
// demonstrative example :
//------------------------------------------------------------------
CStrCombin obj;
obj.SetGenMode(CStrCombin::combWithRep);
obj.SetGenStr("ABCD");
obj.SetGenPlaces(4);
obj.GenAndSaveCombToFile("c:\\GenCombs.txt");
//------------------------------------------------------------------
HANDLE hF=CreateFile("c:\\CombInfos.txt",GENERIC_WRITE,0,NULL,
CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
DWORD dw;
char w[100];
sprintf(w,"%d combinations found.\r\n%d ms elapsed.\r\n",
(unsigned int)obj.GetCombFoundNbr(),
unsigned int)obj.GetCombTime());
SetFilePointer(hF,0,0,FILE_END);
WriteFile(hF,w,strlen(w),&dw,NULL);
CloseHandle(hF);
//-------------------------------------------------------------------
}
catch(char* str)
{
cout<<str<<endl;
}
return 0;
}
历史
- 2007/01/09 -
CStrCombin版本 1.0