4 people like it.

Function to get all possible combinations

Function to get all possible combinations of list items. There are some Euler problems (like 77 & 78) to get total amounts. But e.g. for some card game implementations you will need the real items.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
//See examples:

//Input: ["a";"b"]
//Output: ["a"; "b"; "ab"]

//Input: ["a";"b";"c";"d"] 
//Output: ["a"; "b"; "c"; "d"; "ab"; "ac"; "ad"; "bc"; "bd"; "cd"; "bcd"; "abc"; "abd"; "acd"; "abcd"]

//Input: [1;2;5]
//Output: [1; 2; 5; 3; 6; 7; 8]

//Input: [2;3;8;12] 
//Output: [2; 3; 8; 12; 5; 10; 14; 11; 15; 20; 23; 13; 17; 22; 25]

//-----------------------------------------------------

let toDistinct mylist = (List.toSeq >> Seq.distinct >> Seq.toList) mylist;;

/// get combinations of sums
let rec recursivecombinations aggregate mylist = 
    match mylist with
    |[] -> []
    |h::t ->
        let tailpart = (toDistinct << recursivecombinations aggregate) t
        let headpart = t |> aggregate h
        let sums = headpart @ tailpart
        
        let recsums = match sums with
                        |[] -> []
                        |[x] -> [x]
                        | _ -> tailpart |> aggregate h
        sums @ recsums 

let combinations aggregate mylist = mylist @ recursivecombinations aggregate mylist |> toDistinct

//custom aggregate function, just sum here:
let inline sumfunction head = List.map (fun f ->head+f) 

//test:
//> combinations sumfunction ["a";"b";"c"];; 
//val it : string list = ["a"; "b"; "c"; "ab"; "ac"; "bc"; "abc"]

//> combinations sumfunction [1;2;3];; 
//val it : int list = [1; 2; 3; 4; 5; 6]
val toDistinct : mylist:'a list -> 'a list (requires equality)

Full name: Script.toDistinct
val mylist : 'a list (requires equality)
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val toSeq : list:'T list -> seq<'T>

Full name: Microsoft.FSharp.Collections.List.toSeq
module Seq

from Microsoft.FSharp.Collections
val distinct : source:seq<'T> -> seq<'T> (requires equality)

Full name: Microsoft.FSharp.Collections.Seq.distinct
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
val recursivecombinations : aggregate:('a -> 'a list -> 'a list) -> mylist:'a list -> 'a list (requires equality)

Full name: Script.recursivecombinations


 get combinations of sums
val aggregate : ('a -> 'a list -> 'a list) (requires equality)
val h : 'a (requires equality)
val t : 'a list (requires equality)
val tailpart : 'a list (requires equality)
val headpart : 'a list (requires equality)
val sums : 'a list (requires equality)
val recsums : 'a list (requires equality)
val x : 'a (requires equality)
val combinations : aggregate:('a -> 'a list -> 'a list) -> mylist:'a list -> 'a list (requires equality)

Full name: Script.combinations
val sumfunction : head:'a -> ('b list -> 'c list) (requires member ( + ))

Full name: Script.sumfunction
val head : 'a (requires member ( + ))
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val f : 'b (requires member ( + ))

More information

Link:http://fssnip.net/1Q
Posted:7 years ago
Author:Tuomas Hietanen
Tags: combination , list , math