生成组合算法

1.    按字典序生成组合

1.1.算法的描述

（1）从0...0开始，当字典序为1...1时，退出

（2）求出使得ai=0的最小整数i

（3）用1代替ai并用0代替ai-1, ai-1, ..., a0

2.    按格雷码序生成组合

2.1.算法描述

（1）从0...0开始，到10...0结束。

（2）设t代表代码中1的个数，若t为偶数，将最后一位变换（1变0，0变1）。

（3）若t为奇数，则找到最后一个1，然后把i+1位变换。

2.2.算法分析

通过算法分析，可以得出以下的结论

1. t的奇偶性是交替出现的，最开始为偶数。

2. 在C语言中，可以通过与一个数，将某一位变成0，通过或一个数将某变成1.

3. 可以通过循环右移，然后检查最后一位是否为1来找到最后一个1.

4. 通过判断最后一位是否为（二进制）1来判断是奇数还是偶数。

3.    生成r-组合

3.1.算法描述

（1）算法从1..10...0开始，到0...01...1结束。

（2）确定最大的整数k，使得ak +1<= n且ak + 1不是a1, a2,..., ar。

（3）打印新的r-组合a1...ak-1, ak+1,...,ak+r-k+1。

3.2.算法分析

1. 若将a1, a2, ..,ak也用字典序表示的话，生成r-组合就想法于将r个1和k-r个0进行排列。由于整个过程中，1的数目和0 的数目都是不变的，可以用一个长为k的字符串来表示，字符串中有r个1和k-r个0。r个1和k-r个0的每一个排列都对应一个组合。

2. 引入活动的1这个概念。ai=1为活动的1仅当存在aj=0且j>i。直接的说法就是仅当这个1的后面有0。

按字典序生成组合的实现

<代码>

// 生成字典序
void dict_gen(int *array, int len)
{
  int s = 1<<len;  // 要进行 2^n 次循环 
  for(int i=0;i<s; i++)
  {
    // 递增序列刚好对应了字典序的顺序 
    print_dict(array, len, i);
    cout<<endl;
  }
}

//显示字典序 
void print_dict(int *array, int len, int key)
{
  if(len == 0 || array == NULL)
    return;
  int curr = 1;
  std::bitset<8> aout(key);
  cout<<aout<<": ";
  for(int i=0;i<len;i++)
  {
    // curr为当前下标对应的字典序，如下标为3对应的字典序为：1000 0000
    curr = 1 << i;
    // key为一个综合的字典序，如 key = 0100 1100 
    // 如果 key在curr位为1的话，则会打印出来 
    if(key & curr)
    {
      cout//<<setw(4)
        <<array[i]<<',';
    }
  }
}

按格雷码序生成组合的实现

<代码>

#include <iostream>
#include <bitset>
#include <stdlib.h>
using namespace std;
using std::bitset;

#define BIT_WIDTH 8

// gray 码生成器 
void gray(int *array, int len);
// 用于找到最后一个1的位置，如果找不到，则返回-1 
int findlast1pos(int value);
// 用于打印gray码 
void print_dict(int *array, int len, int key);

void gray(int *array, int len)
{
  // 最后一个数，为: 100 
  int target = (1<<len - 1);
  // 循环次数，为：2^n 
  int total = (1<<len);
  // gray序的字典序，默认从0开始 
  int dict = 0;
  // 相加因子，用于将其中的某一位置0或置1 
  int factor = 0;
  // 表示1的个数是否为奇数，0为否 
  int oddFlag = 0;
  int v;
  
  for(int i=0;i<total;i++)
  { 
    print_dict(array, len, dict);
    // 如果是最后一个数，则退出 
    if(dict == target)
      break;
    
    // 如果有偶数个1  
    if(oddFlag == 0)
    {
      if(dict & 0x01)  //如果最后一位为 1，则置 0 
        dict--;
      else   
        dict = dict | 0x01;  // 否则置1
      oddFlag = 1;
    }
    else  // 如果是奇数个1 
    {
      v = findlast1pos(dict);  // 找到最后一个1的位置 
      if(v == -1)
        break;
        
      // 将那一位反向（0变1，1变0） 
      factor = 1<<(v+1);  
      if(dict & factor)
        dict = dict & (~factor); // 将第v位置0 
      else
        dict |= factor; // 将第v位置1 
      oddFlag = 0;
    }
    cout<<endl;
  }
}

