Kết hợp các yếu tố trang nhã nhất trong F #

Question

Một câu hỏi khác về việc triển khai phần tử đơn giản và thanh lịch nhất trong F #.

Nó phải trả về tất cả các kết hợp của các yếu tố đầu vào (một trong hai danh sách hoặc chuỗi). Đối số đầu tiên là số phần tử kết hợp.

Ví dụ:

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

Answer 1

Một ít chính xác và nhanh hơn nhiều giải pháp hơn 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

Có nhiều phiên bản consise của câu trả lời KVB của:

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

Giải pháp của tôi là ít ngắn gọn, ít hiệu quả (altho, không đệ quy trực tiếp được sử dụng) nhưng nó trully trả về tất cả các kết hợp (hiện tại chỉ có cặp, cần phải mở rộng filterOut để nó có thể trả về một tuple của hai danh sách, sẽ làm ít sau).

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 

lược [1; 2; 3; 4] sẽ trở lại: [[1; 2]; [1; 3]; [1; 4]; [2; 1]; [2; 3]; [2; 4]; [3; 1]; [3; 2]; [3; 4]; [4; 1]; [4; 2]; [4; 3]]

Answer 5

Ok, kết hợp chỉ đuôi cách tiếp cận hơi khác (mà không sử dụng các chức năng thư viện)

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 ] 

Answer 6

Câu trả lời được chấp nhận là tuyệt đẹp và nhanh chóng dễ hiểu nếu bạn đã quen với việc đệ quy cây. Kể từ khi thanh lịch đã được tìm kiếm, mở chủ đề này không hoạt động lâu có vẻ hơi không cần thiết.

Tuy nhiên, giải pháp đơn giản hơn đã được yêu cầu. Các thuật toán lặp lại đôi khi có vẻ đơn giản hơn đối với tôi. Hơn nữa, hiệu suất đã được đề cập như một chỉ số về chất lượng, và các quá trình lặp lại đôi khi nhanh hơn các đệ quy.

Đoạn mã sau là đệ quy đuôi và tạo ra một quá trình lặp lại. Nó đòi hỏi một phần ba thời gian để tính toán các kết hợp của kích thước 12 từ một danh sách 24 yếu tố.

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

Ý tưởng cho phép quy trình lặp lại là tính toán trước một bản đồ của phần tử đã chọn cuối cùng vào danh sách các phần tử còn lại còn lại. Bản đồ này được lưu trữ trong remainderAfter.

Mã không súc tích, cũng không phù hợp với đồng hồ trữ tình và vần điệu.

Answer 7

A Ngây thơ triển khai bằng biểu thức trình tự. Cá nhân tôi thường cảm thấy các biểu thức trình tự dễ làm theo hơn các hàm dày đặc khác.

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 8

Phương thức lấy từ Toán học rời rạc và ứng dụng của nó. Kết quả trả về một danh sách thứ tự các kết hợp được lưu trữ trong mảng. Và chỉ mục dựa trên 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 
     [] 

Giải pháp này là chức năng đơn giản và trợ giúp chi phí bộ nhớ không đổi.