算法与acm

组合方案生成算法

2009年5月11日 阅读(27)

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);

}

You Might Also Like