COME ON CODE ON

A blog about programming and more programming.

Counting Problems

with 18 comments

Problem 1: Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to  K?

Also called the Subset Sum Problem, in this problem, the number of times we can use a particular number is limited i.e. we can use a number only once. This problem can be done in two ways
1> Binary Representation of Numbers and
2> DP

1> Using Binary Representation of Numbers
First lets discuss the common approach for iterating through all subsets of a set. Mathematics tells us that the total number of subsets of a set is 2n. THe easier way to do this is in any programmin language is to represent each element of a set by a single bit of the number. So for example, if we have 3 elements in a set then we have 8 subsets. or we can iterate from 0 to 7 to get all subsets as

Number Binary Representation
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

So if we let 1 in the binary represent that the number is selected and 0 that the number is not selected, we actually have all the subsets of the set. We can use this approach to solve the above problem by iterating through all subsets and finding whether the sum is equal to the required sum. The point to be noted is that this approach is quite slow since for a worst case scenario we iterate through all the 2n cases. Also checking each bit takes time. Here’s a simple C++ implementation of the above logic. Below is a program which takes as input N numbers and M the required subset sum and outputs Yes if the subset sum M is possible and No otherwise.

int a[21];
int main()
{
    int t,N,M,i,j,k,sum;
    bool F;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]); 

        F=0;
        j=1<<N;
        for (i=1;i<j && F==0;i++)
        {
            sum=0;
            for (k=0;k<N;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k];
            }
            if (sum == M)
            {
                F=1;
                printf("Yes\n");
            }

        }
        if (F==0)
           printf("No\n");

    }
}

The time complexity of the above code is O(2n). We also have a O(2n/2) algorithm, where we divide the input numbers into two equal subsets. Then we calculate the sum of subsets of each of the two subset. We then iterate through the sums of one subset and check whether M-sum is present in the sums of the other subset. If yes, we get our desired result. If there are no such values we print no.

#include<iostream>
using namespace std;
#include<set>

int a[21];
int main()
{
    int t,N,M,i,j,k,sum,x;
    set<int> s1,s2;
    set<int>::iterator l;
    scanf("%d",&t);
    
    while(t--)
    {
        scanf("%d%d",&N,&M);
        s1.clear();
        s2.clear();
        for (i=0;i<N;i++)
            scanf("%d",&a[i]); 

        
        j=1<<(N/2);
        for (i=0;i<j;i++)
        {
            sum=0;
            for (k=0;k<N/2;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k];
            }
            s1.insert(sum);
        }
        
        x=N-N/2;
        j=1<<x;
        for (i=0;i<j;i++)
        {
            sum=0;
            for (k=0;k<x;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k+N/2];
            }
            s2.insert(sum);
        }
        
        for (l=s1.begin();l!=s1.end();l++)
        {
            if (binary_search(s2.begin(),s2.end(),M-*l))
            {
               printf("Yes\n");
               break;
            }
        }
        if (l==s1.end())
           printf("No\n");
    }
}

2> DP Approach
This is the other approach to solving this problem. This method takes into account that the possible sum’s after including a number, are all previous possible sum’s plus the new number. So we only check whether x-ai is a possible sum, if yes x is also a possible sum. We iterate from M (maximum possible sum) to ai because we cannot include a number twice. Here’s the C++ implementation of the above program using DP approach.

int m[30000],a[21];
int main()
{
    int t,N,M,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]);
        for (i=0;i<=M;i++)
            m[i]=0;
       	m[0]=1;
        for(i=0; i<N; i++)
        	for(j=M; j>=a[i]; j--)
        		m[j] |= m[j-a[i]];
  		if (m[M])
  		   printf("Yes\n");
	   else
	       printf("No\n");
    }
}

Problem 2: Given that the ai‘s are unlimited i.e you can use the numbers in the subset as many times as you want find whether a particular sum M is possible and if possible how many ways are there to do it?

Also called the Counting Change Problem, this problem is a variation of the above problem and we just need to change the direction of the second loop in the above problem. Here’s a program to find the number of ways to change a amount of Rs. 100 using the coins and notes of RS. 1,2,5,10,20,50,100.

int main()
{
    int coin[7]={1,2,5,10,20,50,100},i,j,x,c;
    x=100;
    vector<long long> ways(x+1,0);
    ways[0]=1;
    for (i=0;i<7;i++)
    {
      c=coin[i];
      for (j=c;j<=x;j++)
          ways[j]+=ways[j-c];
    }
    cout<<ways[100]<<endl;
}

More variations of the above problem can be minimizing the number of elements required to get a particular sum.

Problem 3: Find the number of ways of writing a number as the sum of positive integers?

Also called the Partition Function P of n, it is denoted by P(n). For example,

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

Euler invented a generating function which gives rise to a recurrence equation in P(n),
Recurrence Equation in P(n)
Below is a program to calculate P(n). It can easily modified to include large numbers.

#include<iostream>
using namespace std;
#include<map>

map <int , long long> P;
 
long long Calculate_Pn(long long n)
{
  if (n < 0) 
     return 0;
 
  long long Pn = P[n];
 
  if (Pn == 0) 
  {
     long long k; 
     for (k = 1; k <= n; k++) 
     { 
         // A little bit of recursion 
         long long n1 = n - k * (3 * k - 1) / 2; 
         long long n2 = n - k * (3 * k + 1) / 2; 
    
         long long Pn1 = Calculate_Pn(n1); 
         long long Pn2 = Calculate_Pn(n2); 
    
         // elements are alternately added 
         // and subtracted 
         if (k % 2 == 1) 
            Pn = Pn + Pn1 + Pn2; 
         else 
              Pn = Pn - Pn1 - Pn2; 
    }
       P[n]=Pn;
  } 
  return Pn;
}

