CODEWITHSUNDEEP
pythonpython-3.xpermutation
Kumaran S
Kumaran S

Reputation: 119

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

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?

Upvotes: 3

Views: 283

Answers (5)

Aidan Bailey
Aidan Bailey

Reputation: 41

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]

Upvotes: 2

Tom McLean
Tom McLean

Reputation: 6369

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

Upvotes: 2

Mortz
Mortz

Reputation: 4939

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

Upvotes: 0

John Coleman
John Coleman

Reputation: 52008

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.

Upvotes: 3

Vinícius Tomazoni
Vinícius Tomazoni

Reputation: 58

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)

Upvotes: 1

Related Questions