Is there a non-recursive way to solve this problem?

dave8753

New member
Joined
Oct 7, 2021
Messages
2
Hey Folks!

I am dabbling a bit into computer programming, specifically algorithms. I came across a problem that I found out how to solve recursively, however it seems...inelegant..to me and I am wondering if there is a "faster" way solve the problem that doesn't include doing the same formula "X" times.

Let's say I am building a machine that makes flavored beverages by adding any specific combination of flavors that the user wants, how can I calculate how many combinations of drinks a user can make given X flavors?
(Example: If I have 10 flavors available, how many combinations of drinks can a person make with that)

The solution I arrived at was a basic recursive combination calculation:

n!/(r!(n−r)!)
n = number of flavors available
r = sample of flavors

If I had, say 10 flavors, I would need to recursively run this equation 10 times to get the result:
10!/(1!(10−1)!) = 10
10!/(2!(10−2)!) = 45
10!/(3!(10−3)!) = 120
10!/(4!(10−4)!) =210
10!/(5!(10−5)!) = 252
10!/(6!(10−6)!) = 210
10!/(7!(10−7)!) = 120
10!/(8!(10−8)!) = 45
10!/(9!(10−9)!) = 10
10!/(10!(10−10)!) =1

and add those results together:

10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 = 1023

...and then add one more because "no flavor" is a valid combination = 1024

I am curious if there is a way to solve this problem that isn't O(n)
(Perhaps what I have currently is the best way...but I wanted to see if there is a better way to think about it)
 

dave8753

New member
Joined
Oct 7, 2021
Messages
2
Okay following up here to confirm I am thinking about this too hard (While feeling slightly stupid if true):
Since a flavor can either be added or not added wouldn't this just be an easy problem to solve with a binary exponent?

n = number of flavors?
[math]2^{n}[/math]
 

lookagain

Elite Member
Joined
Aug 22, 2010
Messages
2,858
dave8753, you have 10 flavors in total. Think of it as 10 switches in a line.
Each switch is either on or off, that is, a flavor is either used in a combination or it is not. So, there are 2 choices for each switch, 10 switches (flavors), and that equals
2*2*2* . . .*2 = 2^10 = 1,024 exactly.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
11,332
I am dabbling a bit into computer programming, specifically algorithms. I came across a problem that I found out how to solve recursively, however it seems...inelegant..to me and I am wondering if there is a "faster" way solve the problem that doesn't include doing the same formula "X" times.
Let's say I am building a machine that makes flavored beverages by adding any specific combination of flavors that the user wants, how can I calculate how many combinations of drinks a user can make given X flavors?
(Example: If I have 10 flavors available, how many combinations of drinks can a person make with that)
10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 = 1023
We assume that each deink consists of at least one flavor and at most [imath]X[/imath] flavors.
That is the same as asking how many non-empty subsets are there in a set [imath]X[/imath] elements.
The answer is [imath]2^X-1[/imath]. In your posted example: [imath]2^{10}-1=1024[/imath].
 
Top