Adi_S - 12 days ago 5

Python Question

`def number_ties(my_list, for_it=[], against=[],ties=0,k=0):`

if len(my_list)==0:

return ties

j=my_list[0]

del my_list[0]

if sum(list(for_it))==sum(list(against)) and k>0:

ties+=1

k+=1

return number_ties(my_list,for_it+[j],against,ties,k)+number_ties(my_list,for_it,against+[j],ties,k)

Using recursion, I'm trying to take a list of numbers and find out how many ways I can put different combinations of these numbers for and against something ( a vote for example ) and achieve a tie. For example [1,2,3] can tie in 2 ways i.e [1,2] against [3] and [3] against [1,2]. Similarly [1, 1, 2, 3, 5] should tie in 4 ways. ( Same numbers within the list should be considered different votes.Like people with different voting weights, for example.)

My code above doesnt work. How may I fix it?

Answer

The resulting problem of summing up combinations to half the total sum of your list is more suitable for a recursive implementation:

```
def number_ties(lst):
s = sum(lst)
if s % 2:
return 0 # sum must be even for it to work at all
half = s // 2
return sum_count(lst, half)
def sum_count(lst, total): # number of combinations out of lst that sum to total
if not lst: # base case
return int(total == 0) # empty lst and total 0 -> return 1
# recur: add ways with first element and ways without
return sum_count(lst[1:], total) + sum_count(lst[1:], total-lst[0])
> print(number_ties([1, 2, 3]))
2
> print(number_ties([1, 1, 2, 3, 5]))
4
```

Source (Stackoverflow)

Comments