4

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

AAA
AAB
ABB
BBB
BBC
BCC
CCC
CCA
CAA
ABC

我要解决的具体问题要简单一些。我正在做一个二十一点游戏作为 F# 中的练习（我之前已经发布过这个）。我计算手牌值的方法是使用卡片可能值列表的列表。除了 A 之外的所有卡片在列表中都有一个项目，但 A 可以是 1 或 11。我在那篇文章中提出的实现产生了很多冗余。例如，3 个 ace 将创建一个类似的列表[3; 13; 13; 13; 23; 23; 23; 33]。现在我正在获取最终列表并运行它Distinct()，但感觉有点像黑客。

将这一切联系在一起，A 的潜在值 (1, 11) 构成了字母表，而手中 A 的数量决定了数字的数量。在这种情况下，我希望算法提出以下模式：

1, 1 
1, 11
11,11

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

编辑

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

4

5 回答 5

3

嗯，在您的情况下，（1）计算 A（让计数为 N）然后（2）生成可能的总值作为列表理解就足够了

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

...但是您会在 F# 中表达这一点。无需进行实际的排列、组合等。

于 2010-02-17T20:25:48.227 回答
2

这是 Thomas 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
    | [] -> () 
  }
于 2010-02-17T19:52:57.373 回答
2

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

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是所有连接工作发生的地方。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)
于 2010-02-17T22:58:48.680 回答
0

您可以递归地执行此操作。我正在用 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，那么您应该得到数学组合。

于 2010-02-17T19:35:15.173 回答
0

给定 {1,11} 的“字母表”，那么您基本上想要生成长度为n的所有“单词” ，其中n是 ace 的数量，这样所有的 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]

如果您不熟悉 Python 语法，请注意，括号[]表示一个列表，[1]*x表示创建一个新列表，该列表是 ; 的x副本的串联[1]。那是，

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

如果x = 3

于 2010-02-17T19:42:40.290 回答