Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   I need a more efficient algorithm for this problem. (http://www.velocityreviews.com/forums/t837463-i-need-a-more-efficient-algorithm-for-this-problem.html)

 Sam Kong 01-23-2007 05:07 AM

I need a more efficient algorithm for this problem.

Hi,

I have a question which is not necessarily a ruby-related one.
Anyway, I'm using Ruby for it.

To make 5 by adding 2 more more natural numbers, there are different 6
ways.

1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
2 + 2 + 1
3 + 1 + 1
3 + 2
4 + 1

In array form, you may express it like:

[1,1,1,1,1]
[2,1,1,1]
[2,2,1]
[3,1,1]
[3,2]
[4,1]

Is there a general and efficient way to get the arrays?
For example,

set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]

I came up with a mutual recursive solution but it's not very efficient.
(Probably because it's recursive, which Ruby is not very good at.)
I can't make it efficient for big numbers.
I tried to use a cache but it didn't help much enough.

def set n
return [[1, 1]] if n == 2
result = []
(1...n).each do |i|
subset = get_subset(n - i, i)
subset.each do |j|
result << [i] + j
end
end
result
end

def get_subset n, max
result = (n <= max) ? [[n]] : []
result += (set(n).select { |i| i.all? { |j| j <= max } })
end

Do you know a good solution to this problem?
Also, is there a mathematical or algorithmic term for this problem like
combinations and permutations?

Thanks.

Sam

 M. Edward (Ed) Borasky 01-23-2007 06:01 AM

Re: I need a more efficient algorithm for this problem.

Sam Kong wrote:
> Hi,
>
> I have a question which is not necessarily a ruby-related one.
> Anyway, I'm using Ruby for it.
>
> To make 5 by adding 2 more more natural numbers, there are different 6
> ways.
>
> 1 + 1 + 1 + 1 + 1
> 2 + 1 + 1 + 1
> 2 + 2 + 1
> 3 + 1 + 1
> 3 + 2
> 4 + 1
>
>
> In array form, you may express it like:
>
> [1,1,1,1,1]
> [2,1,1,1]
> [2,2,1]
> [3,1,1]
> [3,2]
> [4,1]
>
>
> Is there a general and efficient way to get the arrays?
> For example,
>
> set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]
>
> I came up with a mutual recursive solution but it's not very efficient.
> (Probably because it's recursive, which Ruby is not very good at.)
> I can't make it efficient for big numbers.
> I tried to use a cache but it didn't help much enough.
>
> def set n
> return [[1, 1]] if n == 2
> result = []
> (1...n).each do |i|
> subset = get_subset(n - i, i)
> subset.each do |j|
> result << [i] + j
> end
> end
> result
> end
>
> def get_subset n, max
> result = (n <= max) ? [[n]] : []
> result += (set(n).select { |i| i.all? { |j| j <= max } })
> end
>
>
> Do you know a good solution to this problem?
> Also, is there a mathematical or algorithmic term for this problem like
> combinations and permutations?
>
> Thanks.
>
> Sam
>

I think it's called "partitions" and I think it's covered somewhere in
Knuth's "Art Of Computer Programming". That's where I'd check first, anyhow.

--
M. Edward (Ed) Borasky, FBG, AB, PTA, PGS, MS, MNLP, NST, ACMC(P)

If God had meant for carrots to be eaten cooked, He would have given rabbits fire.

 stuart yarus 01-23-2007 06:04 AM

Re: I need a more efficient algorithm for this problem.

On 1/22/07, Sam Kong <sam.s.kong@gmail.com> wrote:
> Hi,
>
> I have a question which is not necessarily a ruby-related one.
> Anyway, I'm using Ruby for it.
>
> To make 5 by adding 2 more more natural numbers, there are different 6
> ways.
>
> 1 + 1 + 1 + 1 + 1
> 2 + 1 + 1 + 1
> 2 + 2 + 1
> 3 + 1 + 1
> 3 + 2
> 4 + 1
>
>
> In array form, you may express it like:
>
> [1,1,1,1,1]
> [2,1,1,1]
> [2,2,1]
> [3,1,1]
> [3,2]
> [4,1]
>
>
> Is there a general and efficient way to get the arrays?
> For example,
>
> set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]
>
> I came up with a mutual recursive solution but it's not very efficient.
> (Probably because it's recursive, which Ruby is not very good at.)
> I can't make it efficient for big numbers.
> I tried to use a cache but it didn't help much enough.
>
> def set n
> return [[1, 1]] if n == 2
> result = []
> (1...n).each do |i|
> subset = get_subset(n - i, i)
> subset.each do |j|
> result << [i] + j
> end
> end
> result
> end
>
> def get_subset n, max
> result = (n <= max) ? [[n]] : []
> result += (set(n).select { |i| i.all? { |j| j <= max } })
> end
>
>
> Do you know a good solution to this problem?
> Also, is there a mathematical or algorithmic term for this problem like
> combinations and permutations?

There are a few terms: partition function, number partitioning,
integer partition,...

There is a moderately large literature on the topic. Try googling.
Wikipedia has some good introductory articles, like
<http://en.wikipedia.org/wiki/Integer_partition>, and a number of
references.

>
> Thanks.
>
> Sam
>
>
>

--
Stuart Yarus

<syarus at gmail dot com>

 James Edward Gray II 01-23-2007 02:13 PM

Re: I need a more efficient algorithm for this problem.

On Jan 22, 2007, at 11:10 PM, Sam Kong wrote:

> To make 5 by adding 2 more more natural numbers, there are different 6
> ways.
>
> 1 + 1 + 1 + 1 + 1
> 2 + 1 + 1 + 1
> 2 + 2 + 1
> 3 + 1 + 1
> 3 + 2
> 4 + 1

> Is there a general and efficient way to get the arrays?

You said you have a recursive solution. The first step to optimizing
recursion is to make sure you aren't doing a bunch of unneeded work.
For example, generating all the combinations and then removing
duplicates is too much work. Instead, we want to make sure we
recursively generate just one set of numbers:

def partition(largest, rest = Array.new, &block)
block.call([largest] + rest)
(rest.first || 1).upto(largest / 2) do |i|
partition(largest - i, [i] + rest, &block)
end
end

partition(5) { |nums| p nums }
# >> [5]
# >> [4, 1]
# >> [3, 1, 1]
# >> [2, 1, 1, 1]
# >> [1, 1, 1, 1, 1]
# >> [2, 2, 1]
# >> [3, 2]

The optimization for recursion is to eliminate the recursion. You
can always unroll recursive code into an iterative solution:

def partition(num)
partitions = [[num]]

until partitions.empty?
current = partitions.shift

yield current

largest = current.shift
(current.first || 1).upto(largest / 2) do |i|
partitions << Array[largest - i, i, *current.dup]
end
end
end

partition(5) { |nums| p nums }
# >> [5]
# >> [4, 1]
# >> [3, 2]
# >> [3, 1, 1]
# >> [2, 2, 1]
# >> [2, 1, 1, 1]
# >> [1, 1, 1, 1, 1]

I translated these examples from the book Higher-Order Perl and, in
case you are curious, wrote more about them here:

http://blog.grayproductions.net/arti.../31/iterators-
chapters-4-and-5

Hope that helps.

James Edward Gray II

 Sam Kong 01-23-2007 05:40 PM

Re: I need a more efficient algorithm for this problem.

Hi James,

James Edward Gray II wrote:
> On Jan 22, 2007, at 11:10 PM, Sam Kong wrote:
>
> > To make 5 by adding 2 more more natural numbers, there are different 6
> > ways.
> >
> > 1 + 1 + 1 + 1 + 1
> > 2 + 1 + 1 + 1
> > 2 + 2 + 1
> > 3 + 1 + 1
> > 3 + 2
> > 4 + 1

>
> > Is there a general and efficient way to get the arrays?

>
> You said you have a recursive solution. The first step to optimizing
> recursion is to make sure you aren't doing a bunch of unneeded work.
> For example, generating all the combinations and then removing
> duplicates is too much work. Instead, we want to make sure we
> recursively generate just one set of numbers:
>
> def partition(largest, rest = Array.new, &block)
> block.call([largest] + rest)
> (rest.first || 1).upto(largest / 2) do |i|
> partition(largest - i, [i] + rest, &block)
> end
> end
>
> partition(5) { |nums| p nums }
> # >> [5]
> # >> [4, 1]
> # >> [3, 1, 1]
> # >> [2, 1, 1, 1]
> # >> [1, 1, 1, 1, 1]
> # >> [2, 2, 1]
> # >> [3, 2]
>
> The optimization for recursion is to eliminate the recursion. You
> can always unroll recursive code into an iterative solution:

Right. But some recursions are harder to unroll than others.^^

>
> def partition(num)
> partitions = [[num]]
>
> until partitions.empty?
> current = partitions.shift
>
> yield current
>
> largest = current.shift
> (current.first || 1).upto(largest / 2) do |i|
> partitions << Array[largest - i, i, *current.dup]
> end
> end
> end
>
> partition(5) { |nums| p nums }
> # >> [5]
> # >> [4, 1]
> # >> [3, 2]
> # >> [3, 1, 1]
> # >> [2, 2, 1]
> # >> [2, 1, 1, 1]
> # >> [1, 1, 1, 1, 1]
>
> I translated these examples from the book Higher-Order Perl and, in
> case you are curious, wrote more about them here:
>
> http://blog.grayproductions.net/arti.../31/iterators-
> chapters-4-and-5

I just bookmarked it.

>
> Hope that helps.

Yes. It helped a lot.
>
> James Edward Gray II

Thank you very much.
Also, I thank others who replied to my question.

Sam

 Thomas Hafner 01-23-2007 06:07 PM

Re: I need a more efficient algorithm for this problem.

"Sam Kong" <sam.s.kong@gmail.com> wrote/schrieb <1169528870.482644.83900@11g2000cwr.googlegroups.c om>:

> Do you know a good solution to this problem?

I let you decide if mine is a good solution:

#\\\
\$cache = []

def parts(s)
if s < 1
[]
else
\$cache[s] ||
begin
a = []
s.downto(1) do |n|
k = s / n
left = [].fill(n, (0 .. (k-1)))
r = s - k * n
if (r > 0)
right = parts(r)
right.each do |elem|
a.push([left,elem])
end
else
a.push(left)
end
end
\$cache[s] = a
end
end
end

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

pp part(8)
#///

Regards
Thomas

 James Edward Gray II 01-23-2007 07:07 PM

Re: I need a more efficient algorithm for this problem.

On Jan 23, 2007, at 11:40 AM, Sam Kong wrote:

> Hi James,
>
> James Edward Gray II wrote:
>> You can always unroll recursive code into an iterative solution:

>
> Right. But some recursions are harder to unroll than others.^^

You're not the first person to say that to me, but I still don't
believe it. ;)

