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

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

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

------=_Part_3122_1550131.1214873371594--