From: Robert Dober <robert.dober@...>
Date: 2008-07-01T22:33:11+09:00
Subject: Re: how to - quickly make permutations?

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

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