29 people like it.

All combinations of list elements

For a given list, find all possible combinations of elements of the list (not just k-combinations). The result is a list of lists with each element representing one combination. Order of elements is not taken into account.

 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: 
// This takes something like [1;2;3;4] and returns 
// [4][4; 3][4; 3; 2][4; 3; 2; 1][4; 3; 1][4; 2][4; 2; 1]
// [4; 1][3][3; 2][3; 2; 1][3; 1][2][2; 1][1] 

let allCombinations lst =
    let rec comb accLst elemLst =
        match elemLst with
        | h::t ->
            let next = [h]::List.map (fun el -> h::el) accLst @ accLst
            comb next t
        | _ -> accLst
    comb [] lst

// The output is in reverse order of creation of the list, 
// in order to avoid a second list concatenation. This can be
// changed in the function itself, or you can sort the result
// with the following.

let sortListList ls =
    let rec cmp lstA lstB =
        match lstA, lstB with
        | hA::tA, hB::tB when hA=hB -> cmp tA tB
        | hA::tA, hB::tB when hA<hB -> -1
        | hA::tA, hB::tB when hA>hB -> 1
        | [], [] -> 0
        | [], _ -> -1
        | _ -> 1
    List.map (fun l -> List.sort l) ls
    |> List.sortWith (fun a b -> cmp a b)
val allCombinations : lst:'a list -> 'a list list

Full name: Script.allCombinations
val lst : 'a list
val comb : ('b list list -> 'b list -> 'b list list)
val accLst : 'b list list
val elemLst : 'b list
val h : 'b
val t : 'b list
val next : 'b list list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  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 map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val el : 'b list
val sortListList : ls:'a list list -> 'a list list (requires comparison)

Full name: Script.sortListList
val ls : 'a list list (requires comparison)
val cmp : ('b list -> 'b list -> int) (requires comparison)
val lstA : 'b list (requires comparison)
val lstB : 'b list (requires comparison)
val hA : 'b (requires comparison)
val tA : 'b list (requires comparison)
val hB : 'b (requires comparison)
val tB : 'b list (requires comparison)
val l : 'a list (requires comparison)
val sort : list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sort
val sortWith : comparer:('T -> 'T -> int) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.sortWith
val a : 'a list (requires comparison)
val b : 'a list (requires comparison)
Next Version Raw view Test code New version

More information

Link:http://fssnip.net/2z
Posted:13 years ago
Author:Alexander Rautenberg
Tags: list , combinations