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

Advertisement

Citation

Click to select citation style

Shovon, A. R. (2022, January 2). Python's combinations and combinations with replacement. Ahmedur Rahman Shovon. Retrieved June 22, 2024, from https://arshovon.com/blog/python-combinations_with_replacement/

Shovon, Ahmedur Rahman. “Python's combinations and combinations with replacement.” Ahmedur Rahman Shovon, 2 Jan. 2022. Web. 22 Jun. 2024. https://arshovon.com/blog/python-combinations_with_replacement/.

@misc{ shovon_2022,
    author = "Shovon, Ahmedur Rahman",
    title = "Python's combinations and combinations with replacement",
    year = "2022",
    url = "https://arshovon.com/blog/python-combinations_with_replacement/",
    note = "[Online; accessed 22-June-2024]"
}