Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > I need a more efficient algorithm for this problem.

Reply
Thread Tools

I need a more efficient algorithm for this problem.

 
 
Sam Kong
Guest
Posts: n/a
 
      01-23-2007
Hi Rob,

Rob Biedenharn wrote:

> These are Catalan numbers which you can learn more about on Wikipedia
> [1] or MathWorld[2]. If you just need to know the number of
> solutions, both references give a formula.
>
> -Rob
>
> [1] http://en.wikipedia.org/wiki/Catalan_number
> [2] http://mathworld.wolfram.com/CatalanNumber.html


Thank you for the information.
That's almost what I was looking for.
Catalan numbers are for combinatorics not for partitions in that the
order of numbers is significant in combinatorics.
Anyway, the documents will give me hints.
And at least, now I know that Mathematica provides the function.
I can install Mathematica if I need to.

I'm trying to solve math problems in projecteuler.net .
They are very helpful when you want to apply your coding skills to
solving problems.
(Similar to ruby quiz but more math-oriented.)
Some problems require math knowledge, though. (Brute force won't help.)
It's fun.
I hope more Ruby programmers will join it and challenge.
It shows staticstics which compares languages.
There are not many ruby users there yet.

Thanks again.

Sam


 
Reply With Quote
 
 
 
 
Martin DeMello
Guest
Posts: n/a
 
      01-24-2007
On 1/24/07, Sam Kong <(E-Mail Removed)> wrote:
>
> Thank you for the information.
> That's almost what I was looking for.
> Catalan numbers are for combinatorics not for partitions in that the
> order of numbers is significant in combinatorics.


You want the Stirling Numbers of the second kind, I think

http://en.wikipedia.org/wiki/Stirling_number

martin

 
Reply With Quote
 
 
 
 
Sean O'Halpin
Guest
Posts: n/a
 
      01-24-2007
Hi Sam,

You might also find
http://www.ics.uci.edu/~eppstein/PAD...rPartitions.py
interesting.

Regards,
Sean

 
Reply With Quote
 
Thomas Hafner
Guest
Posts: n/a
 
      01-24-2007
"Sam Kong" <(E-Mail Removed)> wrote/schrieb <(E-Mail Removed) om>:

> Yes. That's much better than the code I posted.


Unfortunately my ``solution'' of
<(E-Mail Removed)> is none, because it does not
report all combinations, sorry. Here's a better approach:

#\\\
$cache = {}

def parts(s,u)
u0 = [s,u].min
if u0 < 1
[]
else
i = (s-1)*s/2+u0-1
$cache[i] ||
begin
a = []
u0.downto(1) do |n|
r = s - n
if (r > 0)
parts(r,n).each do |elem|
a.push([n, elem])
end
else
a.push([n])
end
end
$cache[i] = a
a
end
end
end

def part(n)
parts(n,n).map{|x| x.flatten}
end
#///

> Actually I've already tried that.
> But the problem is that even the cached version is not fast enough for
> my purpose.


On my PC evaluation of parts(45) takes 11.53 seconds without cache,
and 2.96 seconds with cache. But it's definitely not appropriate for
calculating parts(1000). But you've already mentioned, that you need
only the number of combinations, not the combinations itself. Many
years ago at University I've been told that it's often better to solve
the problem directly. Solving an arbitrary intermediate problem can
make things worse or even impossible. Here the intermediate problem is
``calculate the list of combinations''. Some others are (numerics):

- Don't calculate the inverse of a matrix. The original problem is
probably a linear system of equations. Just solve that.

- Never calculate the characteristic polynomial just to find the
roots. Solve the Eigenvalue-problem directly.

Regards
Thomas
 
Reply With Quote
 
Sam Kong
Guest
Posts: n/a
 
      01-24-2007


On Jan 24, 1:00 am, "Martin DeMello" <(E-Mail Removed)> wrote:
> On 1/24/07, Sam Kong <(E-Mail Removed)> wrote:
>
>
>
> > Thank you for the information.
> > That's almost what I was looking for.
> > Catalan numbers are for combinatorics not for partitions in that the
> > order of numbers is significant in combinatorics.You want the Stirling Numbers of the second kind, I think

>
> http://en.wikipedia.org/wiki/Stirling_number


Wow, finally I've got what I've been looking for.
Thanks.

Sam


 
Reply With Quote
 
Sam Kong
Guest
Posts: n/a
 
      01-24-2007


On Jan 24, 3:45 am, Thomas Hafner <(E-Mail Removed)> wrote:
> "Sam Kong" <(E-Mail Removed)> wrote/schrieb <(E-Mail Removed) om>:
>
> > Yes. That's much better than the code I posted.Unfortunately my ``solution'' of

> <(E-Mail Removed)> is none, because it does not
> report all combinations, sorry. Here's a better approach:
>
> #\\\
> $cache = {}
>
> def parts(s,u)
> u0 = [s,u].min
> if u0 < 1
> []
> else
> i = (s-1)*s/2+u0-1
> $cache[i] ||
> begin
> a = []
> u0.downto(1) do |n|
> r = s - n
> if (r > 0)
> parts(r,n).each do |elem|
> a.push([n, elem])
> end
> else
> a.push([n])
> end
> end
> $cache[i] = a
> a
> end
> end
> end
>
> def part(n)
> parts(n,n).map{|x| x.flatten}
> end
> #///
>
> > Actually I've already tried that.
> > But the problem is that even the cached version is not fast enough for
> > my purpose.On my PC evaluation of parts(45) takes 11.53 seconds without cache,

> and 2.96 seconds with cache. But it's definitely not appropriate for
> calculating parts(1000). But you've already mentioned, that you need
> only the number of combinations, not the combinations itself. Many
> years ago at University I've been told that it's often better to solve
> the problem directly. Solving an arbitrary intermediate problem can
> make things worse or even impossible. Here the intermediate problem is
> ``calculate the list of combinations''. Some others are (numerics):
>
> - Don't calculate the inverse of a matrix. The original problem is
> probably a linear system of equations. Just solve that.
>
> - Never calculate the characteristic polynomial just to find the
> roots. Solve the Eigenvalue-problem directly.


Yes, you said it right.
I didn't know that the combination grows that fast.
Now I know what's right approach to the solution.

Thanks.

Sam

>
> Regards
> Thomas



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Efficient Integer Comparison Algorithm JThangiah Java 10 03-06-2008 06:27 PM
Most efficient algorithm for matching Timasmith Java 36 02-16-2007 11:02 PM
efficient therm-2-bin algorithm vishallko31@gmail.com VHDL 6 06-13-2006 04:48 PM
efficient algorithm for customized set_difference KK C++ 1 12-21-2005 05:58 AM
Need help in finding an efficient algorithm robertday5@gmail.com Perl Misc 3 01-06-2005 10:35 AM



Advertisments