From: Frederick Cheung <frederick.cheung@...>
Date: 2008-07-01T07:13:06+09:00
Subject: Re: how to - quickly make permutations?


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