CODEWITHSUNDEEP
pythonarraysalgorithmmath
Elizaveta Ivanova
Elizaveta Ivanova

Reputation: 287

Iterate through all possible values in array which give 1 in sum

I have an array of 4 values. For example: [0.1, 0.1, 0.5, 0.3] (sum of elements = 1) How to iterate though all possible values with increment 0.1 to get in sum 1.

example:

[1.0, 0.0, 0.0, 0,0]
[0.9, 0.1, 0.0, 0,0]
[0.9, 0.0, 0.1, 0,0]
......
[0.7, 0.2, 0.0, 0,1]

Preferably in python or java. Or just algorithm explanation in pseudocode

Upvotes: 0

Views: 566

Answers (4)

Teepeemm
Teepeemm

Reputation: 4508

Instead of the values, pretend you're placing four subintervals into an interval of length 1. Then the four values are determined precisely by the three endpoints of those subintervals.

from itertools import combinations_with_replacement as cwr

for (one,onetwo,onetwothree) in cwr(range(11),3):
    print([one/10,(onetwo-one)/10,(onetwothree-onetwo)/10,(10-onetwothree)/10])

Upvotes: 0

Jonathan Eunice
Jonathan Eunice

Reputation: 22473

This is basically an integer problem couched as a floating point problem. It can be solved as a FP problem, but the inexactness of float representations and the inability of Python builtins like range to provide floating point ranges makes it more difficult. So easier to solve it in the neat, exact integer realm then display the results as floating point values.

It's possible to generate all possible combinations of values, then test whether they sum to the target value. That's what some of the other proposed solutions do. But that's a little brute-force. It's also possible to generate only those vectors/lists that sum to the target value. This solution does so with recursive generators.

def vectors(length, target):
    """
    Generate all lists of whole numbers of given
    length that add up to the target value.
    """
    if length == 1:
        yield [target]
    else:
        for firstval in range(target+1):
            for rest in vectors(length-1, target-firstval):
                yield [firstval] + rest

TARGET=10
LENGTH=4
for vec in vectors(LENGTH, TARGET):
    print [ v / float(TARGET) for v in vec ]

This yields:

[0.0, 0.0, 0.0, 1.0]
[0.0, 0.0, 0.1, 0.9]
[0.0, 0.0, 0.2, 0.8]
...
[0.9, 0.0, 0.0, 0.1]
[0.9, 0.0, 0.1, 0.0]
[0.9, 0.1, 0.0, 0.0]
[1.0, 0.0, 0.0, 0.0]

Upvotes: 1

Paddy3118
Paddy3118

Reputation: 4772

Try the dollowing list comprehension:

>>> from itertools import product
>>> s = [list(p/10. for p in prd) 
         for prd in product(range(11), repeat=4) if sum(prd) == 10]
>>> len(s)
286
>>> [0.,1.,0.,0.] in s
True
>>> [.8,.2,.0,.0] in s
True
>>>

It is itertools.product that is needed here.

Upvotes: 0

Jose Varez
Jose Varez

Reputation: 2077

Have a look at itertools.permutations:

import itertools
allPermutations = itertools.permutations([0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]*4, 4)
Sum1Permutations = [x for x in allPermutations if sum(x) == 1]

As @HuStmpHrrr points out this is using brute force to solve the problem. The algorithm for generating all the permutations which add to 1.0 is this one:

Sum1Permutations = []
for x in range(10):
    for y in range(10-x+1):
        for z in range(10-x-y+1):
            Sum1Permutations.append([float(x)/10, float(y)/10, float(z)/10, float(10 - x - y - z)/10])

Or, using a list comprehension:

Sum1Permutations = [[float(x)/10,float(y)/10,float(z)/10,float(10-x-y-z)/10] for x in range(10) for y in range(10-x+1) for z in range(10-x-y+1)]

Upvotes: 0

Related Questions