Python’s combinations and combinations with replacement
A recent Stack Overflow question had me looking at how to find a list of four numbers each from -1 to 1 that sum up to 1.
Problem statement
Generate every combination of four numbers(a.k.a. quadruplets) from (-1, -0.99, -0.98, ..., 0.98, 0.99, 1) that sum up to 1. Repetitions of numbers are allowed.
For example:
[0, 1, 0.12, -0.12], [0, 0, 0.5, 0.5], [1, 1, -1, 0]....
Solution using Python combination
I assume there will be only a set of unique lists that we should compute. This assumption drives me to use Python’s combination method to get a list of quadruplets from a list of numbers from -1.0 to +1.0 which sum up to 1.
Operating floating numbers are complex, so I multiplied the target sum with 100 and made integer calculations. I created a list from -100 to +100 and repeated the elements four times as the problem allowed repetitions of numbers. Later on, I made a list of quadruplets which sum is equal to 100. Finally, I divided each element by 100 to meet the problem statement.
So far, the code looks like the following snippet:
import csv
from itertools import combinations
def get_four_numbers(target_sum=100):
result = []
ar = list(range(-100, 101, 1)) * 4
for quadruplet in combinations(ar, 4):
if sum(quadruplet) == target_sum:
result.append([i / 100.0 for i in quadruplet])
return result
if __name__ == "__main__":
with open("output.csv", "w") as output_file:
csv_writer = csv.writer(output_file)
csv_writer.writerows(get_four_numbers())
Solution using Python combination
Later on, I found another method from the itertools module called combination with replacement. This will allow me to get the targeted quadruplets without repeating the iterable list ar four times manually. Updating the above snippet, we now have a much cleaner code with the same output quadruplets:
import csv
from itertools import combinations_with_replacement
def get_four_numbers(target_sum=100):
result = []
ar = list(range(-100, 101, 1))
for quadruplet in combinations_with_replacement(ar, 4):
if sum(quadruplet) == target_sum:
result.append([i / 100.0 for i in quadruplet])
return result
if __name__ == "__main__":
with open("output.csv", "w") as output_file:
csv_writer = csv.writer(output_file)
csv_writer.writerows(get_four_numbers())
Output from output.csv (truncated due to filesize):
-1.0,0.0,1.0,1.0
-1.0,0.01,0.99,1.0
-1.0,0.02,0.98,1.0
-1.0,0.02,0.99,0.99
-1.0,0.03,0.97,1.0
-1.0,0.03,0.98,0.99
-1.0,0.04,0.96,1.0
.....
Reference
- Python official documentation on combination method
- Python official documentation on combination with replacement method
- Stackoverflow question: Four numbers each from -1 to 1 that sum up to 1
Advertisement