// 算法是：将当前值反复右移并计数，直到最低位为1 
int findlast1pos(int value)
{
  int ret = -1;
  while(value != 0)
  {
    ret++;
    if(value & 0x01)
      break;
    value >>= 1;
  }
  return ret;
}

//显示字典序 
void print_dict(int *array, int len, int key)
{
  if(len == 0 || array == NULL)
    return;
  
  int curr = 1;
  std::bitset<BIT_WIDTH> aout(key);
  cout<<aout<<": ";
  for(int i=0;i<len;i++)
  {
    // curr为当前下标对应的字典序，如下标为3对应的字典序为：000 0100
    curr = 1 << i;
    // key为一个综合的字典序，如 key = 0100 1100 
    // 如果 key在curr位为1的话，则会打印出来 
    if(key & curr)
    {
      cout//<<setw(4)
        <<array[i]<<',';
    }
  }
}

生成r-组合的实现

<代码>

#define NUM_1 '1'
#define NUM_0 '0'

/**//**
* 生成r-组合的类 
*/
class RCombination
{
private:
  char *dict;
  int *array;
  int size;
  int r;
private:
    void initDict();
    void findActive1(int &activeIndex, int &count1);
    void adjustDict(int activeIndex, int count1);
    void printDict();
public:
  RCombination();
  ~RCombination();
  void genRComb(int *array, int size, int r);
};

RCombination::RCombination()
{
    size = 0;
    r = 0;
    dict = NULL;
}
RCombination::~RCombination()
{
    if(dict != NULL)
        delete []dict;
}

void RCombination::genRComb(int *array, int size, int r)
{
    if(array == NULL || size == 0 || r == 0)
        return;
  if(r>size)
    return;
    
    this->array = array;
    this->size = size;
    this->r = r;
 
    initDict();
    
    int count1 = 0;
    int activeInex = -1;
  
  do{
    cout<<dict<<": ";
    printDict();
      cout<<endl;
      
      findActive1(activeInex, count1);
      adjustDict(activeInex, count1);    
    }while(activeInex >= 0);
}

// 初始化基二的字典序
void RCombination::initDict()
{
    if(dict != NULL)
        delete []dict;
    if(size == 0)
    {
        dict == NULL;
        return;
    }
    dict = new char[size + 1];
    
    // 使用 1100初始化字典序 
    for(int i=0;i<size;i++)
    {
        if(i<r) dict[i] = NUM_1;
        else    dict[i] = NUM_0;
    }
    dict[size] = '\0';
}

// 从后往前找到第一个活动的 1 
// 活动的 1 定义如下：只要 1 后面有 0 （并不一定是紧接） 
void RCombination::findActive1(int &activeIndex, int &count1)
{
    int meet0 = 0;
    
  count1 = 0;
    activeIndex = -1;
    for(int i=size-1;i>=0;i--)
    {
        if(dict[i] == NUM_0)
        {
            meet0 = 1;
        }
        else
        {
            count1++;
            if(meet0 == 1)
            {
                activeIndex = i;
                break;
            }
        }
    }
}

// 设i是从最后面开始第1个活动的 1，将 a1, a2, , ai, ai+1,  变成
// a1, a2,ai-1, ai+1, ai+2,  
void RCombination::adjustDict(int activeIndex, int count1)
{
    if(activeIndex >= 0)
    {
        dict[activeIndex++] = NUM_0;
        for(;activeIndex < size; activeIndex++, count1--)
        {
            if(count1 <= 0)
                dict[activeIndex] = NUM_0;
            else
                dict[activeIndex] = NUM_1;
        }
    }
}
void RCombination::printDict()
{
    if(array == NULL)
        return;
    for(int i=0;i<size;i++)
    {
        if(dict[i] == NUM_1)
            cout<<array[i]<<',';
    }
}

终于贴完了……