Iterate over pairs in order of sum of absolute values-CodePudding

I want to iterate over pairs of integers in order of the sum of their absolute values. The list should look like:

(0,0)
(-1,0)
(0,1)
(0,-1)
(1,0)
(-2,0)
(-1,1)
(-1,-1)
(0,2)
(0,-2)
(1,1)
(1,-1)
(2,0)
[...]

For pairs with the same sum of absolute values I don't mind which order they come in.

Ideally I would like to be able to create the pairs forever so that I can use each one in turn. How can you do that?

For a fixed range I can make the list of pairs in an ugly way with:

sorted([(x,y)for x in range(-20,21)for y in range(-20,21)if abs(x) abs(y)<21],key=lambda x:sum(map(abs,x))

This doesn't allow me to iterate forever and it also doesn't give me one pair at a time.

CodePudding user response：

This seems to do the trick:

from itertools import count  # Creates infinite iterator

def abs_value_pairs():
    for absval in count():  # Generate all possible sums of absolute values
        for a in range(-absval, absval   1):  # Generate all possible first values
            b = abs(a) - absval  # Compute matching second value (arbitrarily do negative first)
            yield a, b
            if b:  # If first b is zero, don't output again, otherwise, output positive b
                yield a, -b

This runs forever, and operates efficiently (avoiding recomputing anything unnecessarily).

CodePudding user response：

This will do it. If you really want it to be infinite, remove the firs if statement.

import itertools

def makepairs(count=3):
    yield (0,0)
    for base in itertools.count(1):
        if base > count:  # optional escape
            return        # optional escape
        for i in range(base 1):
            yield (i, base-i)
            if base != i:
                yield (i, i-base)
            if i:
                yield (-i, base-i)
                if base != i:
                    yield (-i, i-base)

print(list(makepairs(9)))

CodePudding user response：

The solution below produces a sum stream with tuples of any length:

from itertools import count
def pairs(l = 2):
  def groups(d, s, c = []):
     if not d and sum(map(abs, c)) == s:
        yield tuple(c)
     elif d:
        for i in [j for k in d[0] for j in {k, -1*k}]:
           yield from groups(d[1:], s, c  [i])
  for i in count():
     yield from groups([range(i 1) for _ in range(l)], i)

p = pairs()
for _ in range(10):
   print(next(p))

CodePudding user response：

You could make an infinite generator function:

def pairSums(s = 0): # base generation on target sum to get pairs in order
    while True:      # s parameter allows starting from a given sum
        for i in range(s//2 1):                            # partitions
            yield from {(i,s-i),(s-i,i),(i-s,-i),(-i,i-s)} # no duplicates
        s  = 1                                             # next target sum

Output:

for p in pairSums(): print(p)
        
(0, 0)
(0, 1)
(0, -1)
(1, 0)
(-1, 0)
(2, 0)
(-2, 0)
(0, -2)
(0, 2)
(1, 1)
(-1, -1)
(3, 0)
(0, 3)
(0, -3)
(-3, 0)
(1, 2)
(-1, -2)
(2, 1)
...

CodePudding user response：

First notice that you can lay your totals out in a grid for non-negative values:

x
3|3
2|23
1|123
0|0123
- ----
 |0123y

Here we can see a pattern where the diagonals are your totals. Let's just trace some systematic line through them. The following shows an order you could walk through them:

x
3|6
2|37
1|148
0|0259
- ----
 |0123y

Here the matrix contains the order of the iterations.

This solves your problem for non-negative values of x and y. To get the rest you can just negate x and y, making sure you don't do it for when they are zero. Something like this:

def generate_triplets(n):
    yield 0, (0, 0)
    for t in range(1, n   1):  # Iterate over totals t
        for x in range(0, t   1):  # Iterate over component x
            y = t - x  # Calclulate component y
            yield t, (x, y)  # Default case is non-negative
            if y > 0:
                yield t, (x, -y)
            if x > 0:
                yield t, (-x, y)
            if x > 0 and y > 0:
                yield t, (-x, -y)

def generate_pairs(n):
    yield from (pair for t, pair in generate_triplets(n))

# for pair in generate_pairs(10):
#     print(pair)

for t, (x, y) in generate_triplets(3):
    print(f'{t} = abs({x})   abs({y})')

This outputs

0 = abs(0)   abs(0)
1 = abs(0)   abs(1)
1 = abs(0)   abs(-1)
1 = abs(1)   abs(0)
1 = abs(-1)   abs(0)
2 = abs(0)   abs(2)
2 = abs(0)   abs(-2)
2 = abs(1)   abs(1)
2 = abs(1)   abs(-1)
2 = abs(-1)   abs(1)
2 = abs(-1)   abs(-1)
2 = abs(2)   abs(0)
2 = abs(-2)   abs(0)
3 = abs(0)   abs(3)
3 = abs(0)   abs(-3)
3 = abs(1)   abs(2)
3 = abs(1)   abs(-2)
3 = abs(-1)   abs(2)
3 = abs(-1)   abs(-2)
3 = abs(2)   abs(1)
3 = abs(2)   abs(-1)
3 = abs(-2)   abs(1)
3 = abs(-2)   abs(-1)
3 = abs(3)   abs(0)
3 = abs(-3)   abs(0)

Or as pairs:

(0, 0)
(0, 1)
(0, -1)
(1, 0)
(-1, 0)
(0, 2)
(0, -2)
(1, 1)
(1, -1)
(-1, 1)
(-1, -1)
(2, 0)
(-2, 0)
...

CodePudding user response：

(I hope I understood the requirements) I used itertools product:

>>> for i in sorted(itertools.product(range(-5, 4), range(-5, 4)), key=lambda tup: abs(tup[0])   abs(tup[1])):
    print(i)
... 
(0, 0)
(-1, 0)
(0, -1)
(0, 1)
(1, 0)
(-2, 0)
(-1, -1)
(-1, 1)
(0, -2)
(0, 2)
(1, -1)
(1, 1)
(2, 0)
(-3, 0)
(-2, -1)
(-2, 1)
(-1, -2)
(-1, 2)
(0, -3)
(0, 3)
(1, -2)
(1, 2)
(2, -1)
...