说了这么多，做了这么多，这就是奥卡姆的代码。 算法是显而易见的代码..

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;

这是一个简单的JS解决方案:

function getAllCombinations(n, k, f1) { indexes = Array(k); for (let i =0; i< k; i++) { indexes[i] = i; } var total = 1; f1(indexes); while (indexes[0] !== n-k) { total++; getNext(n, indexes); f1(indexes); } return {total}; } function getNext(n, vec) { const k = vec.length; vec[k-1]++; for (var i=0; i<k; i++) { var currentIndex = k-i-1; if (vec[currentIndex] === n - i) { var nextIndex = k-i-2; vec[nextIndex]++; vec[currentIndex] = vec[nextIndex] + 1; } } for (var i=1; i<k; i++) { if (vec[i] === n - (k-i - 1)) { vec[i] = vec[i-1] + 1; } } return vec; } let start = new Date(); let result = getAllCombinations(10, 3, indexes => console.log(indexes)); let runTime = new Date() - start; console.log({ result, runTime });

也许我错过了重点(你需要的是算法，而不是现成的解决方案)，但看起来scala已经开箱即用了(现在):

def combis(str:String, k:Int):Array[String] = {
  str.combinations(k).toArray 
}

使用这样的方法:

  println(combis("abcd",2).toList)

会产生:

  List(ab, ac, ad, bc, bd, cd)

这是一个c++解决方案，我提出使用递归和位移位。它也可以在C语言中工作。

void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

你可以在这里找到这是如何工作的解释。

我可以给出这个问题的递归Python解决方案吗?

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

使用示例:

>>> len(list(choose_iter("abcdefgh",3)))
56

我喜欢它的简洁。

我知道这个问题已经有很多答案了，但我想在JavaScript中添加我自己的贡献，它由两个函数组成——一个生成原始n元素集的所有可能不同的k子集，另一个使用第一个函数生成原始n元素集的幂集。

下面是这两个函数的代码:

//Generate combination subsets from a base set of elements (passed as an array). This function should generate an
//array containing nCr elements, where nCr = n!/[r! (n-r)!].

//Arguments:

//[1] baseSet :     The base set to create the subsets from (e.g., ["a", "b", "c", "d", "e", "f"])
//[2] cnt :         The number of elements each subset is to contain (e.g., 3)

function MakeCombinationSubsets(baseSet, cnt)
{
    var bLen = baseSet.length;
    var indices = [];
    var subSet = [];
    var done = false;
    var result = [];        //Contains all the combination subsets generated
    var done = false;
    var i = 0;
    var idx = 0;
    var tmpIdx = 0;
    var incr = 0;
    var test = 0;
    var newIndex = 0;
    var inBounds = false;
    var tmpIndices = [];
    var checkBounds = false;

    //First, generate an array whose elements are indices into the base set ...

    for (i=0; i<cnt; i++)

        indices.push(i);

    //Now create a clone of this array, to be used in the loop itself ...

        tmpIndices = [];

        tmpIndices = tmpIndices.concat(indices);

    //Now initialise the loop ...

    idx = cnt - 1;      //point to the last element of the indices array
    incr = 0;
    done = false;
    while (!done)
    {
    //Create the current subset ...

        subSet = [];    //Make sure we begin with a completely empty subset before continuing ...

        for (i=0; i<cnt; i++)

            subSet.push(baseSet[tmpIndices[i]]);    //Create the current subset, using items selected from the
                                                    //base set, using the indices array (which will change as we
                                                    //continue scanning) ...

    //Add the subset thus created to the result set ...

        result.push(subSet);

    //Now update the indices used to select the elements of the subset. At the start, idx will point to the
    //rightmost index in the indices array, but the moment that index moves out of bounds with respect to the
    //base set, attention will be shifted to the next left index.

        test = tmpIndices[idx] + 1;

        if (test >= bLen)
        {
        //Here, we're about to move out of bounds with respect to the base set. We therefore need to scan back,
        //and update indices to the left of the current one. Find the leftmost index in the indices array that
        //isn't going to  move out of bounds with respect to the base set ...

            tmpIdx = idx - 1;
            incr = 1;

            inBounds = false;       //Assume at start that the index we're checking in the loop below is out of bounds
            checkBounds = true;

            while (checkBounds)
            {
                if (tmpIdx < 0)
                {
                    checkBounds = false;    //Exit immediately at this point
                }
                else
                {
                    newIndex = tmpIndices[tmpIdx] + 1;
                    test = newIndex + incr;

                    if (test >= bLen)
                    {
                    //Here, incrementing the current selected index will take that index out of bounds, so
                    //we move on to the next index to the left ...

                        tmpIdx--;
                        incr++;
                    }
                    else
                    {
                    //Here, the index will remain in bounds if we increment it, so we
                    //exit the loop and signal that we're in bounds ...

                        inBounds = true;
                        checkBounds = false;

                    //End if/else
                    }

                //End if 
                }               
            //End while
            }
    //At this point, if we'er still in bounds, then we continue generating subsets, but if not, we abort immediately.

            if (!inBounds)
                done = true;
            else
            {
            //Here, we're still in bounds. We need to update the indices accordingly. NOTE: at this point, although a
            //left positioned index in the indices array may still be in bounds, incrementing it to generate indices to
            //the right may take those indices out of bounds. We therefore need to check this as we perform the index
            //updating of the indices array.

                tmpIndices[tmpIdx] = newIndex;

                inBounds = true;
                checking = true;
                i = tmpIdx + 1;

                while (checking)
                {
                    test = tmpIndices[i - 1] + 1;   //Find out if incrementing the left adjacent index takes it out of bounds

                    if (test >= bLen)
                    {
                        inBounds = false;           //If we move out of bounds, exit NOW ...
                        checking = false;
                    }
                    else
                    {
                        tmpIndices[i] = test;       //Otherwise, update the indices array ...

                        i++;                        //Now move on to the next index to the right in the indices array ...

                        checking = (i < cnt);       //And continue until we've exhausted all the indices array elements ...
                    //End if/else
                    }
                //End while
                }
                //At this point, if the above updating of the indices array has moved any of its elements out of bounds,
                //we abort subset construction from this point ...
                if (!inBounds)
                    done = true;
            //End if/else
            }
        }
        else
        {
        //Here, the rightmost index under consideration isn't moving out of bounds with respect to the base set when
        //we increment it, so we simply increment and continue the loop ...
            tmpIndices[idx] = test;
        //End if
        }
    //End while
    }
    return(result);
//End function
}


