4

可能な値のセットと「桁」の数が与えられた場合、一意で順序付けられていない値のグループをすべて見つけたいと考えています。たとえば、A、B、C のアルファベットがあるとします。3 桁のすべての組み合わせは次のようになります。

AAA
AAB
ABB
BBB
BBC
BCC
CCC
CCA
CAA
ABC

私が解決しようとしている特定の問題は、もう少し単純です。F# の演習として BlackJack ゲームをやっています (これについては以前に投稿しました)。私がハンド値を計算する方法は、カードの可能な値のリストのリストを使用することです。エースを除くすべてのカードはリストに 1 つのアイテムを持っていますが、エースは 1 または 11 のいずれかです。その投稿で思いついた実装は、多くの冗長性を生成します。たとえば、3 つのエースは のようなリストを作成します[3; 13; 13; 13; 23; 23; 23; 33]。今、私は最終的なリストを取得して実行していDistinct()ますが、ちょっとしたハックのように感じます.

これをすべてまとめると、エースの潜在的な値 (1、11) がアルファベットを構成し、手のエースの数によって桁数が決まります。この場合、アルゴリズムで次のパターンを考え出す必要があります。

1, 1 
1, 11
11,11

ここで動的プログラミングが登場する可能性があることを何かが教えてくれますが、適切な用語が不足しているため、少し立ち往生しています。どんな助けでも大歓迎です。

編集

価値があるのは、特定の問題に対するより単純な解決策があることを私は認識していますが、関数型プログラミングの演習であるため、一般性が私の目標の 1 つです。

4

5 に答える 5

3

うーん、あなたの場合、（1）エースを数え（カウントをNとする）、（2）可能な合計値をリスト内包表記として生成するだけで十分です

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

...ただし、F# でそれを表現します。実際の順列、組み合わせなどを行う必要はありません。

于 2010-02-17T20:25:48.227 に答える
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 に答える
2

これは、F# に対する Thomas Pornin の回答の半忠実な翻訳です。これが を使用した素朴なアプローチよりも特にパフォーマンスが高いとは思わないことに注意してください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 に答える