-------- Original-Nachricht --------

Datum: Tue, 1 Jul 2008 02:58:51 +0900

Von: Max Williams <toastkid.williams@gmail.com>

An: ruby-talk@ruby-lang.org

Betreff: how to - quickly make permutations?

can anyone provide an elegant implementation for this method?

#gives all distinct combinations of numbers up to n, with maximum size

max_size

def permutations(n,max_size)

so, eg,

permutations(4,2)

=> [[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

permutations(4,3)

=> above + [[1,2,3],[1,2,4],[2,3,4]]

i'm guessing something recursive is the key but i can't quite work out

the best way.

thanks

max

--

Posted via http://www.ruby-forum.com/\.

Max,

what you are asking for in your examples is not a permutation, but rather the collection of

subsets of up to k elements.

Naming the elements as 0,...,n-1 , consider this example code

n=5

numbers=(0...2**n)

set_size=3

sets=

for number in numbers

res =("%b" % number).split(//) # get a binary representation of number, as an Array of '0' and '1'

res=[0]*(n-res.length)+res # fill '0' in at the beginning, as many as necessary

el_number=res.dup.grep(/1/).length # search for those elements that have set_size times '1' in them

temp=

if el_number<=set_size

res.each_with_index{|x,i|

if x=='1'; temp<<i; end

}

sets<<temp

end

end

p sets

Somebody else might make this more concise, but as it is after 11pm here, not me..

Best regards,

Axel

## ···

--

Psssst! Schon vom neuen GMX MultiMessenger gehört?

Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger