F#의 요소의 가장 우아한 조합

Question

F#에서 요소 조합의 가장 우아하고 간단한 구현에 대한 한 가지 더 질문.

입력 요소의 모든 조합 (목록 또는 시퀀스)을 반환해야합니다. 첫 번째 인수는 조합의 요소 수입니다.

예를 들어:

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

Answer 1

SSP보다 간결하고 더 빠른 솔루션 중 하나 :

let rec comb n l = 
    match n, l with
    | 0, _ -> [[]]
    | _, [] -> []
    | k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs

Answer 2

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

Answer 3

KVB의 답변에 대한 더 많은 Consise 버전이 있습니다.

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)]

Answer 4

허용 된 대답은 화려하고 트리 재귀에 익숙하다면 빠르게 이해할 수 있습니다. 우아함이 추구 되었기 때문에이 긴 휴면 실을 여는 것은 다소 불필요 해 보입니다.

그러나 더 간단한 솔루션을 요구했습니다. 반복 알고리즘은 때때로 나에게 더 간단 해 보입니다. 또한 성능은 품질의 지표로 언급되었으며, 반복 프로세스는 때때로 재귀적인 프로세스보다 빠릅니다.

다음 코드는 꼬리 재귀이며 반복 프로세스를 생성합니다. 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.

코드는 간결하지 않으며 서정적 미터와 운율을 준수하지도 않습니다.

Answer 5

ㅏ 순진한 시퀀스 표현식을 사용한 구현. 개인적으로 나는 종종 시퀀스 표현이 다른 더 조밀 한 기능보다 따르는 것이 더 쉽다고 생각합니다.

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)

Answer 6

가져온 방법 개별 수학 및 응용 프로그램. 결과는 배열에 저장된 순서 조합 목록을 반환합니다. 그리고 인덱스는 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
        []

이 솔루션은 간단하고 도우미 기능은 일정한 메모리 비용입니다.

Answer 7

내 솔루션은 간결하고 덜 효과적이지만 (Altho, 직접 재귀는 사용되지 않음) 모든 조합을 반환합니다 (현재 쌍 만 필터 아웃을 확장해야 두 개의 목록의 튜플을 반환 할 수 있으므로 나중에 거의 수행하지 않음).

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; 삼]; [1; 4]; [2; 1]; [2; 삼]; [2; 4]; [삼; 1]; [삼; 2]; [삼; 4]; [4; 1]; [4; 2]; [4; 삼]

Answer 8

좋아, 단지 꼬리 조합이 거의 다른 접근 방식 (라이브러리 기능을 사용하지 않고)

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  ]