CODEWITHSUNDEEP
pythonrecursioncombinationsdistinct
Muhammad Usama
Muhammad Usama

Reputation: 78

Find Distinct parts of List that Sum are equal to the given Number

I want to find the distinct tuples whose sum equals to K, from an input list with no repeated numbers.

Input: A=[1, 2, 3], K = 3 
Output: 
(1, 2)
(2, 1)
(3)

Note that - (2,3) is not same as (3,2).

What I am doing:

def unique_combination(l, sum, K, local, A):
 
    # If a unique combination is found
    if (sum == K):
        print("(", end="")
        for i in range(len(local)):
            if (i != 0):
                print(" ", end="")
            print(local[i], end="")
            if (i != len(local) - 1):
                print(", ", end="")
        print(")")
        return
 
    # For all other combinations
    for i in range(l, len(A), 1):
 
        # Check if the sum exceeds K
        if (sum + A[i] > K):
            continue
 
        # Check if it is repeated or not
        if (i > l and
                A[i] == A[i - 1]):
            continue
 
        # Take the element into the combination
        local.append(A[i])
 
        # Recursive call
        unique_combination(i+1, sum + A[i],
                           K, local, A)
 
        # Remove element from the combination
        local.remove(local[len(local) - 1])
 

def myFunc(A, K):
 
    # Sort the given elements
    A.sort(reverse=False)
 
    local = []
 
    unique_combination(0, 0, K, local, A)
 

arr = [1,2,3,4,6,7]
target = 8
myFunc(arr, target)

This function Return:

Input: A=[1,2,3,4,6,7], K = 8 
Output: 
(1,  3,  4)
(1,  7)
(2,  6)

I also want the other combination like: (1, 4, 3), (1, 3, 4), (4, 1, 3), (4, 3, 1), (3, 1, 4), (3, 4, 1), (7, 1), (2, 6)

So, What should I do with the code to achieve my result...

Upvotes: 0

Views: 775

Answers (3)

user8234870
user8234870

Reputation:

use permutations

from itertools import permutations
k=8
data = [ 1, 2, 3, 4, 5, 6,7]
ans = []
for i in range(len(data)):
    ans.extend([values for values in permutations(data, i+1) if sum(values)==k])

print(ans)

Output:

$ python3 test.py
[(1, 7), (2, 6), (3, 5), (5, 3), (6, 2), (7, 1), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (2, 1, 5), (2, 5, 1), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (5, 1, 2), (5, 2, 1)]

One liner solution :

k = 8

data = range(1, 8)

ans = [values for i in range(len(data)) for values in itertools.permutations(data, i+1) if sum(values) ==k]
print('permutations : ', ans)

Output:

permutations :  [(1, 7), (2, 6), (3, 5), (5, 3), (6, 2), (7, 1), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (2, 1, 5), (2, 5, 1), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (5, 1, 2), (5, 2, 1)]

Upvotes: 0

nonDucor
nonDucor

Reputation: 2083

Your original function was generating properly the possible combinations. The only problem was that you were printing it, instead of saving it in a list to use later.

I modified it so it saves the result into a list, that can be input to a function that generates all permutations (also implemented recursively) of a list.

Overall, the approach is:

  1. Generate all combinations of 1, 2, ... n numbers that sum to less than goal
  2. Generate all the permutations of these combinations (this step seems useless, because sum is commutative, but I'm assuming that is the definition of your problem)

Note that this is an instance of the Subset Sum Problem, which is a difficult optimisation problem. The solution below does not scale well for large sets.

def unique_combination(in_list, goal, current_sum, current_path, accumulator):
    # Does a depth-first search of number *combinations* that sum exactly to `goal`
    # in_list is assumed sorted from smaller to largest

    for idx, current_element in enumerate(in_list):
        next_sum = current_sum + current_element
        if next_sum < goal:
            next_path = list(current_path)  # list is needed here to create a copy, as Python has a pass by reference semantics for lists
            next_path.append(current_element)
            unique_combination(in_list[idx+1:], goal, next_sum, next_path, accumulator)
        elif next_sum == goal:  # Arrived at a solution
            final_path = list(current_path)
            final_path.append(current_element)
            accumulator.append(final_path)
        else:   # Since in_list is ordered, all other numbers will fail after this
            break
    return accumulator

def permutations(elements):
    # Returns a list of all permutations of `elements`, calculated recursively
    if len(elements) == 1:
        return [elements]
    result = []
    for idx, el in enumerate(elements):
        other_elements = elements[:idx] + elements[idx+1:]
        all_perms = [[el] + sub_perms for sub_perms in permutations(other_elements)]
        result.extend(all_perms)
    return result

def myFunc(input_list, goal):
    # Sort the given elements
    input_list.sort()
    combinations = unique_combination(input_list, goal, 0, [], [])

    result = []
    for comb in combinations:
        result.extend(permutations(comb))
    return result

def print_results(results):
    for el in results:
        print(tuple(el)) # to get the parentheses

# Input:
a = [1,2,3,4,6,7,8]
k = 8
all_permutations = myFunc(a, k)
print_results(all_permutations)

# (1, 3, 4)
# (1, 4, 3)
# (3, 1, 4)
# (3, 4, 1)
# (4, 1, 3)
# (4, 3, 1)
# (1, 7)
# (7, 1)
# (2, 6)
# (6, 2)
# (8,)

Upvotes: 2

Pychopath
Pychopath

Reputation: 1580

Using itertools to go through the candidates:

from itertools import permutations

A = [1,2,3,4,6,7]
K = 8 

for n in range(len(A) + 1):
    for perm in permutations(A, n):
        if sum(perm) == K:
            print(perm)

Output:

(1, 7)
(2, 6)
(6, 2)
(7, 1)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)

Upvotes: 1

Related Questions