登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

组合方案生成算法  

2009-05-11 17:38:48|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1.枚举int值,统计二进制bit中1的个数

1.1记忆化统计1的个数,x^(x-1)直接统计

 //enum int comb
int count(unsigned int x){
    int i = 0;
    while(x != 0){
        x = x&(x-1);
        i++;
    }
    return i;
}
void enumComb(int N,int M){
    int one[1<<15];
    for(int i = 0 ; i < (1 << (N+1)/2) ; i++){
        one[i] = count(i);
    }
    int half = N/2;
    for(int i = 1 ; i < (1 << half) ; i++){
        for(int j = 1 ; j < (1 << N-half) ; j++){
            if(one[i] + one[j] == M){
                 cout << i << " " << j << endl;      
            }    
        }
    }
}

 

2.组成生成

2.1递归枚举

//recurise comb gen
const int M = 3;
int comb[M+1];
void genComb(int index,int start,int N){
    if(index == M+1){
        for(int i = 1 ; i <= M ; i++)
             cout <<   comb[i] << " ";
        cout << endl;     
        return;
    }
    for(int i = start ; N - i >= M - index ; i++){
        comb[index] = i;
        genComb(index+1,i+1,N);
    }
}

2.2next生成法

寻找比当前组合大的那个最靠近的下一个组合:从右往左寻找第一个可以改变的位置值,从该位置值开始重新安排一个比它大1的值,可以安排到末尾。比如 C(5,3),2 3 5的下一个是 2 4 5。

 //next gen comb
void nextComb(int n,int m){
    int array[100];
    for(int i = 1 ; i <= m ; i++)
        array[i] = i;
    while(true){
        for(int i = 1 ; i <= m ; i++){
            cout << array[i] << " ";   
        }
        cout << endl;
        int pos = -1;
        for(int j = m ; j >= 1 ; j--){
           if(array[j]+1+m-j <= n){
              pos = j;       
              break;
           }    
        }       
        if(pos == -1)break;
        array[pos]++;
        for(int j = pos+1 ; j <= m ; j++){
           array[j] = array[j-1]+1;    
        }
    }
}

3.利用01排列,转为排列的生成

3.1自己写next peru

方法:从右往左扫描,找到第一个下降点处停止,设为 a|b

该处将排列分成左右两部分,其中右半部分是单掉上升的。从右半部分找到大于a的最小值,将它与a交换,然后将右半部分翻转即可。比如 a|b...c...变成a|b...a...

正确性说明:注意交换后的b...a...仍然是单调上升的,因为c处是大于a的最小值,故原来c的右边必然小于a,左边大于a。交换a,c保证该排列变大,将其翻转保证是大于它的最小值。同时这个查找过程,保证了被增长的位置尽量靠右。

//next perm
void nextPerm(int N){
    int array[100];
    for(int i = 0 ; i < N ; i++){
        array[i] = i+1;
    }
    while(true){   
    for(int j = 0 ; j < N ; j++)
        cout << array[j] ;
    cout << endl;           
    int pos = -1;
    for(int i = N-2 ; i >= 0 ; i--){
        if(array[i] < array[i+1]){
            pos = i+1;   
            int min_pos = pos;
            for(int j = pos ; j < N ; j++){
                if(array[j] > array[i] && array[j] < array[min_pos]){
                    min_pos = j;           
                }                   
            }
            int temp = array[i];
            array[i] = array[min_pos];
            array[min_pos] = temp;
            for(int j = pos,k = N-1 ; j < (N+pos)/2 ; j++,k--){
                int temp = array[j];
                array[j] = array[k];
                array[k] = temp;       
            }
            break;
        }
    }
        if(pos == -1) break;
    }

}

3.2利用c++库next_permutation

组合实际上可以看成是排列是01的特殊情况,故使用这个函数可以解决。

把数组元素赋恰当的0,1元素,直接调用next_permutation即可。

 

3.3递归生成排列

3.3.1无重复数字

//recur perm
void recurPerm(int array[],int index,int N){
    if(index == N){
        for(int i = 0 ; i < N ; i++)
            cout << array[i];
        cout << endl;       
        return;
    }
    for(int i = index ; i < N ; i++){
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;

        recurPerm(array,index+1,N);

        temp = array[index];
        array[index] = array[i];
        array[i] = temp;
       
    }


}

3.3.2含重复数字,表示采用a[i]表示i的个数的方法。

 //recur perm 2
void recurPerm2(int a[],int size,int array[],int index,int N){
    if(index == N){
        for(int i = 0 ; i < N ; i++)
            cout << array[i];
        cout << endl;       
        return;
    }
    for(int i = 0 ; i < size ; i++){
       if(a[i] > 0){
          array[index] = i;
          a[i]--;
          recurPerm2(a,size,array,index+1,N);
          a[i]++;
       }   
       
    }
   

}

 

各函数调用方法:


int main(){
    genComb(1,1,5);
    enumComb(10,2);
    nextComb(5,3);
    nextPerm(3);
    int array[4]={1,2,3,4};
    recurPerm(array,0,4);
    int a[2] = {2,2};
    recurPerm2(a,2,array,0,4);
    while(true);

}

  评论这张
 
阅读(938)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018