Think of it this way. All recursion is doing for you is managing the
call stack. You can always do that yourself.

Just use an Array for the stack and put all the local variable in
it. That's always works for unrolling recursion. Period.

Frequently you can get away with much less too. In my example
earlier in this thread, note that I didn't even need all the local
values to unroll it.

It just takes practice to think this way.

James Edward Gray II

 Sam Kong 01-23-2007 07:34 PM

Re: I need a more efficient algorithm for this problem.

James Edward Gray II wrote:
> On Jan 23, 2007, at 11:40 AM, Sam Kong wrote:
>
> > Hi James,
> >
> > James Edward Gray II wrote:
> >> You can always unroll recursive code into an iterative solution:

> >
> > Right. But some recursions are harder to unroll than others.^^

>
> You're not the first person to say that to me, but I still don't
> believe it. ;)
>
> Think of it this way. All recursion is doing for you is managing the
> call stack. You can always do that yourself.
>
> Just use an Array for the stack and put all the local variable in
> it. That's always works for unrolling recursion. Period.
>
> Frequently you can get away with much less too. In my example
> earlier in this thread, note that I didn't even need all the local
> values to unroll it.
>
> It just takes practice to think this way.

>
> James Edward Gray II

Sam

 Sam Kong 01-23-2007 07:45 PM

