[Math] Most efficient way to calculate possible combinations

combinationscombinatorics

So I just had discussion with a friend about a theoretical situation were he was to populate a server mother board with ram modules in his garage..

So lets assume there are 48 ram slots available to populate each with one of the 7 different capacities of ram available* (1GB,2,4,8,16,32,64) in order to achieve a total of 1TB (or else 1024 GB) of total capacity.

How many possible combinations are there to achieve this? which is the most efficient way to find out?

*you could use each available capacity more than once obviously but I would also like your thoughts on the scenario were you could use them all the combinations of numbers of capacities you like + use just SOME of the group at your discretion e.g just 64 and 32GB sticks and none of the other capacities etc.

Best Answer

This is a dynamic programming problem where there is a base case (Base Case: With $0$ slots, there is $1$ way to create $0$ GB of RAM) and induction (Induction: Using the number of ways to create any sum up to the maximum with $n-1$ slots, we can find the number of ways to get a sum to $s$ with $n$ slots by summing the number of ways to get a sum to $s-a$ with $n-1$ slots for all addends $a$). This is also similar to the subset sum, but instead of figuring out whether or not we can get a sum with $1024$ GB, we're finding the number of ways we can do so. This means that this problem is NP-complete, which basically means the time to solve the problem grows very fast as the addends and/or the sum are added with more digits.

Thus, here is my dynamic programming algorithm for this problem in Python:

# These are our addends:
addends = [1, 2, 4, 8, 16, 32, 64]
# num_sums[num_addends][sum] is the number of ways sum can be found
# using num_addends addends
num_sums = []

# We iterate the number of addends from 0 to 49, not including 49:
for num_addends in range(49):
    # Append an array into num_sums for num_sums[num_addends]:
    num_sums.append([])
    for sum in range(1025):
        # If there are no addends,
        # then there is 1 way to add to 0
        # and 0 ways to add to anything else:
        if num_addends == 0:
            num_sums[num_addends].append(1 if sum == 0 else 0)
        # Otherwise:
        else:
            # At first, we have found 0 ways:
            num_sums[num_addends].append(0)
            # Loop through all the addends:
            for addend in addends:
                # If addend is bigger than sum,
                # exit because that means there is no way
                # to include addend in our sum:
                if addend > sum: break
                # Increment num_sums[num_addends][sum]
                # by the number of ways that sum-addend can be found
                # with num_addends-1 addends:
                num_sums[num_addends][sum] += \
                    num_sums[num_addends-1][sum-addend]

# Output the number of ways to sum to 3 GB with 2 addends.
# It is easy to show that this should be 2,
# so we know we did something wrong if our program does not output 2:
print(num_sums[2][3])
# Output the number of ways to sum to 1024 GB with 48 addends.
print(num_sums[48][1024])

Also, please note that my program accounts for the order in which the slots are filled , so the situation where $1$ GB is put in the first RAM slot and $2$ GB is put in the second RAM slot and the situation where $2$ GB is put in the first RAM slot and $1$ GB is put in the second RAM slot are treated as the different situation and are counted as $2$ ways to sum to $3$ with $2$ addends. Also, I leave no RAM slot empty, so each RAM slot has at least $1$ GB of RAM.

My program outputs $54725807780812926153007692867349522953$ as an answer, meaning that there are $54725807780812926153007692867349522953$ ways to sum to $1024$ GB using $48$ RAM slots with either $1$, $2$, $4$, $8$, $16$, $32$, and $64$ GB of RAM while account for the order in which the RAM slots are filled and leaving no RAM slot empty.

Related Question