我可以更有效地找到给定大小的所有多集？

Question

给定一组可能值和一些“数字，”我想找到值的每一个独特的，无序的分组。例如，假设你有A，B的字母表，C.所有的3位数字组合将是：

AAA
AAB
ABB
BBB
BBC
BCC
CCC
CCA
CAA
ABC

我试图解决的具体问题是有点简单。我做了二十一点游戏在F＃的锻炼（的我已经张贴了关于这个之前）。我手计算值的方法是用卡的可能值的列表的列表。除王牌所有卡在列表中的单个项目，但王牌可以是1个或11.我在后与上前的实施产生大量的冗余。例如，3个ace球将创建一个像[3; 13; 13; 13; 23; 23; 23; 33]列表。现在，我走的是最终名单，并通过Distinct()运行它，但感觉就像一个黑客攻击的一位。

搭售此一起，所述王牌电位值（1，11）构成了字母，并在手ACE的数量决定的位数。在这种情况下，我希望的算法来与以下模式：

1, 1 
1, 11
11,11

东西告诉我，动态规划可能会在这里发挥作用，但我缺乏适当的术语在离开我有点卡住了。任何帮助，将不胜感激。

修改

有关它的价值，我知道，有具体的问题要简单得多的解决方案，但作为函数式编程练习，共性是我的目标之一。

Answer 1

此问题是一个很好的谜。它应该是代码高尔夫球。 :)

let rec permute list count =
    seq {
        match list with
        | y::ys when count > 0 -> 
            for n in permute list (count - 1) do
                yield Seq.map (fun li -> y::li) n
            yield Seq.concat (permute ys count)
        | y::ys -> yield Seq.singleton []
        | [] -> ()
    }

埃斯实施例

permute ["1";"11"] 2
|> Seq.concat
|> Seq.iter (printfn "%A")

["1"; "1"]
["1"; "11"]
["11"; "11"]

ABC实施例

permute ["A";"B";"C"] 3
|> Seq.concat
|> Seq.iter (printfn "%A");;

["A"; "A"; "A"]
["A"; "A"; "B"]
["A"; "A"; "C"]
["A"; "B"; "B"]
["A"; "B"; "C"]
["A"; "C"; "C"]
["B"; "B"; "B"]
["B"; "B"; "C"]
["B"; "C"; "C"]
["C"; "C"; "C"]

y::li是所有concating工作情况。你可以用y + li取代它，如果你想为所有的字符串。你也必须yield Seq.singleton一个"" insted的[]的

<强>性能更新：

这个问题很好memoizes并给出memoized为无小事的情况下更好的性能。

let memoize2 f = 
    let cache = Dictionary<_,_>()
    fun x y -> 
        let ok, res = cache.TryGetValue((x, y))
        if ok then 
            res 
        else 
            let res = f x y
            cache.[(x, y)] <- res
            res

// permute ["A";"B";"C"] 400 |> Seq.concat |> Seq.length |> printf "%A"       
// Real: 00:00:07.740, CPU: 00:00:08.234, GC gen0: 118, gen1: 114, gen2: 4
let rec permute =
    memoize2(fun list count ->
        seq {
            match list with
            | y::ys when count > 0 -> 
                for n in permute list (count - 1) do
                    yield Seq.map (fun li -> y::li) n |> Seq.cache
                yield Seq.concat (permute ys count)
            | y::ys -> yield Seq.singleton []
            | [] -> ()
        } |> Seq.cache)

我还memoized KVB溶液和它执行比我快15％。

// permute ["A";"B";"C"] 400 |> Seq.length |> printf "%A"
// Real: 00:00:06.587, CPU: 00:00:07.046, GC gen0: 87, gen1: 83, gen2: 4
let rec permute = 
    memoize2 (fun list n ->
        match n with
            | 0 -> Seq.singleton []
            | n -> 
                seq {
                    match list with 
                    | x::xs ->  
                        yield! permute list (n-1) |> Seq.map (fun l -> x::l)
                        yield! permute xs n
                    | [] -> () 
                } |> Seq.cache)

Answer 2

嗯，你的情况就足够了（1）计数王牌（让计数为N），然后（2）产生的可能的合计值作为列表解析

{ i * 11 + (N - i) * 1 }   |   0 <= i <= N }

...但是你会表示，在F＃。不需要做实际的排列，组合等。

Answer 3

下面是托马斯Pornin的答案F＃的半忠实的翻译。请注意，我不希望这是特别比使用distinct天真的方法更好的性能，但它绝对整洁：

let rec splits l = function
| [] -> Seq.empty
| x::xs -> seq {
    yield [],x,xs
    for l,y,ys in splits xs do
      yield x::l,y,ys
  }

let rec combs s = function
| 0 -> Seq.singleton []
| n -> seq {
    for _,x,rest in splits s do
      for l in combs (x::rest) (n-1) do
        yield x::l
  }

或者，在gradbot的溶液的变化，而不是：

let rec permute list = function
| 0 -> Seq.singleton []
| n -> seq { 
    match list with 
    | x::xs ->  
        yield! permute list (n-1) |> Seq.map (fun l -> x::l)
        yield! permute xs n
    | [] -> () 
  }

Answer 4

您可以递归做到这一点。我用Java编写这一点;我的F＃是不够的：

static void genCombInternal(int num, int[] base,
    int min, int max, Collection<int[]> dst)
{
    if (num == 0) {
        dst.add(base);
        return;
    }
    for (int i = min; i <= max; i ++) {
        int[] nb = new int[base.length + 1];
        System.arraycopy(base, 0, nb, 0, base.length);
        nb[base.length] = i;
        genCombInternal(num - 1, nb, i, max, dst);
    }
}

static Collection<int[]> genComb(int num, int min, int max)
{
    Collection<int[]> d = new ArrayList<int[]>();
    genCombInternal(num, new int[0], min, max, d);
    return d;
}

此代码是完全未经测试。如果它的工作原理，然后调用genComb(num, min, max)应该产生num整数的所有的“组合”范围min到max（含），如没有两个返回的组合是相等的保存排序。

这是非常接近，其产生“真”的组合的代码。诀窍是在每个步骤中允许的整数：如果您在递归调用改变i成i+1，那么你应该得到的数学组合

Answer 5

由于您的{1,11}“字母表”，那么你基本上要产生长度名词后，所有的“话”，其中的名词是尖子数量，使得所有1的（0或更多）是向左和所有11的的是在正确的。该排序并不重要，这只是一个简单的方法，通过你所关心的组合进行迭代。

在的Python：

n = 3 # number of aces
hands = []
for i in range(0,n+1):
    hands.append([1] * (n-i) + [11] * i)

或者甚至更简单的在Python：

hands = [[1]*(n-i) + [11]*i for i in range(0,n+1)]

要得到每手总得分：

scores = [sum(hand) for hand in hands]

的情况下，不熟悉，括号[]表示的列表，并[1]*x装置创建新的列表即x的[1]拷贝级联上Python语法的说明;即，

[1] * x ==  [1,1,1] 

如果x = 3