1

I am trying to generate a list of ordered pairs with replacement (i.e. needs (0.1, 0.1), (0.1, 0.2) and (0.2, 0.1))that fulfil the condition that their sum is <= max_sum in Python. For example, given max_sum=1 and the list:

[0, 0.1, 0.2, ..., 0.9, 1.0]

I'd like to produce a list containing:

[(0, 0), (0, 0.1), ..., (0, 0.9), (0, 1.0), (0.1, 0), (0.1, 0.1), ..., (0.1, 0.8), (0.1, 0.9), (0.2, 0), (0.2, 0.1), ...]

but not (0.1, 1.0) etc.

Here is a likely inefficient and ugly solution that has some issues in that the if statement sometimes doesn't resolve correctly:

alphas = [0., .1, .2, .3, .4, .5, .6, .7, .8, .9, 1.]
max_sum = 1
def get_pairs(alphas, max_sum)
    for a in alphas:
        for b in alphas:
            if a + b <= max_sum:
                yield (a, b)
Harrison W.
  • 197
  • 11
  • Is the `list` in sorted order? Must the output adhere to a specific order? Can you just brute-force, or is the input large enough that `O(n²)` solutions must be avoided? What have you tried so far? We don't typically write code to order, but if you have an attempt that's failing, post a [MCVE] and someone can likely help fix it. – ShadowRanger Jan 28 '20 at 15:34
  • Is brute forcing an option or does have to be optimised for time complexity ? – k88 Jan 28 '20 at 15:35
  • Apologies, have edited my question to include something that almost works, but doesn't appear to always give the correct thing if you try max_sum = 0.3 for example, I was mainly curious as to whether there was a built-in function / neat way of achieving this, brute-forcing is probably fine for my needs, order does matter – Harrison W. Jan 28 '20 at 15:42
  • 2
    @HarrisonW.: Your specific problem with `0.3` is a duplicate of [Is floating point math broken?](https://stackoverflow.com/q/588004/364696). You'll need to use [the `decimal` module's `Decimal` type](https://docs.python.org/3/library/decimal.html) instead of `float`s, or incorporate manual rounding or the like, if small floating point imprecision is an issue. – ShadowRanger Jan 28 '20 at 15:51

3 Answers3

3

If order matters, which means you will have both (0, 0.2) and (0.2,0) for example, then you can try this :

L = [round(x*0.1, 2) for x in range(0, 10)]
print([(x,y) for x in L for y in L if x + y <= 1])

Output :

[(0.0, 0.0), (0.0, 0.1), (0.0, 0.2), ... (0.8, 0.2), (0.9, 0.0), (0.9, 0.1)]
Phoenixo
  • 2,071
  • 1
  • 6
  • 13
  • This seems to be the most elegant solution that actually gives what is required in output, though for anyone else reading, you need to be conscious of the point ShadowRanger raises in a comment on my question; distinguishing between floats and Decimal types in Python – Harrison W. Jan 28 '20 at 16:34
  • 1
    Yeah, that's why I added a `round(x,2)`, to avoid `0.30000000000000004` instead of `0.3` and stuff like that. – Phoenixo Jan 28 '20 at 16:38
1

You can use itertools permutations. Example code.

from itertools import permutations


test_list = [0, 0.1, 0.2, 0.9, 1.0]
final_list = [item for item in permutations(test_list,2) if sum(item)<=1]
print(final_list)

[(0, 0.1), (0, 0.2), (0, 0.9), (0, 1.0), (0.1, 0), (0.1, 0.2), (0.1, 0.9), (0.2, 0), (0.2, 0.1), (0.9, 0), (0.9, 0.1), (1.0, 0)]
jawsem
  • 751
  • 5
  • 8
  • There is no need to `list`ify the result of `permutations` here; just run over the `permutations` iterator directly and avoid storing a potentially huge `list` when a substantial fraction of it would be discarded immediately. – ShadowRanger Jan 28 '20 at 15:54
  • 1
    Also, `sum()` takes any iterable, so `sum([i for i in item])` is a convoluted and inefficient (wrt/ both space and time) way to write `sum(item)`. – bruno desthuilliers Jan 28 '20 at 15:56
  • Thanks both of you i made edits to address the 2 things you pointed out. – jawsem Jan 28 '20 at 15:56
  • Apologies as the question was perhaps initially unclear but I don't think permutations or combinations does what I require here, maybe the only option is the list comprehension suggested in another answer – Harrison W. Jan 28 '20 at 16:01
1

Something like this:

import itertools
everyPermutation = [x for x in itertools.permutations(iterable, 2)]
finalList = [[x,y] for x,y in everyPermutation if (x + y) <= 1]
OD1995
  • 1,647
  • 4
  • 22
  • 52
  • the result should be a list of tuples, not a list of lists. And you should stick to pep08 naming conventions when posting example Python snippets ;-) – bruno desthuilliers Jan 28 '20 at 15:58