How to - quickly make permutations?

ruby-talk
1

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

2

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

3

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

···

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

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

4

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| } 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-forum.com/\.

5

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-forum.com/\.

6

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

···

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

7

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

It runs into biiig performance issues for n >> size, and worse it does
not use inject :wink:
look at these benchmarks

···

On Tue, Jul 1, 2008 at 11:29 AM, Max Williams <toastkid.williams@gmail.com> wrote:

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) :frowning:

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.blogspot.com/

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

8

Robert Dober wrote:

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

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-forum.com/\.

9

-------- 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 :wink:

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_ext_mf@gmx

10

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 :frowning:

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

···

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 :wink:

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

11

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-forum.com/\.

12

Here's an alternate implementation using the "bankers order" algorithm from
http://applied-math.org/subset.pdf, and some timings using Robert's
program - for small samples they are similar, but this algorithm
scales better. (Unfortunately, it still brings my machine to its
knees on 50/10)

···

On 7/1/08, Robert Dober <robert.dober@gmail.com> wrote:

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 :wink:
>
> 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,
I stopped the program after 15 minutes :(.

==========================
def adam( n, size)
  r=
  a = Array.new(n+1){0}
  size.times{|sz|
    while (a[sz+1]<1)
      r<< (a-[0]) #.sort
      a[i=0]+=1
      a[i+=1]+=1 while (a[i] > n-i )
      (a[i-1]=a[i]+1; i-=1)while (i>0)
    end
  }
  r
end

C:\code\quiz>subsetsRubyTalk.rb 10 5 100
Rehearsal ------------------------------------------
robert 1.563000 0.000000 1.563000 ( 1.641000)
adam 1.516000 0.047000 1.563000 ( 1.562000)
--------------------------------- total: 3.126000sec

             user system total real
robert 1.562000 0.016000 1.578000 ( 1.578000)
adam 1.515000 0.015000 1.530000 ( 1.531000)

C:\code\quiz>subsetsRubyTalk.rb 20 5 10
Rehearsal ------------------------------------------
robert 49.984000 0.109000 50.093000 ( 50.858000)
adam 7.282000 0.093000 7.375000 ( 7.375000)
------------------------------- total: 232.078000sec

             user system total real
robert 46.344000 0.156000 46.500000 ( 46.608000)
adam 3.234000 0.047000 3.281000 ( 3.281000)

-Adam

13

gem install permutation

it's *super* fast.

a @ http://codeforpeople.com/

···

On Jul 1, 2008, at 8:15 AM, Max Williams wrote:

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

--
we can deny everything, except that we have the possibility of being better. simply reflect on that.
h.h. the 14th dalai lama

14

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

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

Max,

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-forum.com/\.

an alternative approach is simulated annealing ... it makes use of "jumping" in a
space of parameters, where the jumps are initially quite big, but get smaller as your solution gets better.
In this way, in nature, liquids that get cooled to crystals achieve very low energy configurations if cooled
slowly...
There's an implementation for Ruby using GSL

http://rb-gsl.rubyforge.org/siman.html

In your case, you could use a vector of 50 entries for the columns, each entry determining whether that column
is in your subset at hand or not.
In addition to that, you need a function that measures the quality of your solution, i.e. calculates the overlap.
As the value of the vector entries is changed by the Iterator function implemented in Ruby-gsl when it jumps in the
configuration space, you could say, "column i is in my subset, if the entry is positive, and otherwise not",
then calculate the overlap resulting from that collection of subsets using the Set class,say, and then decide whether a lot of overlap is good or bad for your solution.

The number of solutions to check is certainly far smaller than iterating through all subsets...

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_ext_mf@gmx

15

1. I believe 50/10 is over ten billion long.
2. robert and all: thanks

3. A tolerably inefficient approach is to just take the column with the
most remaining folks each time
until you have covered everyone:

    uncovered_list =[everyone]
    while ( uncovered-list.length > 0 )
         a= the column containing the longest list of folks not yet
covered;
         uncovered_list -= a
         columns.map!{|e| e-a}
   end

···

On Tue, Jul 1, 2008 at 4:53 PM, Adam Shelly <adam.shelly@gmail.com> wrote:

On 7/1/08, Robert Dober <robert.dober@gmail.com> wrote:
> 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 :wink:
> >
> > 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,
> I stopped the program after 15 minutes :(.
>

Here's an alternate implementation using the "bankers order" algorithm from
http://applied-math.org/subset.pdf, and some timings using Robert's
program - for small samples they are similar, but this algorithm
scales better. (Unfortunately, it still brings my machine to its
knees on 50/10)

def adam( n, size)
r=
a = Array.new(n+1){0}
size.times{|sz|
   while (a[sz+1]<1)
     r<< (a-[0]) #.sort
     a[i=0]+=1
     a[i+=1]+=1 while (a[i] > n-i )
     (a[i-1]=a[i]+1; i-=1)while (i>0)
   end
}
r
end

C:\code\quiz>subsetsRubyTalk.rb 10 5 100
Rehearsal ------------------------------------------
robert 1.563000 0.000000 1.563000 ( 1.641000)
adam 1.516000 0.047000 1.563000 ( 1.562000)
--------------------------------- total: 3.126000sec

            user system total real
robert 1.562000 0.016000 1.578000 ( 1.578000)
adam 1.515000 0.015000 1.530000 ( 1.531000)

C:\code\quiz>subsetsRubyTalk.rb 20 5 10
Rehearsal ------------------------------------------
robert 49.984000 0.109000 50.093000 ( 50.858000)
adam 7.282000 0.093000 7.375000 ( 7.375000)
------------------------------- total: 232.078000sec

            user system total real
robert 46.344000 0.156000 46.500000 ( 46.608000)
adam 3.234000 0.047000 3.281000 ( 3.281000)

-Adam

16

ara.t.howard wrote:

gem install permutation

it's *super* fast.

thanks - i looked at that but couldn't see how to only get distinct
subsets, ie to not get [1,2,3], [1,3,2], [3,1,2] etc in the same result
set. I was probably being a bit dumb though...i had just got back from
glastonbury when i was having a go :slight_smile:

···

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

17

Axel Etzold wrote:

an alternative approach is simulated annealing ... it makes use of
"jumping" in a
space of parameters, where the jumps are initially quite big, but get
smaller as your solution gets better.

..

There's an implementation for Ruby using GSL

http://rb-gsl.rubyforge.org/siman.html

Thanks axel - i was thinking that some sort of 'homing in' approach
might be better but couldn't work out how to go about it. I'll have a
look at this.

···

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

18

If you find it hard to define your "steps", you should try a genetic
algorithm aproach, using an array of 50 elements (representing if each
column is on the solution or not), and a function that measures the
fitness (how good is that combination).

Initially you create 100 random boolean arrays, select the best 20,
mix them in some way, for instance you could use the first half of one
array and the last half of another, or swaping a number of pairs of
columns in a single array (mutation), to create the remaining 80, and
repeat the process until your best candidate is good enough.

Of course the numbers can be tuned and will affect the efficience of
the program.

Lucas.

···

On Jul 1, 12:04 pm, Max Williams <toastkid.willi...@gmail.com> wrote:

Thanks axel - i was thinking that some sort of 'homing in' approach
might be better but couldn't work out how to go about it. I'll have a
look at this.