wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> different ways of expressing the sum of a number.
        
(Message started by: enabler on Jun 18^th, 2007, 7:43am)

Title: different ways of expressing the sum of a number.
Post by enabler on Jun 18^th, 2007, 7:43am

different ways of expressing the sum of a number.

eg.
for 2
1+1
2

for 3
1+1+1
1+2
2+1
3

please do give algo

Title: Re: different ways of expressing the sum of a numb
Post by SMQ on Jun 18^th, 2007, 8:23am

A search for "partition function" on either Wikipedia (http://en.wikipedia.org) or Mathworld (http://mathworld.wolfram.com) should give you several different ways to calculate this.

--SMQ

Title: Re: different ways of expressing the sum of a numb
Post by Grimbal on Jun 18^th, 2007, 8:23am

A000041 (http://www.research.att.com/~njas/sequences/A000041)

Title: Re: different ways of expressing the sum of a numb
Post by towr on Jun 18^th, 2007, 8:36am

One way would be to find all the partitions of a multiset of n identical elements, then find in how many ways you can arrange the elements of the partition.

e.g
if we have 4
we can have the partitions
{4}
{3,1}
{2,2}
{2,1,1}
{1,1,1,1}
Which you can find quite systematically.

Then find the number of ways to permute the elements from all these multiset partitions.
In this case respectively
1!/1!=1
2!/1!/1! = 2
2!/2!=1
3!/2!/1!=3
4!/4! = 1
which summed gives a total of 8

Title: Re: different ways of expressing the sum of a numb
Post by towr on Jun 18^th, 2007, 8:40am

on 06/18/07 at 08:23:23, SMQ wrote:

A search for "partition function" on either Wikipedia (http://en.wikipedia.org) or Mathworld (http://mathworld.wolfram.com) should give you several different ways to calculate this.

on 06/18/07 at 08:23:37, Grimbal wrote:

A000041 (http://www.research.att.com/~njas/sequences/A000041)

He's not just asking for the number of partitions though..

I mean, for n=2 he has 2, for n=3 he has 4.
That doesn't exactly match "1, 1, 2, 3, 5, 7, 11, 15 ...", even when shifted.

Title: Re: different ways of expressing the sum of a numb
Post by SMQ on Jun 18^th, 2007, 8:54am

on 06/18/07 at 08:40:52, towr wrote:

He's not just asking for the number of partitions though..

Well then it's much simpler: 2^n-1. Consider a "list" of n 1's with n-1 symbols inbetween, each of which is either a plus or a comma. Now take the resulting sums for your answers. e.g. for n = 3:

1 , 1 , 1 --> 1 + 1 + 1
1 , 1 + 1 --> 1 + 2
1 + 1 , 1 --> 2 + 1
1 + 1 + 1 --> 3

--SMQ

Title: Re: different ways of expressing the sum of a numb
Post by R0B1N on Jun 18^th, 2007, 9:49am

As far as i know ,Growth Rate of partition number is ,
partition Number = P(n) = theta((e ^ Pi*(sqrt(2*n/3) )/n)

Code:

template <class T> T &min(T& a, T&b){ return a>b?b:a;}

void integerPartitions(int _Remaining, int _UpperBound, int N, vector<int> &_Array)
{

if ( _Remaining == 0 )

{

for ( int ii=1; ii<=N; ii++)

cout << _Array[ii] << "\t"; cout<<endl;

}

else

{

for ( int j=1; j<=min(_UpperBound,_Remaining); j++, _Array)

{

_Array[N+1] = j;

integerPartitions(_Remaining-j, j, N+1,_Array);

}

}
}

void integerPartitions(const int number)
{

vector<int> _Array(number+1,0);

integerPartitions(number, number, 0,_Array);
}

Title: Re: different ways of expressing the sum of a numb
Post by towr on Jun 18^th, 2007, 10:09am

on 06/18/07 at 08:54:22, SMQ wrote:

Well then it's much simpler: 2^n-1.

I has that sneaking suspicion when I had the partial sequence 1,2,4,8. But I hadn't worked it out yet.
1's seperated by commas or plusses; very neat.

Title: Re: different ways of expressing the sum of a numb
Post by SMQ on Jun 18^th, 2007, 1:56pm

on 06/18/07 at 10:09:24, towr wrote:

1's seperated by commas or plusses; very neat.

Thanks. I suspect there's also a reasonably-natural formulation where 2^n-1 arises as the sum of the binomial coefficients of n-1 choose k-1. For instance it's clear that the number of ways to sum to n with exactly two numbers is n-1 choose 1 -- pick the first number of the pair from 1...n-1 , and the other is forced. It's less clear that the number of ways to sum to n with exactly three numbers is n-1 choose 2 -- or in general that the number of ways to sum to n with exactly k numbers is n-1 choose k-1 -- but it "feels right," and some quick examples seem to bear it out...

--SMQ

Title: Re: different ways of expressing the sum of a numb
Post by Aryabhatta on Jun 19^th, 2007, 9:38am

on 06/18/07 at 13:56:14, SMQ wrote:

<snip>
It's less clear that the number of ways to sum to n with exactly three numbers is n-1 choose 2 --
<snip>
--SMQ

Using your own idea :D Ditch the plusses and use 2 commas and interpret the numbers in base 1.

Title: Re: different ways of expressing the sum of a numb
Post by enabler on Jun 21^st, 2007, 12:40am

My question was if a number is given as input.....
It should print its different ways of expressing its SUM.

input : 2

output:

1 1
2

input : 3

1 1 1
1 2
2 1
3

Title: Re: different ways of expressing the sum of a numb
Post by towr on Jun 21^st, 2007, 12:52am

on 06/21/07 at 00:40:40, enabler wrote:

My question was if a number is given as input.....
It should print its different ways of expressing its SUM.

Ah, I thought you only wanted the number of ways.
But, unless you also want them in a particular order, SMQs solution gives an easy way to give the various representations.
Just take all binary numbers up to 2^n-1, imagine a 0 in front and after it. Take the number of set bits between each two consecutive 0's, add 1 to each, print as sum
so e.g. 1101110010 -> 011011100100 -> {2,3,0,1,0} -> {3,4,1,2,1} -> print(3+4+1+2+1)

Title: Re: different ways of expressing the sum of a numb
Post by SMQ on Jun 21^st, 2007, 6:48am

in C++:

void printSums(unsigned int n) { if (n < 1 || n > 32) { cerr << "error: n must be from 1 to 32" << endl; return; } for(unsigned long i = 0; i < (1UL << (n-1)); i++) { unsigned int x = 1; for(unsigned int j = 0; j < (n-1); j++) { if ((i & (1UL << j)) != 0) { cout << x << " "; x = 1; } else { x++; } } cout << x << endl; } }

--SMQ

Title: Re: different ways of expressing the sum of a numb
Post by enabler on Jun 22^nd, 2007, 3:11am

this works well but it consumes O(n) space

but there is more efficient solution than this............

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void sum(int a[],int left,int right)
{
if(left<right)
{
printf("\n");
for(int i=left;i<=right;i++)
printf("%d ",a[i]);
if(a[left+1]==1)
{
a[left+1]=a[left]+1;
sum(a,left+1,right);
a[left+1]=a[left+1]-a[left];
}
if(a[right-1]==1)
{
a[right-1]=a[right]+1;
sum(a,left,right-1);
a[right-1]=a[right-1]-a[right];
}
}
}

int main()
{
int N=3;
clrscr();
int *p=(int*)malloc(sizeof(int)*N);
for(int i=0;i<N;i++)
p[i]=1;
sum(p,0,N-1);
getch();
return 1;
}

Title: Re: different ways of expressing the sum of a numb
Post by sumantbhardvaj on Jun 25^th, 2007, 4:53am

I could not fully grasp the code implemented by SMQ.
Can any body explain how's that working ?

Does that code implement the same method suggested by towr above...

Title: Re: different ways of expressing the sum of a numb
Post by SMQ on Jun 26^th, 2007, 7:01am

on 06/25/07 at 04:53:46, sumantbhardvaj wrote:

Can any body explain how's that working ?

Certainly!

Theory:

The question asks for all the sums of positive integers totaling a given value http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif. This can be restated as listing all partitions of an ordered list of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif elements. That is, given positive integers http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif₁, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif₂, ... http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subk.gif} such that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subp.gif=1}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subp.gif} = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif, the first partition contains elements 1 through http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif₁, the second partition contains elements http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif₁+1 through http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif₁+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif₂, etc., with the http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/k.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/suph.gif partition containing elements (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subp.gif=1}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup1.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subp.gif})+1 through http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif. Now the list of such partitions is simple to generate: consider, for each 1 _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/j.gif} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif, whether or not the list is partitioned after the _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/j.gif}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/suph.gif element. There are clearly 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supn.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup1.gif unique partitionings, and thus 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supn.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup1.gif unique sums in the original problem statement.

