Python3 - Permutations for 7 digit number that totals to a number-CodePudding

I need to find a solution for the below problem in Python3. I tried itertools.combinations but not clear on how to do it.

Prepare a 7-digit number that sums to 5. Each digit can be between 0-4 only. Also, there can be repetitions. Valid example numbers are -

[ [2,1,1,0,0,1,0], [3,0,1,0,0,1,0], [0,0,0,4,0,0,1], [1,0,0,3,0,1,0], [1,1,1,1,0,1,0], ...... ]

As you can see, numbers may appear more than once in this list.

How can I create a list of all combinations meeting the criteria above?

CodePudding user response：

You can get all that sum to 5 with:

list(p for p in itertools.product(range(5),repeat = 7) if sum(p) == 5)

This yields 455 solutions.

CodePudding user response：

This function will find every combination, with repeated combinations, that sum to N:

from itertools import product
from typing import List, Tuple
def perm_n_digit_total(n_digits, total, choices) -> List[Tuple]:
    return list(filter(
        lambda x: sum(x) == total,
        product(choices, repeat=n_digits)
    ))

Example:

perm_n_digit_total(3, 1, range(4))
Out[43]: [(0, 0, 1), (0, 1, 0), (1, 0, 0)]

perm_n_digit_total(7, 5, range(4))[::50]
Out[49]: 
[(0, 0, 0, 0, 0, 0, 5),
 (0, 0, 0, 3, 1, 1, 0),
 (0, 0, 2, 0, 3, 0, 0),
 (0, 1, 0, 1, 3, 0, 0),
 (0, 2, 0, 0, 1, 0, 2),
 (0, 4, 1, 0, 0, 0, 0),
 (1, 0, 1, 1, 1, 0, 1),
 (1, 1, 1, 1, 1, 0, 0),
 (2, 0, 1, 0, 0, 2, 0),
 (3, 1, 0, 0, 0, 1, 0)]

CodePudding user response：

Here's an itertools'less recursive solution.

def find_solutions(target, numbers, depth, potential_solution=[]):

    if depth == 0:
        if sum(potential_solution) == target:
            print(potential_solution)
        return

    current_sum = sum(potential_solution)

    for n in numbers:
        new_sum = current_sum   n
        if new_sum > target:
            continue
        find_solutions(target, numbers, depth - 1, potential_solution   [n])

find_solutions(target=5, numbers=[0,1,2,3,4], depth=7)

Output

[0, 0, 0, 0, 0, 1, 4]
[0, 0, 0, 0, 0, 2, 3]
[0, 0, 0, 0, 0, 3, 2]
[0, 0, 0, 0, 0, 4, 1]
[0, 0, 0, 0, 1, 0, 4]
[0, 0, 0, 0, 1, 1, 3]
...
[3, 1, 1, 0, 0, 0, 0]
[3, 2, 0, 0, 0, 0, 0]
[4, 0, 0, 0, 0, 0, 1]
[4, 0, 0, 0, 0, 1, 0]
[4, 0, 0, 0, 1, 0, 0]
[4, 0, 0, 1, 0, 0, 0]
[4, 0, 1, 0, 0, 0, 0]
[4, 1, 0, 0, 0, 0, 0]

CodePudding user response：

If I got it, you need something like this:

import itertools
value = [0, 1, 2, 3, 4]


p = itertools.product(value, repeat=7)
for j in list(p):
  print(j)

CodePudding user response：

As each digit can only take 5 unique values - you would require itertools.combinations_with_replacement -

from itertools import combinations_with_replacement
zero_four = list(range(5))
for c in combinations_with_replacement(zero_four, 7):
    if sum(c) == 5:
        print(c)

This will give you all possible combinations that sum to 5 but not all the permutations -

Output

(0, 0, 0, 0, 0, 1, 4)
(0, 0, 0, 0, 0, 2, 3)
(0, 0, 0, 0, 1, 1, 3)
(0, 0, 0, 0, 1, 2, 2)
(0, 0, 0, 1, 1, 1, 2)
(0, 0, 1, 1, 1, 1, 1)

To get all permutations - you can use the itertools.permutations but since your output can have repeated elements, you will need to use a set to retain only unique permutations -

for c in combinations_with_replacement(zero_four, 7):
    if sum(c) == 5:
        print(set(permutations(c)))