logo标签列表

从n个元素中返回k个元素的所有组合算法

algorithmcombinations
642

我想编写一个函数，该函数接受字母数组作为参数以及要选择的这些字母的数量。

比如你提供了一个由8个字母组成的数组，并希望从中选择3个字母。那么你应该得到： 

8! / ((8 - 3)! * 3!) = 56

由3个字母组成的返回数组（或单词）。

4
编程语言有偏好吗？ - Jonathan Tran
9
你希望如何处理重复的字母？ - wcm
在PHP中，以下代码应该可以解决问题：https://dev59.com/D2855IYBdhLWcg3wilCD#8880362 - Kemal Dağ
@wcm 我在这里找不到处理重复字母的解决方案。我回答了一个需要重复（并需要C ++）的问题：https://dev59.com/ll0a5IYBdhLWcg3wxbHm - Jonathan Mee
这里有一篇简明的文章，提供了一个看起来很高效的C#实现：https://msdn.microsoft.com/zh-cn/library/aa289166(v=vs.71).aspx - Angelo
显示剩余4条评论
77个回答
5

使用Clojure版本：

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))
5
Array.prototype.combs = function(num) {

    var str = this,
        length = str.length,
        of = Math.pow(2, length) - 1,
        out, combinations = [];

    while(of) {

        out = [];

        for(var i = 0, y; i < length; i++) {

            y = (1 << i);

            if(y & of && (y !== of))
                out.push(str[i]);

        }

        if (out.length >= num) {
           combinations.push(out);
        }

        of--;
    }

    return combinations;
}
5
算法：
  • 从1数到2^n。
  • 将每个数字转换为其二进制表示。
  • 根据位置，将每个“on”位翻译为集合中的元素。

在C#中：

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
    
    var kElement = 2;
    
    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

为什么它有效？
一个n元素集合的子集与n位序列之间存在双射关系。
这意味着我们可以通过计算序列来确定有多少个子集。
例如，下面的四元素集合可以用{0,1} X {0, 1} X {0, 1} X {0, 1}（或2^4）不同的序列表示。
所以 - 我们只需要从1数到2^n，就能找到所有的组合。（我们忽略空集。）接下来，将数字转换为它们的二进制表示。然后用你的集合元素替换 'on' 位。
如果你只想要k个元素的结果，在k位上是 'on' 时才打印。
（如果你想要所有子集而不是长度为k的子集，请删除cnt/kElement部分。）
有关证明，请参见MIT免费课程《计算机科学数学基础》Lehman等人，第11.2.2节。
2
这个解决方案非常适合我。它迭代次数最少，因此非常快速。 - Steve Hibbert
通过将int转换为基于2进制的字符串表示，然后使用正则表达式来计算1的数量来计算位数实在是相当令人不快的。这远非“快速”。仅分配的数量就很疯狂。var cnt = System.Runtime.Intrinsics.X86.Popcnt.PopCount(i); - Alastair Maw
太好了！你提出了pop count，我当时并不知道。然而，这个想法仍然是有效的；在循环内改进常数时间计算是有益的。我会保留这个，因为它清晰地表达了观点。谢谢！ - jacoblambert
4

另一种使用 Python 实现的递归解决方案。

def combination_indicies(n, k, j = 0, stack = []):   
    if len(stack) == k:            
        yield list(stack)
        return
        
    for i in range(j, n):
        stack.append(i)
        for x in combination_indicies(n, k, i + 1, stack):            
            yield x
        stack.pop()  
        
list(combination_indicies(5, 3))

输出：

[[0, 1, 2],
 [0, 1, 3],
 [0, 1, 4],
 [0, 2, 3],
 [0, 2, 4],
 [0, 3, 4],
 [1, 2, 3],
 [1, 2, 4],
 [1, 3, 4],
 [2, 3, 4]]
4
这里有一种方法，可以从随机长度的字符串中获取指定大小的所有组合。类似于quinmars的解决方案，但适用于各种输入和k。
代码可以更改为环绕，即从输入'abcd'中获取'dab'，并且k=3。
public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}


//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

"abcde"的输出结果：

abc abd abe acd ace ade bcd bce bde cde

4

最终，这里是O'caml代码。从代码中可以看出算法...

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 []
;;
也许对骆驼来说很明显。特里·普拉切特声称它们是已知宇宙中最伟大的数学家。 - kuroi neko
4

简短的JavaScript版本（ES 5）

let combine = (list, n) =>
  n == 0 ?
    [[]] :
    list.flatMap((e, i) =>
      combine(
        list.slice(i + 1),
        n - 1
      ).map(c => [e].concat(c))
    );

let res = combine([1,2,3,4], 3);
res.forEach(e => console.log(e.join()));

1
你能否解释一下这个或者将其改成一个函数？我真的很难跟上或理解正在发生的事情。 - Altimus Prime
3
1
我很感兴趣，但链接已失效。 - Altimus Prime
3

这是我最近用Java编写的一段代码，它可以计算并返回从"outOf"个元素中选择"num"个元素的所有组合。

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}
3
一种简洁的JavaScript解决方案：
Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);
如果你将第16行从combi(1,toCombine);改为combi(0, ['']);，那么这个解决方案就适用于k=1。如原文所述，使用k=1调用会得到与k=2相同的结果。 - ericP
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接