Combinations algorithm challenge

0
votes

I am trying to solve this problem for over a month now. I have a list of numbers and these variables:

list_num = [1, 1, 2, 3, 5, 6, 1, 1, 3, 4, 4]

#x is number of numbers in combination eg. if x = 5 combiantions will look like this [n,n,n,n,n], where n is possible member of list _num
x = 5
#y is a sum of numbers inside combination
y = 10

I have a need to generate all possible combinations of this numbers in the way that x is number of numbers in combination and the y is the sum of numbers in combination, also the number of repeating inside list_num must be considered.

I can do this by generating all possible combination and by eliminating the combinations that are not determined by my rules but this method is messy and I cant use it with large number of data. In mine original program list_num can have hundreds of numbers and variables x and y can have large values.

Couple of the combinations for this example:

comb1 = [1,1,2,3,3], x = 5, y = 10
comb2 = [1,1,1,2,5], x = 5, y = 10
comb3 = [1,1,1,1,6], x = 5, y = 10

...

I would appreciate some new ideas, I do not have any left :)

3
pythonalgorithmcombinations
Any constraints on x and y? - default locale
give clear variablenames :) - Quonux
Default locale, well obviously x cant be larger of len(num_list) and y must be possible both are integers. Quonux what do you mean by clear variablenames? - Domagoj
y in comb1, comb2, comb3 is the sum of the numbers. But it isn't in list_num. comb1,comb2,comb3 have repeated numbers that are counted. I don't quite follow your examples and what you mean by "repeating numbers must be counted" - Vorsprung
check out: en.wikipedia.org/wiki/Subset_sum_problem - georg

3 Answers

1
votes

This is NP-complete problem, please find the optimal solution for this at :

http://en.wikipedia.org/wiki/Subset_sum_problem

3
votes

Here is an idea:

1) Sort the list

2) Use an array A of x elements - these are going to be indexes

3) Initialize A to be [0,1,2,...,x-1]

4) Now start increasing the indexes lexicographical, e.g. first increase the last one until the sum gets >y. Then increase the second to last and make the last be 1+the second to last

and so on

Fisrt few iterations:

sorted array: [1, 1, 1, 1, 2, 3, 3, 4, 4, 5, 6]

A: [0,1,2,3,4]

A: [0,1,2,3,5]

A: [0,1,2,3,6]

A: [0,1,2,3,7]

A: [0,1,2,3,8]

A: [0,1,2,3,9]

A: [0,1,2,3,10] - solution

A: [0,1,2,4,5]

A: [0,1,2,4,6]

A: [0,1,2,4,7]

A: [0,1,2,4,8]

A: [0,1,2,4,9] - solution

A: [0,1,2,4,10] - >y

A: [0,1,2,5,6]

A: [0,1,2,5,7] - solution

etc.

0
votes

For base 10 output numbers you can just count a variable up, do the sign sum and output the combination if the sign sum is for example 10.

Code:

def SignSum(X):
    Sum = 0

    String = str(X)

    for Sign in String:
       Sum += int(Sign)

    return Sum

Counter = 0


while Counter < 10000:
   if SignSum(Counter) == 10:
      print Counter

   Counter += 1

this of course works also with other bases with a modified SignSum() function