how to create a dictionary whose keys are (i,j) integer pairs with i < j

user_7447976 0
Viewed 206

I intend to create thousands of integer pairs, number them and store them in a dictionary. Given a number n, my goal is to generate every (i,j) pair such that i<j.

For instance, if n=4, the pairs will be then the dictionary will look like {(0, 1): 0, (0, 2): 1, (0, 3): 2, (1, 2): 3, (1, 3): 4, (2, 3): 5}.

I can generate this dictionary by using nested for loops, but it is not efficient when n is large. Could someone help me to perform this operation quicker than I currently do?

d={}
n=4
temp =0

for i in range(n):
    for j in range(n):
        if i <j:
            d.update({(i,j): temp})
            temp+= 1
combinations nested-loops dictionary python
2 Answers

This is a perfect job for itertools.combinations as it will only produce the required combinations:

from itertools import combinations

n = 4
out = {k:v for v,k in enumerate(combinations(range(n), 2))}

output: {(0, 1): 0, (0, 2): 1, (0, 3): 2, (1, 2): 3, (1, 3): 4, (2, 3): 5}

Using your code

Note that you could rework your code to only produce the required combinations:

d={}
n=4
temp = 0

for j in range(n):
    for i in range(j):
        d[(i,j)] = temp
        temp += 1

# {(0, 1): 0, (0, 2): 1, (1, 2): 2, (0, 3): 3, (1, 3): 4, (2, 3): 5}
user_163434640

Taking it a step further:

from itertools import combinations, count

n = 4
out = dict(zip(combinations(range(n), 2), count()))

Try it online!

Seems to be slightly faster. Test with n = 1000:

191.0 ms  mozway
176.2 ms  kelly
186.8 ms  mozway
177.8 ms  kelly
185.2 ms  mozway
178.6 ms  kelly

Code (Try it online!):

from timeit import repeat
from itertools import combinations, count

def mozway():
    return {k:v for v,k in enumerate(combinations(range(n), 2))}

def kelly():
    return dict(zip(combinations(range(n), 2), count()))

n = 1000
for func in [mozway, kelly] * 3:
    t = min(repeat(func, number=1))
    print('%5.1f ms ' % (t * 1e3), func.__name__)
user_126710570
Related