[ruby-core:63108] Re: [ruby-trunk - Bug #9932] [Open] Permutation - Segment fault

On Wed, Jun 11, 2014 at 1:12 PM, <[e-mail]> wrote:

> Execute the following program with the inputs
>
>
> ######################################################################################
> # hash.rb
>
> t = gets.chomp.to_i
>
> def hash str
>         res = str.count "A"
>         if str.size > 1
>                 s1 = str[0..(str.size/2 - 1)]
>                 s2 = str[(str.size/2)..-1]
> #p "#{s1}, #{str}"
>                 res += [hash(s1), hash(s2)].max
>         end
>
>         res
> end
> #puts hash("AAEAAE")
>
> t.times do |x|
>         a = gets.chomp.to_i
>         e = gets.chomp.to_i
>         v = gets.chomp.to_i
>
>         pos = ("A"*a + "E"*e).split('').permutation.map(&:join).uniq
>
>         r = 0
>
>         pos.each do |y|
>                 r += 1 if(hash(y)==v)
>         end
>
>         puts (r % 1000000007)
> end
>
>
> ######################################################################################
>
> $ ruby hash.rb
> $ 1
> $ 234234
> $ 224
> $ 754674567
>
> Then the follwing error is produced
>
>
This looks a lot like a solution to a programming contest problem. Can you
provide a link to the problem statement?

The number of permutations you are asking for is humongous: (234234 + 224)!
which, if my calculations are right, is between 10 ** 1157233 and 10 **
1157234. There won't be a computer that can calculate and store that many
permutations for a long time (if ever).

Peter