Loop searching all possible combinations in an array

Question

I'm having trouble with an algorithm in python. I have an array of 4 values [a,b,c,d] those are percentages so at any given time a+b+c+d=1. I need a loop that goes through all possible combinations of these numbers with a stepsize of 0.1. Example:

[0,0,0,1]
[0,0,0.1,0.9]
[0,0.1,0.1,0.8]
[0.1,0.1,0.1,0.7]
.....
[0.1,0.1,0.2,0.6]
[0.1,0.1,0.3,0.5]
....
[1,0,0,0]

I created a code that seems to overflow... any help? ty I Know its a noob question...

def frange(start, stop, step):
    while start <= stop:
        yield start
        start += step

def distribuir(p,array):
    if len(array) == 3:
        array.append(p)
        print(Array)
        return
    for i in frange(0,1,0.1):
        temp = []
        temp.append(array)
        temp.append(i)
        distribuir(p-i,temp)

So, what have you tried? If you don't know how to loop from 0.0 through 1.0 by a step size of 0.1, consider what happens if you do range(10) and multiply each value by 0.1. Once you have that, you should know how to write the next loop down (hint: if the first value is 0.4, then the next value only has to loop from 0.0 to 0.6), and the next, and the next. If you get stuck somewhere, you can post your code and where you're stuck. — abarnert
– abarnert, Commented Sep 30, 2014 at 0:09
@abarnert: It's an implementation of partitioning in Python. The only difference is the scaling by 0.1. — Greg Hewgill
– Greg Hewgill, Commented Sep 30, 2014 at 0:11
@GregHewgill: But that question is for all partitions up to length 4, not just length 4, and with no 0s, and treating 1, 1, 1, 7 and 7, 1, 1, 1 as the same partition, all of which are different from the desired output here. — abarnert
– abarnert, Commented Sep 30, 2014 at 0:16
You know, sometimes if you're given a 90% solution it might be worthwhile doing the extra 10% yourself. Anyway, I'll unclose this and you can sort it out. — Greg Hewgill
– Greg Hewgill, Commented Sep 30, 2014 at 0:18
@GregHewgill: Sure, but I don't think the OP is likely to figure out how to turn that algorithm into one that handles permutations (except maybe by getting all permutations of each value and then filtering them, which wouldn't be a very good solution). — abarnert
– abarnert, Commented Sep 30, 2014 at 0:22

Chris Martin · Accepted Answer · 2014-09-30 00:39:32Z

A naive recursive solution with a lot of room for optimization:

import itertools

def possibilities(prefix, size, values, total):                                                                                                                                               
    if size == 0:
        return [prefix] if sum(prefix) == total else []
    return itertools.chain(*map(
        lambda v: possibilities(prefix+[v], size-1, values, total),
        values
    ))

Example:

list(
    map(
        lambda t: map(float, t),
        possibilities(
            prefix=[],
            size=3,
            values=map(Decimal, ['0', '0.1', '0.2', '0.3']),
            total=Decimal('0.4')
        )
    )
)

Output:

[[0.0, 0.1, 0.3],
 [0.0, 0.2, 0.2],
 [0.0, 0.3, 0.1],
 [0.1, 0.0, 0.3],
 [0.1, 0.1, 0.2],
 [0.1, 0.2, 0.1],
 [0.1, 0.3, 0.0],
 [0.2, 0.0, 0.2],
 [0.2, 0.1, 0.1],
 [0.2, 0.2, 0.0],
 [0.3, 0.0, 0.1],
 [0.3, 0.1, 0.0]]

Collectives™ on Stack Overflow

Loop searching all possible combinations in an array

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related