int main()
{
    long long i;
    P[0]=1;
    while (scanf("%lld",&i)!=EOF)
          printf("%lld\n",Calculate_Pn(i));
}

Happy Coding!!!
-fR0D

Advertisements

Written by fR0DDY

July 21, 2009 at 10:05 AM

18 Responses

Subscribe to comments with RSS.

  1. There is also a O(2^(n/2)) algorithm which uses binary search or data structures like balanced trees 🙂
    Check it out on wikipedia, it’s good when the numbers are too large to permit a DP.

    whome

    September 24, 2009 at 12:34 AM

  2. hey buddy..
    regarding the DP approach to counting problem,
    if the statement goes like this…

    “Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to K, the subset of numbers must contain x elements where x<M?"

    i.e in this case, the number of elements required to obtain the sum K are given, then how to go about this problem.

    ayan

    January 23, 2010 at 10:38 AM

    • I don’t know of any DP approach that can be used to do this. The subset should contain exactly x elements or the number of elements in the subset be less than equal to x?

      fR0DDY

      January 25, 2010 at 9:10 PM

  3. the number of elements should be exactly equal to x.

    ayan

    January 25, 2010 at 9:38 PM

    • Then I am unaware of a solution. If i do get to know any, I will let you know. Also can you give me the source of the question?

      fR0DDY

      January 25, 2010 at 9:41 PM

  4. thanks anywayz… 🙂
    this is a question from UVA ..
    problem no: 10032

    ayan

    January 25, 2010 at 9:49 PM

  5. […] problema. References: 1. Wikipwdia 2. Introduction to Algorithms, Thomas h: Cormen, MIT Press 3. https://comeoncodeon.wordpress.com/2009/07/21/counting-problem/ Possibly related posts: (automatically generated)Euler Problem 278Euler Problem 99Project Euler i […]

  6. Curiously I’ve developed an algorithm for solving subset sum problems using natural numbers, and this uses an abstract form of counting to form rules on how to progress the search of possible subsets. So for the nCr type problem of a target of 2 for the set { 1, 1, 1, 1 } my algorithm, without any special cases, will progress to the binary solutions as follows:

    0011
    0101
    0110
    1001
    1010
    1100

    The algorithm for this case would also never select more than 2 numbers from the original set. In fact for any problem it is possible to determine the maximum and minimum subset sizes it would possibly consider. Currently I’m developing an application that uses the algorithm to find non intersecting subset sums from a set, and it behaves in a similar manner for these cases. To the best of my knowledge, (endless google searches), the technique has not been published, or made public by anybody else.

    JB

    John Bufton

    April 17, 2010 at 7:30 AM

    • Hi John,

      This is not a new algorithm but a known one. In fact, the question asked above by Ayan
      “Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to K, the subset of numbers must contain x elements where x<M?"
      has to be solved by a similar algorithm.

      fR0DDY

      April 17, 2010 at 4:30 PM

  7. […] problema. References: 1. Wikipwdia 2. Introduction to Algorithms, Thomas h: Cormen, MIT Press 3. https://comeoncodeon.wordpress.com/2009/07/21/counting-problem/ Share/Bookmark This entry was posted in C#, Programiranje, Project Euler and tagged C#, Project […]

  8. Greetings ..
    My name is Ahmad, I just wanted to thank you very much for this code, Ive been trying to do such a function but unfortunately it didnt work out.
    anyway Im participating in the ACM local contest and I hope I can refer to you and ask you anything.
    many thanks in advance.

    best regards.
    Ahmad

    Ahmad

    October 27, 2011 at 5:45 AM

  9. solution to subset_sum problem:-
    1> Using Binary Representation of Numbers

    in the given code what is – “t”??

    Thanks in advance

    addi

    November 23, 2011 at 10:50 AM

    • t is number of test cases, it is not related to the problem at hand.

      fR0DDY

      November 23, 2011 at 10:58 AM

  10. Hi ,

    for Counting Change Problem when i=0

    for (j=c;j<=x;j++)
    ways[j]+=ways[j-c];

    then this loop will make ways[100]=100;

    i didnt get this bcoz ways[100] represents number of ways by which we can use given coin to sum upto Rs 100

    so when i=0 then Rs 1 is selected and it is making value of ways[100]=100 i.e there are 100 ways by which you can sum up to 100 using Rs 1 coin….. I doubt that
    coin Rs 1 can be added 100 times to make 100 Rs..this is 1 way of doing it not 100 ways..

    please let me know where i am making mistake.

    Thanks in advance 🙂

    addi

    November 24, 2011 at 10:06 AM

    • When i = 0, then we have all the values for ways equal to zero except ways[0]. So we get a loop for j from 1 to 100 and ways[1] = ways[0] = 1. Then ways[2] = ways[1] = 1 and so on till ways[100] = ways[99] = 1. So there is only one way to make a sum of 100 by using 1 Re coins.

      fR0DDY

      November 24, 2011 at 10:38 AM

      • Thanks fRoDDY …got it
        sorry my mistake , i didnt read the code properly

        addi

        November 24, 2011 at 12:39 PM

  11. Variant of coins-change!
    =)
    How about this:
    Determine if there is a way to give a change R using at most k coins.

    Example:
    The coins are this: v1 = 1; v2 = 5; v3 = 10.
    We have to give change R = 17.
    We must use k = 4 coins.
    So, the solution is R = 1 + 1 + 5 + 10 (because of the 4 coins k)

    (If R = 18, for example above, there is no way!)

    Carmelina

    June 29, 2015 at 9:22 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: