递归实现 从n个数中选取m个数的所有组合

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

有个数,从中选取个数,找出所有的组合情况(不分顺序)。这样的组合共有 .

一个数组 data 有 n 个元素,从中选取 m 个数的组合 arr,使用递归算法实现是这样一个过程:
1) 选择 data的第1个元素为arr的第一个元素,即:arr[0] = data[0];
2) 在data第一个元素之后的其它元素中,选取其余的 m – 1个数,这是一个上述问题的子问题,递归即可。
3) 依次选择 data的第 2 到 n – m + 1元素作为起始点,再执行1、2步骤。
4) 递归算法过程中的 m = 0 时,输出 arr 的所有元素。

C++ 代码如下:

template <typename T>
void computeAllChoices(std::vector<T> &data, int n, int outLen, int startIndex, int m, int *arr, int arrIndex)
{
    if(m == 0)
    {   
         for (int i = 0; i < outLen; i++)   
         {
            std::cout << arr[i] << "\t";
         }
         std::cout << std::endl; 

         return;
    }

    int endIndex = n - m;
    for(int i=startIndex; i<=endIndex; i++)
    {
        arr[arrIndex] = data[i];
        computeAllChoices(data, n, outLen, i+1, m-1, arr, arrIndex+1);
    }
}

测试代码如下:

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> data;
    for(int i = 0; i < 6; i++)
    {
        data.push_back(i+1);
    }

    int arr[3];

    computeAllChoices(data, data.size(), 3, 0, 3, arr, 0);

    return 0;
}
这里写图片描述

输出结果:

参考:
http://blog.csdn.net/wumuzi520/article/details/8087501#comments

点这里可以跳转到人工智能网站