function MakePowerSet(baseSet)
{
    var bLen = baseSet.length;
    var result = [];
    var i = 0;
    var partialSet = [];

    result.push([]);    //add the empty set to the power set

    for (i=1; i<bLen; i++)
    {
        partialSet = MakeCombinationSubsets(baseSet, i);
        result = result.concat(partialSet);
    //End i loop
    }
    //Now, finally, add the base set itself to the power set to make it complete ...

    partialSet = [];
    partialSet.push(baseSet);
    result = result.concat(partialSet);

    return(result);
    //End function
}

我用集合["a"， "b"， "c"， "d"， "e"， "f"]作为基本集进行了测试，并运行代码以产生以下幂集:

[]
["a"]
["b"]
["c"]
["d"]
["e"]
["f"]
["a","b"]
["a","c"]
["a","d"]
["a","e"]
["a","f"]
["b","c"]
["b","d"]
["b","e"]
["b","f"]
["c","d"]
["c","e"]
["c","f"]
["d","e"]
["d","f"]
["e","f"]
["a","b","c"]
["a","b","d"]
["a","b","e"]
["a","b","f"]
["a","c","d"]
["a","c","e"]
["a","c","f"]
["a","d","e"]
["a","d","f"]
["a","e","f"]
["b","c","d"]
["b","c","e"]
["b","c","f"]
["b","d","e"]
["b","d","f"]
["b","e","f"]
["c","d","e"]
["c","d","f"]
["c","e","f"]
["d","e","f"]
["a","b","c","d"]
["a","b","c","e"]
["a","b","c","f"]
["a","b","d","e"]
["a","b","d","f"]
["a","b","e","f"]
["a","c","d","e"]
["a","c","d","f"]
["a","c","e","f"]
["a","d","e","f"]
["b","c","d","e"]
["b","c","d","f"]
["b","c","e","f"]
["b","d","e","f"]
["c","d","e","f"]
["a","b","c","d","e"]
["a","b","c","d","f"]
["a","b","c","e","f"]
["a","b","d","e","f"]
["a","c","d","e","f"]
["b","c","d","e","f"]
["a","b","c","d","e","f"]

只要复制粘贴这两个函数“原样”，你就有了提取n元素集的不同k子集所需的基本知识，并生成该n元素集的幂集(如果你愿意的话)。

我并不是说这很优雅，只是说它在经过大量的测试(并在调试阶段将空气变为蓝色:)之后可以工作。