Find all unique pairs of keys of a dictionary

Question

If there's a dictionary:

test_dict = { 'a':1,'b':2,'c':3,'d':4}

I want to find pairs of keys in list of tuples like:

[('a','b'),('a','c'),('a','d'),('b','c'),('b','d'),('c','d')]

I tried with the following double iteration

test_dict = { 'a':1,'b':2,'c':3,'d':4}
result = []
for first_key in test_dict:
    for second_key in test_dict:
        if first_key != second_key:
            pair = (first_key,second_key)
            result.append(pair)

But it's generating the following result

[('a', 'c'), ('a', 'b'), ('a', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('d', 'a'), ('d', 'c'), ('d', 'b')]

For my test case ('a','b') and ('b','a') are similar and I just want one of them in the list. I had to run one more loop for getting the unique pairs from the result.

So is there any efficient way to do it in Python (preferably in 2.x)? I want to remove nested loops.

Update:
I have checked with the possible flagged duplicate, but it's not solving the problem here. It's just providing different combination. I just need the pairs of 2. For that question a tuple of ('a','b','c') and ('a','b','c','d') are valid, but for me they are not. I hope, this explains the difference.

Possible duplicate of [How to get all possible combinations of a list’s elements?](https://stackoverflow.com/questions/464864/how-to-get-all-possible-combinations-of-a-list-s-elements) — Aran-Fey, Mar 26 '18 at 12:54
@Aran-Fey, please check the update. I don't require all of the possible combinations, but a subset of those combinations. — 0xC0DED00D, Mar 26 '18 at 13:03
@noob you require *all combinations*. Did you actually try that answer? Or looked at the three answers in this question, which all use `itertools.combinations(data, 2)`? — juanpa.arrivillaga, Mar 26 '18 at 13:05
I don't see how it's _not_ a duplicate... well, my eyes are deceiving me those days, so I may be wrong. — Jean-François Fabre, Mar 26 '18 at 13:06
@noob Well, the answer uses a loop to generate combinations of increasing length, so it's trivial to apply it to your use case... but maybe you'd be happier with [this](https://stackoverflow.com/questions/20762574/combinations-with-two-elements) question? — Aran-Fey, Mar 26 '18 at 13:10
ok, the question asked for all the combination, but I asked for combinations of length 2. The accepted answer solves the problem. I didn't get the chance to try the answer. My bad :-( — 0xC0DED00D, Mar 26 '18 at 13:10

sjw · Accepted Answer · 2018-03-26T13:03:55.327

10

Sounds like a job for itertools.

from itertools import combinations
test_dict = {'a':1, 'b':2, 'c':3, 'd':4}
results = list(combinations(test_dict, 2))

[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

I should add that although the output above happens to be sorted, this is not guaranteed. If order is important, you can instead use:

results = sorted(combinations(test_dict, 2))

edited Mar 26 '18 at 13:03

answered Mar 26 '18 at 12:53

sjw

6,213
2
24
39

juanpa.arrivillaga · Answer 2 · 2018-03-26T13:00:22.320

Since dictionary keys are unique, this problem becomes equivalent of finding all combinations of the keys of size 2. You can just use itertools for that:

>>> test_dict = { 'a':1,'b':2,'c':3,'d':4}
>>> import itertools
>>> list(itertools.combinations(test_dict, 2))
[('c', 'a'), ('c', 'd'), ('c', 'b'), ('a', 'd'), ('a', 'b'), ('d', 'b')]

Note, these will come in no particular order, since dict objects are inherently unordered. But you can sort before or after, if you want sorted order:

>>> list(itertools.combinations(sorted(test_dict), 2))
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]
>>>

Note, this algorithm is relatively simple if you are working with sequences like a list:

>>> ks = list(test_dict)
>>> for i, a in enumerate(ks):
...     for b in ks[i+1:]: # this is the important bit
...         print(a, b)
...
c a
c d
c b
a d
a b
d b

Or more succinctly:

>>> [(a,b) for i, a in enumerate(ks) for b in ks[i+1:]]
[('c', 'a'), ('c', 'd'), ('c', 'b'), ('a', 'd'), ('a', 'b'), ('d', 'b')]
>>>

score 3 · Answer 3 · answered Mar 26 '18 at 12:54

itertools.combinations does just what you want:

from itertools import combinations

test_dict = { 'a':1,'b':2,'c':3,'d':4}
keys = tuple(test_dict)
combs = list(combinations(keys, 2))
print(combs)
# [('a', 'd'), ('a', 'b'), ('a', 'c'), ('d', 'b'), ('d', 'c'), ('b', 'c')]

combs = list(combinations(test_dict, 2)) would just do; iterating over a dictionary is just iterating over its keys...

Find all unique pairs of keys of a dictionary

3 Answers3

Linked