10

F＃での要素の組み合わせの最もエレガントでシンプルな実装に関するもう1つの質問。

入力要素のすべての組み合わせ（リストまたはシーケンス）を返す必要があります。最初の引数は、組み合わせの要素の数です。

例えば：

comb 2 [1;2;2;3];;
[[1;2]; [1;2]; [1;3]; [2;2]; [2;3]; [2;3]]
4

8 に答える 8

12

sspよりも簡潔で高速なソリューションが1つあります。

let rec comb n l = 
    match n, l with
    | 0, _ -> [[]]
    | _, [] -> []
    | k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs
于 2009-08-05T07:42:01.170 に答える
6 
let rec comb n l =
  match (n,l) with
  | (0,_) -> [[]]
  | (_,[]) -> []
  | (n,x::xs) ->
      let useX = List.map (fun l -> x::l) (comb (n-1) xs)
      let noX = comb n xs
      useX @ noX
于 2009-08-03T13:31:36.433 に答える
1

KVBの答えのより簡潔なバージョンがあります：

let rec comb n l =
  match (n,l) with
    | (0,_) -> [[]]
    | (_,[]) -> []
    | (n,x::xs) ->
      List.flatten [(List.map (fun l -> x::l) (comb (n-1) xs)); (comb n xs)]
于 2009-08-04T16:10:03.010 に答える
1

受け入れられた答えは、ツリーの再帰に精通している場合、ゴージャスですぐに理解できます。優雅さが求められていたので、この長い休眠中の糸を開くことはやや不必要に思えます。

ただし、より簡単な解決策が求められました。反復アルゴリズムは、私には単純に見えることがあります。さらに、パフォーマンスは品質の指標として言及されており、反復プロセスは再帰プロセスよりも高速な場合があります。

次のコードは末尾再帰であり、反復プロセスを生成します。24個の要素のリストからサイズ12の組み合わせを計算するには、3分の1の時間が必要です。

let combinations size aList = 
    let rec pairHeadAndTail acc bList = 
        match bList with
        | [] -> acc
        | x::xs -> pairHeadAndTail (List.Cons ((x,xs),acc)) xs
    let remainderAfter = aList |> pairHeadAndTail [] |> Map.ofList
    let rec comboIter n acc = 
        match n with
        | 0 -> acc
        | _ -> 
            acc
            |> List.fold (fun acc alreadyChosenElems ->
                match alreadyChosenElems with
                | [] -> aList //Nothing chosen yet, therefore everything remains.
                | lastChoice::_ -> remainderAfter.[lastChoice]
                |> List.fold (fun acc elem ->
                    List.Cons (List.Cons (elem,alreadyChosenElems),acc)
                ) acc
            ) []
            |> comboIter (n-1)
    comboIter size [[]]

反復プロセスを可能にする考え方は、最後に選択された要素のマップを残りの使用可能な要素のリストに事前に計算することです。このマップはに保存されremainderAfterます。

コードは簡潔ではなく、叙情的な韻律や韻律にも準拠していません。

于 2016-06-01T17:51:08.970 に答える
1

シーケンス式を使用した単純な実装。個人的には、シーケンス式は他のより密度の高い関数よりもわかりやすいと感じることがよくあります。

let combinations (k : int) (xs : 'a list) : ('a list) seq =
    let rec loop (k : int) (xs : 'a list) : ('a list) seq = seq {
        match xs with
        | [] -> ()
        | xs when k = 1 -> for x in xs do yield [x]
        | x::xs ->
            let k' = k - 1
            for ys in loop k' xs do
                yield x :: ys
            yield! loop k xs }
    loop k xs
    |> Seq.filter (List.length >> (=)k)
于 2016-09-25T14:19:02.100 に答える
1

離散数学とその応用から取られた方法。結果は、配列に格納されている組み合わせの順序付きリストを返します。そして、インデックスは1ベースです。

let permutationA (currentSeq: int []) (n:int) (r:int): Unit = 
    let mutable i = r
    while currentSeq.[i - 1] = n - r + i do
        i <- (i - 1)
    currentSeq.[i - 1] <- currentSeq.[i - 1] + 1
    for j = i + 1 to r do
        currentSeq.[j - 1] <- currentSeq.[i - 1] + j - i   
    ()
let permutationNum (n:int) (r:int): int [] list =
    if n >= r then
        let endSeq = [|(n-r+1) .. n|]
        let currentSeq: int [] = [|1 .. r|]
        let mutable resultSet: int [] list = [Array.copy currentSeq];
        while currentSeq <> endSeq do
            permutationA currentSeq n r
            resultSet <- (Array.copy currentSeq) :: resultSet
        resultSet
    else
        []

このソリューションはシンプルで、ヘルパー関数は一定のメモリを消費します。

于 2017-04-18T03:11:53.413 に答える
0

わかりました、テールの組み合わせは少し異なるアプローチです（ライブラリ関数を使用せずに）

let rec comb n lst =
    let rec findChoices = function
      | h::t -> (h,t) :: [ for (x,l) in findChoices t -> (x,l) ]
      | []   -> []
    [ if n=0 then yield [] else
            for (e,r) in findChoices lst do
                for o in comb (n-1) r do yield e::o  ]
于 2009-08-05T10:39:08.737 に答える
0

私の解決策は簡潔で効果的ではありませんが（直接再帰は使用されません）、すべての組み合わせを完全に返します（現在、ペアのみ、2つのリストのタプルを返すことができるようにfilterOutを拡張する必要がありますが、少し後で実行されます）。 

let comb lst =
    let combHelper el lst =
        lst |> List.map (fun lstEl -> el::[lstEl])
    let filterOut el lst =
        lst |> List.filter (fun lstEl -> lstEl <> el)
    lst |> List.map (fun lstEl -> combHelper lstEl (filterOut lstEl lst)) |> List.concat

コーム[1;2;3; 4]は次を返します：[[1; 2]; [1; 3]; [1; 4]; [2; 1]; [2; 3]; [2; 4]; [3; 1]; [3; 2]; [3; 4]; [4; 1]; [4; 2]; [4; 3]]

于 2009-08-04T17:00:48.650 に答える