[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

how to - quickly make permutations?

Max Williams

6/30/2008 5:59:00 PM

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-....
17 Answers

Axel Etzold

6/30/2008 9:17:00 PM

0


-------- 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-....

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/mult...

Frederick Cheung

6/30/2008 10:13:00 PM

0


On 30 Jun 2008, at 18:58, Max Williams wrote:

> can anyone provide an elegant implementation for this method?
>

Quick bash at it:

def subsets(n, max_k)
results = []
1.upto(max_k) {|k| results << permutations(n,k, results.last)}
results
end

def permutations(n,k,previous_iteration=nil)
return (1..n).collect {|x| [x]} if k == 1
previous_iteration ||= permutations(n,k-1)
(1..n).inject([]) do |result, to_add|
result.concat( previous_iteration.inject([]) do |memo, perm|
memo << (perm + [to_add]).sort unless perm.include?(to_add)
memo
end)
end.uniq
end

This is recursive with a shortcut: since we are anyway accumulating
the previous results, there is no point calculating them over and over
again (if not p(n,1) is calculated max_k times, p(n,2) is calculated
max_k - 1 times etc...


Fred

> #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-....
>

jim finucane

7/1/2008 12:47:00 AM

0

[Note: parts of this message were removed to make it a legal post.]

each new element tries to double the size of the list

def permutations(n,max_size)
result =[[]]
Array.new(n).fill{|k|k+1}.each{|i|result +=result.collect{|x|
x.length<max_size ? x +=[i] : [] } }
return result.uniq - [[]]
end

or

def permutations (n,max_size)
result = [[]]
for i in 1..n
result +=result.collect{|x| x.length<max_size ? x +=[i] : [] }
end
return result.uniq - [[]]
end



On Mon, Jun 30, 2008 at 6:13 PM, Frederick Cheung <
frederick.cheung@gmail.com> wrote:

>
> On 30 Jun 2008, at 18:58, Max Williams wrote:
>
> can anyone provide an elegant implementation for this method?
>>
>>
> Quick bash at it:
>
> def subsets(n, max_k)
> results = []
> 1.upto(max_k) {|k| results << permutations(n,k, results.last)}
> results
> end
>
> def permutations(n,k,previous_iteration=nil)
> return (1..n).collect {|x| [x]} if k == 1
> previous_iteration ||= permutations(n,k-1)
> (1..n).inject([]) do |result, to_add|
> result.concat( previous_iteration.inject([]) do |memo, perm|
> memo << (perm + [to_add]).sort unless perm.include?(to_add)
> memo
> end)
> end.uniq
> end
>
> This is recursive with a shortcut: since we are anyway accumulating the
> previous results, there is no point calculating them over and over again (if
> not p(n,1) is calculated max_k times, p(n,2) is calculated max_k - 1 times
> etc...
>
>
> Fred
>
>
> #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-....
>>
>>
>
>

Max Williams

7/1/2008 9:20:00 AM

0

Frederick Cheung wrote:

>
> This is recursive with a shortcut: since we are anyway accumulating
> the previous results, there is no point calculating them over and over
> again (if not p(n,1) is calculated max_k times, p(n,2) is calculated
> max_k - 1 times etc...
>
>
> Fred

Thanks everyone - Fred, this is perfect, having the different sized
groups seperated into their own arrays is actually even better for me
than what i specified. Thanks.

Axel - you're right, i did mean subsets. oops.


thanks again,
max
--
Posted via http://www.ruby-....

Max Williams

7/1/2008 9:29:00 AM

0

jim finucane wrote:

> def permutations (n,max_size)
> result = [[]]
> for i in 1..n
> result +=result.collect{|x| x.length<max_size ? x +=[i] : [] }
> end
> return result.uniq - [[]]
> end

Jim, this wins the elegance prize i think! It's almost magical...i
can't quite get my head round it. :)

--
Posted via http://www.ruby-....

Robert Dober

7/1/2008 1:33:00 PM

0

On Tue, Jul 1, 2008 at 11:29 AM, Max Williams
<toastkid.williams@gmail.com> wrote:
> jim finucane wrote:
<snip>
> Jim, this wins the elegance prize i think! It's almost magical...i
> can't quite get my head round it. :)
It runs into biiig performance issues for n >> size, and worse it does
not use inject ;)
look at these benchmarks
==================================
require 'benchmark'
def robert n, size
(1..n).inject([[]]){
|perms, ele|
perms.concat( perms.map{|perm| perm+[ele]} ).
uniq.delete_if{|p| p.size > size}
}
end

def jim n, size
result = [[]]
for i in 1..n
result +=result.collect{|x| x.length<size ? x +=[i] : [] }
end
result.uniq - [[]]
end

N,S,R = ARGV.map{|x| x.to_i}
Benchmark::bmbm do | report |
report.report("robert") do
R.times do
robert N, S
end
end

report.report("jim") do
R.times do
jim N, S
end
end
end
=============================

528/28 > ruby perms.rb 4 2 10000
Rehearsal ------------------------------------------
robert 1.328000 0.032000 1.360000 ( 1.359000)
jim 1.000000 0.015000 1.015000 ( 1.016000)
--------------------------------- total: 2.375000sec

user system total real
robert 1.344000 0.032000 1.376000 ( 1.375000)
jim 1.016000 0.031000 1.047000 ( 1.047000)
=======================================
529/29 > ruby perms.rb 10 2 100
Rehearsal ------------------------------------------
robert 0.141000 0.000000 0.141000 ( 0.141000)
jim 0.484000 0.016000 0.500000 ( 0.500000)
--------------------------------- total: 0.641000sec

user system total real
robert 0.141000 0.000000 0.141000 ( 0.141000)
jim 0.453000 0.000000 0.453000 ( 0.453000)
========================================

530/30 > ruby perms.rb 20 2 10
Rehearsal ------------------------------------------
robert 0.125000 0.000000 0.125000 ( 0.125000)
jim 53.922000 0.656000 54.578000 ( 54.610000)
-------------------------------- total: 54.703000sec

user system total real
robert 0.140000 0.000000 0.140000 ( 0.141000)
jim 57.750000 0.531000 58.281000 ( 58.297000)
========================================

of course if n and size are large there is not much that can be done
on the exponential runtime
as O(n!) is just O(e**n) :(

531/31 > ruby perms.rb 20 15 1
Rehearsal ------------------------------------------
robert 95.469000 0.312000 95.781000 ( 95.890000)
jim 95.703000 0.266000 95.969000 ( 96.219000)
------------------------------- total: 191.750000sec

user system total real
robert 95.422000 0.281000 95.703000 ( 96.141000)
jim 91.843000 0.172000 92.015000 ( 92.141000)

HTH
Robert

--
http://ruby-smalltalk.blo...

---
AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF

Max Williams

7/1/2008 1:50:00 PM

0

Robert Dober wrote:

> It runs into biiig performance issues for n >> size, and worse it does
> not use inject ;)

That's good to know actually, my real numbers are likely to be n =
50ish, max_size = 10ish. Right in the pain spot. So maybe elegant
wasn't quite the right word...elegant in design but not operation?

--
Posted via http://www.ruby-....

Axel Etzold

7/1/2008 2:02:00 PM

0


-------- Original-Nachricht --------
> Datum: Tue, 1 Jul 2008 22:50:05 +0900
> Von: Max Williams <toastkid.williams@gmail.com>
> An: ruby-talk@ruby-lang.org
> Betreff: Re: how to - quickly make permutations?

> Robert Dober wrote:
>
> > It runs into biiig performance issues for n >> size, and worse it does
> > not use inject ;)

Max,

>
> That's good to know actually, my real numbers are likely to be n =
> 50ish, max_size = 10ish. Right in the pain spot. So maybe elegant
> wasn't quite the right word...elegant in design but not operation?
>

what are you trying to do ? The number of subsets is enormous... maybe there's
an easier way to achieve your goal.

Best regards,

Axel
--
GMX startet ShortView.de. Hier findest Du Leute mit Deinen Interessen!
Jetzt dabei sein: http://www.shortview.de/wasistshortview.php?mc=sv_...

Robert Dober

7/1/2008 2:14:00 PM

0

On Tue, Jul 1, 2008 at 3:50 PM, Max Williams
<toastkid.williams@gmail.com> wrote:
> Robert Dober wrote:
>
>> It runs into biiig performance issues for n >> size, and worse it does
>> not use inject ;)
>
> That's good to know actually, my real numbers are likely to be n =
> 50ish, max_size = 10ish. Right in the pain spot. So maybe elegant
Oh that will be tough in Ruby, if I have some time I will try to
optimize this, inject is known to be slow, but one cannot expect a
speedup more than factor 2 or 3 by using each instead. Thus looking at
the performance right now,
I do not have much hope :(

I stopped the program after 15 minutes :(.


But there was a binding to a c framework for doing these things fast,
does anybody remember?
Cheers
Robert

Max Williams

7/1/2008 2:15:00 PM

0

Axel Etzold wrote:

> what are you trying to do ? The number of subsets is enormous... maybe
> there's
> an easier way to achieve your goal.
>
> Best regards,
>
> Axel

Maybe there is...it's a little program to help my wife out with a bit of
data processing. I have a bunch of columns (50ish) that each list a
group of people. The people overlap between columns and we want to look
at what happens to the total degree of overlap when groups of columns
are removed. So, i was going to try removing each column and calculate
the total overlap for each case. Then, remove every possible pair of
columns, recalculate for each case. Then, every possible trio of
columns, etc. And keep going until the number of subsets to test starts
to get impractical. Which might happen quite quickly as you suggest.
--
Posted via http://www.ruby-....