代码之家 › 专栏 › 技术社区 › Cogwheel

我能更有效地找到给定尺寸的所有多集吗?

dynamic-programming f# algorithm

Cogwheel · 技术社区 · 15 年前

给定一组可能的值和一些“数字”,我想查找每个唯一的、无序的值分组。例如,假设您有一个字母表A、B、C。所有3位数字的组合都是:

AAA
AAB
ABB
BBB
BBC
BCC
CCC
CCA
CAA
ABC

我想解决的具体问题要简单一点。我在F做21点游戏作为练习#( I've posted about this before )我计算手值的方法是列出卡片的可能值。除ace以外的所有卡在列表中都有一个项目,但ace可以是1或11。我在那篇文章中提出的实现产生了大量的冗余。例如,3个ace将创建一个类似于 [3; 13; 13; 13; 23; 23; 23; 33] . 现在我要把最后一份清单拿出来,把它看完 Distinct() 但感觉有点像黑客。

把这些联系在一起,ace的潜在值(1,11)构成了字母表,手上ace的数量决定了数字的数量。在这种情况下,我希望算法能想出以下模式:

1, 1 
1, 11
11,11

有件事告诉我 Dynamic Programming 可能在这里起作用,但我缺乏适当的术语,这让我有点陷入困境。任何帮助都将不胜感激。

编辑

值得一提的是,我知道对于特定的问题有更简单的解决方案,但是作为函数式编程的练习,通用性是我的目标之一。

5 回复 | 直到 15 年前

gradbot 15 年前

这个问题是个很好的脑筋急转弯。应该是编码高尔夫。:)

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 []
        | [] -> ()
    }

ACE示例

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 是所有具体工作发生的地方。你可以换成 y + li 如果你只想要弦的话。你也必须 yield Seq.singleton 安 "" 安装在 []

性能更新:

这个问题可以很好地记忆,并且对于非琐碎的情况提供了更好的性能记忆。

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)

我还记忆了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)

Antti Huima 15 年前

嗯,在您的情况下,这就足够了:(1)计算ace(让count为n),然后(2)生成可能的总值作为列表理解

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

…不过,你可以用f来表达。不需要做实际的排列,组合等。

kvb 15 年前

以下是托马斯·波宁对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
    | [] -> () 
  }

Thomas Pornin 15 年前

你可以递归地做。我是用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 在递归调用中,您应该得到数学组合。

awesomo 15 年前

如果你的“字母表”是1,11,那么你基本上想要生成所有长度的“单词”。 n 在哪里 n 是ace的数目,1的所有(0或更多)都在左边,11的所有都在右边。排序并不重要,这只是一种简单的方法,可以迭代您关心的组合。

在蟒蛇中:

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]

关于python语法的注释,以防您不熟悉,括号 [] 表示一个列表和 [1]*x 意味着创建一个新的列表,它是 x 复印件 [1] 也就是说,

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

如果 x = 3