排列组合算法

#include <iostream>  

using namespace std;

int Arr[10] = { 1,2,3,4,5 };
int select[10];
int index = 0;

/*common func*/
void swap(int a, int b)
{
    int c = Arr[a];
    Arr[a] = Arr[b];
    Arr[b] = c;
}

/*combination
selec k cells from [low, high];
m is the origin num of to be selected
递归算法
从n中先选出1个，然后从剩下的n-1中再选出m-1个；
递归实现
*/
void combine_recursion(int low, int high, int k, int m)
{
    int i;
    if (0 == k)    //got
    {
        cout << "[" << index++ << "]: ";
        for (i = 0; i < m; i++)
            cout << select[i] << " ";
        cout << endl;
        return;
    }

    for (i = low; i <= high; i++)
    {
        select[m-k] = Arr[i];    //m-k or k-1 需要用递归的参数来实现，而不能用全局变量
        combine_recursion(i + 1, high, k - 1, m);
    }
}

/*
二进制组合算法：
思路是开一个数组，其下标表示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
*/

void printArr(int* a, int m)
{
    int j;
    cout << "[" << index++ << "]: ";
    for (j = 0; j < m; j++)
        if (1 == a[j])
            cout << Arr[j] << " ";
    cout << endl;
}

//select n from m
void combine_normal(int m, int n)
{
    int *a = new int[m];
    int i, j;

    //init
    for (i = 0; i < m; i++)
        a[i] = (i<n)?1:0;
    printArr(a, m);
    //process
    int num = 0;    //统计1的个数
    for (i = 0; i < m - 1; )
    {
        //find (1 0)
        if (a[i] == 1 && a[i + 1] == 0)
        {
            a[i] = 0; a[i + 1] = 1;
            //把左边所有的1都放到最左边
            for (j = 0; j < i; j++)
                a[j] = (j < num) ? 1 : 0;
            printArr(a, m);
            i = 0;
            num = 0;
        }
        else
        {
            if (1 == a[i])
                num++;
            i++;
        }
    }

    delete[] a;
}

/*从low到high的全排列
递归算法
先输出第一个数字，然后输出后面n-1个序列的全排列；
然后用第一个数和后面的n-1个数，做交换；
重复上述步骤
*/
void permute_recursion(int low, int high)
{
    if (low >= high)
    {
        cout << "[" << index++ << "]: ";
        for (int i = 0; i <= high; i++)
            cout << Arr[i] << " ";
        cout << endl;
        return;
    }
    for (int i = low; i <= high; i++)
    {
        swap(low, i);
        permute_recursion(low + 1, high);
        swap(low, i);
    }

}

/*main entrance*/
int main(void)
{
    index = 0;

    //combine_recursion(0, 4, 4, 4);
    //combine_normal(5, 3);

    permute_recursion(0, 2);

    system("pause");
    return 0;
}