From: Adam Shelly <adam.shelly@...>
Date: 2008-07-02T05:53:35+09:00
Subject: Re: how to - quickly make permutations?

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