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)
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)
