I'm doing a programming exercise, these are the instructions:

TLDR version of problem below


Our website receives visitors from 3 locations and the number of unique visitors from each of them is represented by three integers a, b and c.

Considering our servers cannot serve more than N visitors, which is always less than the total number of users from all three locations

Your task is to

write a function that prints to the standard output (stdout) the number of unique possible configurations (as, bs, cs) which can be used to serve exactly N visitors

as represents the number of users from location a we choose to serve

bs represents the number of users from location b we choose to serve

cs represents the number of users from location c we choose to serve

Note that your function will receive the following arguments:

a which is an integer representing the number of users from location a
b which is an integer representing the number of users from location b
c which is an integer representing the number of users from location c
n which is an integer representing the number of users our servers can serve

TLDR; Problem is something like: you have groups of visitors a,b,c. How many ways can you come up with n by taking a unique number from each of these groups? So particular visitor doesn't matter. Only the # of visitors and from which group.

Question: How do I express this as a Permutation or Combination?

The program I'm writing has to be scalable for n's up to 100, so I can't just brute-force every possible scenario. I've brushed up on permutations and combinations, and I feel I have to do some sort of multiplication between dependent events. Or am I thinking too much into it. Any explanation would be awesome! I'm not lazy, just truly stuck. I'm missing something here.

I came up with a "duh" implementation based on what ShreevatsaR said:

`My Code

void count_configurations(int a, int b, int c, int n) { int count = 0;

for (int A = 0; A <= a; A++){
     for (int B = 0; B <=b; B++){
         for (int C = 0; C <= c; C++){
             if (n == A + B + C) count++;

cout << count;

} `

  • $\begingroup$ If you wish to count the number of results printed, you can use the stars and bars argument, in particular Theorem 1: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) $\endgroup$ – Jacopo Notarstefano Feb 5 '14 at 19:27
  • $\begingroup$ As it's a programming exercise, we should probably not give away the mathematical solution (or even terminology). However, note that what you're counting is the number of ways to write the number $n$ as $n = a + b + c$, where $a, b, c$ are nonnegative integers. You can try with brute-force all possibilities $0 \le a \le n$ for $a$, then all possibilities $0 \le b \le n$ for $b$, and see if there's a $c$ that works. This shouldn't be a problem at all for $n$ in the 100s. $\endgroup$ – ShreevatsaR Feb 5 '14 at 19:27
  • $\begingroup$ Thanks! Both ideas are great starts. I think I can go from here. I just had a problem on how to think of the problem more abstractly, and how to apply it concretely in my case. The stars and bars method is exactly what I was looking for. Thanks Jacopo! And thanks ShreevatsaR for ideas on how to implement it. Thanks yall both! :D $\endgroup$ – veeberz Feb 5 '14 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.