Combinations algorithm challenge

Question

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

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
– Domagoj, Commented Apr 8, 2013 at 9:10
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
– Vorsprung, Commented Apr 8, 2013 at 9:12

Petar Ivanov · Accepted Answer · 2013-04-08 09:18:50Z

3

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.

answered Apr 8, 2013 at 9:18

Petar Ivanov

93.4k11 gold badges84 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Domagoj Over a year ago

Interesting I will try this!

Domagoj Over a year ago

However, this is not what I was looking for but the way it was achieved gave me an idea.

Samy Arous Over a year ago

This idea can be improved by branching out as soon as we reach y. meaning since the array is sorted, you do know that if the combination [0, 1, 2, 3, 6] is greater or equal to y, then [0, 1, 2, 3, 7] is not gonna work either and so directly skip and try [0, 1, 2, 4, 5] directly.

Domagoj Over a year ago

Well i said this is not what i was looking for and after trying this out I just stroke the brick wall. If even I manage to develop algorithm that works this way computing time increases exponentionaly.

MissingNumber · Accepted Answer · 2013-04-08 13:56:06Z

1

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

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

edited Apr 8, 2013 at 13:56

answered Apr 8, 2013 at 10:48

MissingNumber

1,18215 silver badges29 bronze badges

1 Comment

Domagoj Over a year ago

Interesting! Thank you for directions!!

Quonux · Accepted Answer · 2013-04-08 09:14:24Z

0

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

answered Apr 8, 2013 at 9:14

Quonux

2,9911 gold badge25 silver badges33 bronze badges

Collectives™ on Stack Overflow

Combinations algorithm challenge

3 Answers 3

4 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related