معظم مجموعات أنيقة من العناصر في 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

وهناك نسخة أكثر إيجازا من كفس الجواب:

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

والجواب المقبول هو رائع ومفهومة بسرعة إذا كنت معتادا العودية شجرة. منذ وطلب الأناقة، وفتح هذا الموضوع نائمة لفترة طويلة يبدو غير ضروري إلى حد ما.

ولكن، طلب حل أبسط ل. يبدو خوارزميات متكررة وأحيانا أكثر بساطة بالنسبة لي. وعلاوة على ذلك، ذكر الأداء كمؤشر للجودة، والعمليات التكرارية هي أسرع أحيانا من تلك متكررة.

والتعليمة البرمجية التالية الذيل عودي ويقوم بإنشاء عملية تكرارية. فهو يتطلب ثلث كمية من الوقت لحساب مجموعات من حجم 12 من لائحة 24 عناصر.

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

A <م> السذاجة التنفيذ باستخدام تسلسل التعبير. شخصيا وكثيرا ما أشعر تسلسل العبارات هي أسهل لمتابعة من وظائف أكثر كثافة أخرى.

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

وبلدي الحل هو أقل موجزة، وأقل فعالية (ثابتة، لا العودية المباشرة المستخدمة) ولكنه يعود تروللي كافة تركيبات (حاليا أزواج فقط، تحتاج إلى تمديد filterOut لذلك يمكن إرجاع الصفوف (tuple) من قائمتين، لن يفعل شيئا يذكر لاحقا).

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

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  ]