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, Sep 30 '14 at 00:09
@abarnert: It's an implementation of partitioning in Python. The only difference is the scaling by 0.1. — Greg Hewgill, Sep 30 '14 at 00:11
@GregHewgill: But that question is for all partitions up to length 4, not just length 4, and with no `0`s, 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, Sep 30 '14 at 00: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, Sep 30 '14 at 00: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, Sep 30 '14 at 00:22
Since the link is now gone: [here it is](http://stackoverflow.com/questions/18503096/python-integer-partitioning-with-given-k-partitions). If you can use that to get started, and come back if you get stuck, you have a good question. If not, you're just asking us to do your work for you. — abarnert, Sep 30 '14 at 00:23
Ty all... Lol Abarnet havent even thought about it!! Got it sorted out!! ty so much!! — Juan Sebastancho, Sep 30 '14 at 00:25

score 0 · Answer 1 · answered Sep 30 '14 at 00:39

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]]

Loop searching all possible combinations in an array

1 Answers1