Implementation:

First, a quick check to be sure that the given value of n is reasonable. If n = 0 then there are no results; if n > 32 then the simple bit-counting algorithm below will fail (but since n = 32 already generates upwards of 2 billion results, listing all possible sums for such n is impractical anyway).

Next, we let the index variable i loop from 0 to 2^n-1-1 (note that 1 << m = 2^m). Each partitioning is thus associated with a value of i by the bits of i: the list is partitioned after element _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/j.gif} if and only if bit _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/j.gif} - 1 (0-based) of i is 1.

Within the outer loop, we establish x as an accumulator to convert from a partitioning to the original problem statement: x counts the number of elements in the current partition. Now we use the loop index j to loop over the bits of i. (Note that because the LSB of i is bit 0, j runs from 0 to n - 2 rather than from 1 to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif - 1 as given in the Theory section.)

If the j^th bit of i is set (i & 2^j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0), the list is partitioned after the j + 1^st element: output the current value of the accumulator, x, and reset it to 1. Otherwise, the list is not partitioned after element j + 1; just increment the accumulator.

Last, after checking all n - 1 bits of i, output the final value of the accumulator x.

Hope that makes things clear!

--SMQ

Title: Re: different ways of expressing the sum of a numb
Post by findmeeifucan on Jul 14^th, 2007, 6:48am

The sum
2+2
repeated twice for input 4 when number of ways is taken as 2^n-1. Is 2^n-1 is correct answer or it should be all the non repeated ways of describing sum.

Title: Re: different ways of expressing the sum of a numb
Post by towr on Jul 15^th, 2007, 9:12am

on 07/14/07 at 06:48:22, findmeeifucan wrote:

The sum
2+2
repeated twice for input 4 when number of ways is taken as 2^n-1. Is 2^n-1 is correct answer or it should be all the non repeated ways of describing sum.

It wouldn't be repeated twice in the 2^(n-1) count; the parenthesis are important though.

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

2^(4-1)=8, fits exactly.