CODEWITHSUNDEEP
listpython-3.xcombinations
FlyingAura
FlyingAura

Reputation: 1601

Generate unique non repeating pairs in a list in O(n)

How do we generate unique non repeating pairs such that (x,y) = (y,x) are not repeated.

Say we have a list [3,6,9]. Then, answer is (3, 6) (3, 9) (6, 9) If the list is [3,6]. Then answer is (3,6)

This can be done using 2 for loops, but we want to be preferably done in O(n) (using max one loop)

Is there a pythonic way of doing this?

Upvotes: 1

Views: 1497

Answers (1)

RemcoGerlich
RemcoGerlich

Reputation: 31260

The Pythonic way to do it is to use the standard library generator (https://docs.python.org/2.7/library/itertools.html#itertools.combinations):

from itertools import combinations

for comb in combinations([3,6,9], 2):
    print(comb)

As the docs say, the number of combinations is n! / (2 * (n-2)!), which I guess is O(n^2). So it can't be done in O(n) time.

Upvotes: 1

Related Questions