From: Jeff de Vries <jdevries@...>
Date: 2002-12-11T12:00:00+09:00
Subject: Re: Implementing combinatorics

hint ...

 binary         set elements
0 = 0 0 0    [           ] = []
1 = 0 0 1    [         3 ] = [3]
2 = 0 1 0    [     2     ] = [2]
3 = 0 1 1    [     2   3 ] = [2,3]
4 = 1 0 0    [ 1         ] = [1]
5 = 1 0 1    [ 1       3 ] = [1,3]
6 = 1 1 0    [ 1   2     ] = [1,2]
7 = 1 1 1    [ 1   2   3 ] = [1,2,3]


Wai-Sun Chia wrote:

> Rubyists,
> Has anyone implemented combinatorics on Ruby before?
> i.e.
> Given a list;
>     L = [x1,x2,x3....xn]
> What is the total number of combinations that we can produce?
>
> Rudimentary discrete math combinatorics theory tells us that it is: 2**n
>
> e.g. L = [1,2,3]
>
> []
> [1]
> [1,2]
> [1,2,3]
> [1,3]
> [2]
> [2,3]
> [3]
>
> Some questions that I have:
> 1. Has anybody implemented this in Ruby? How would you do it?
> 2. Any advantage for an iterative algorithm over a recursive one?
> 3. Is Ruby really suitable for these type of work as opposed to say a 
> Lisp variant, like Ocaml?
>
> TIA.
>