From: jim finucane <jimrails@...>
Date: 2008-07-02T06:43:45+09:00
Subject: Re: how to - quickly make permutations?

------=_Part_7578_33214914.1214948799381
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

------=_Part_7578_33214914.1214948799381--