Re: I need a more efficient algorithm for this problem.

Hi Thomas,

Thomas Hafner wrote:
> "Sam Kong" <sam.s.kong@gmail.com> wrote/schrieb <1169528870.482644.83900@11g2000cwr.googlegroups.c om>:
>
> > Do you know a good solution to this problem?

>
> I let you decide if mine is a good solution:
>
> #\\\
> \$cache = []
>
> def parts(s)
> if s < 1
> []
> else
> \$cache[s] ||
> begin
> a = []
> s.downto(1) do |n|
> k = s / n
> left = [].fill(n, (0 .. (k-1)))
> r = s - k * n
> if (r > 0)
> right = parts(r)
> right.each do |elem|
> a.push([left,elem])
> end
> else
> a.push(left)
> end
> end
> \$cache[s] = a
> end
> end
> end
>
> def part(n)
> parts(n).map{|x| x.flatten}
> end
>
> pp part(8)
> #///

Yes. That's much better than the code I posted.
But the problem is that even the cached version is not fast enough for
my purpose.
James's non-recursive code is not fast enough either.

Probably, the solution to my problem is not just algorithm.
I need to find a mathematical formula.

See http://home.att.net/~numericana/data/partition.htm
What I want is not the array of partitions but only the size of
partitions.
For example, the number of different ways to make 1000 is
24061467864032622473692149727991.
It's almost impossible to keep an array of that size.

I'm satisfied with this thread of talks because it taught me some even
if I couldn't find the answer.

Thanks.

Sam

 Rob Biedenharn 01-23-2007 08:06 PM

Re: I need a more efficient algorithm for this problem.

On Jan 23, 2007, at 2:50 PM, Sam Kong wrote:

> Hi Thomas,
>
> Thomas Hafner wrote:
>> "Sam Kong" <sam.s.kong@gmail.com> wrote/schrieb
>>
>>> Do you know a good solution to this problem?

>>
>> #///

>
> Yes. That's much better than the code I posted.
> Actually I've already tried that.
> But the problem is that even the cached version is not fast enough for
> my purpose.
> James's non-recursive code is not fast enough either.
>
> Probably, the solution to my problem is not just algorithm.
> I need to find a mathematical formula.
>
> See http://home.att.net/~numericana/data/partition.htm
> What I want is not the array of partitions but only the size of
> partitions.
> For example, the number of different ways to make 1000 is
> 24061467864032622473692149727991.
> It's almost impossible to keep an array of that size.
>
> I'm satisfied with this thread of talks because it taught me some even
> if I couldn't find the answer.
>
> Thanks.
>
> Sam

[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

Rob Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

All times are GMT. The time now is 08:15 AM.