8 people like it.

Combinations n choose k

given an array n generates all lists with k choices from n

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 

let n_choose_k n k = let rec choose lo  =
                         function
                         |0 -> [[]]
                         |i -> [for j in lo .. (Array.length n)-1 do
                                     for ks in choose (j+1) (i-1) do
                                       yield n.[j] :: ks ]
                     in choose 0  k                           
                         

(* example
n_choose_k [|'a' .. 'f'|] 4 ;;
Real: 00:00:00.000, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : char list list =
  [['a'; 'b'; 'c'; 'd']; ['a'; 'b'; 'c'; 'e']; ['a'; 'b'; 'c'; 'f'];
   ['a'; 'b'; 'd'; 'e']; ['a'; 'b'; 'd'; 'f']; ['a'; 'b'; 'e'; 'f'];
   ['a'; 'c'; 'd'; 'e']; ['a'; 'c'; 'd'; 'f']; ['a'; 'c'; 'e'; 'f'];
   ['a'; 'd'; 'e'; 'f']; ['b'; 'c'; 'd'; 'e']; ['b'; 'c'; 'd'; 'f'];
   ['b'; 'c'; 'e'; 'f']; ['b'; 'd'; 'e'; 'f']; ['c'; 'd'; 'e'; 'f']]
> 
*)
val n_choose_k : n:'a [] -> k:int -> 'a list list

Full name: Script.n_choose_k
val n : 'a []
val k : int
val choose : (int -> int -> 'a list list)
val lo : int
val i : int
val j : int
module Array

from Microsoft.FSharp.Collections
val length : array:'T [] -> int

Full name: Microsoft.FSharp.Collections.Array.length
val ks : 'a list

More information

Link:http://fssnip.net/fF
Posted:11 years ago
Author:isaiah perumalla
Tags: algorithms , combinations

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.