Operation on every pair of element in a list

Question

Using Python, I'd like to compare every possible pair in a list.

Suppose I have

my_list = [1,2,3,4]

I'd like to do an operation (let's call it foo) on every combination of 2 elements from the list.

The final result should be the same as

foo(1,1)
foo(1,2)
...
foo(4,3)
foo(4,4)

My first thought was to iterate twice through the list manually, but that doesn't seem very pythonic.

Answer 1

Check out product() in the itertools module. It does exactly what you describe.

import itertools

my_list = [1,2,3,4]
for pair in itertools.product(my_list, repeat=2):
    foo(*pair)

This is equivalent to:

my_list = [1,2,3,4]
for x in my_list:
    for y in my_list:
        foo(x, y)

Edit: There are two very similar functions as well, permutations() and combinations(). To illustrate how they differ:

product() generates every possible pairing of elements, including all duplicates:

1,1  1,2  1,3  1,4
2,1  2,2  2,3  2,4
3,1  3,2  3,3  3,4
4,1  4,2  4,3  4,4

permutations() generates all unique orderings of each unique pair of elements, eliminating the x,x duplicates:

 .   1,2  1,3  1,4
2,1   .   2,3  2,4
3,1  3,2   .   3,4
4,1  4,2  4,3   .

Finally, combinations() only generates each unique pair of elements, in lexicographic order:

 .   1,2  1,3  1,4
 .    .   2,3  2,4
 .    .    .   3,4
 .    .    .    .

All three of these functions were introduced in Python 2.6.

Answer 2

I had a similar problem and found the solution here. It works without having to import any module.

Supposing a list like:

people = ["Lisa","Pam","Phil","John"]

A simplified one-line solution would look like this.

All possible pairs, including duplicates:

result = [foo(p1, p2) for p1 in people for p2 in people]

All possible pairs, excluding duplicates:

result = [foo(p1, p2) for p1 in people for p2 in people if p1 != p2]

Unique pairs, where order is irrelevant:

result = [foo(people[p1], people[p2]) for p1 in range(len(people)) for p2 in range(p1+1,len(people))]

---

In case you don't want to operate but just to get the pairs, removing the function foo and using just a tuple would be enough.

All possible pairs, including duplicates:

list_of_pairs = [(p1, p2) for p1 in people for p2 in people]

Result:

('Lisa', 'Lisa')
('Lisa', 'Pam')
('Lisa', 'Phil')
('Lisa', 'John')
('Pam', 'Lisa')
('Pam', 'Pam')
('Pam', 'Phil')
('Pam', 'John')
('Phil', 'Lisa')
('Phil', 'Pam')
('Phil', 'Phil')
('Phil', 'John')
('John', 'Lisa')
('John', 'Pam')
('John', 'Phil')
('John', 'John')

All possible pairs, excluding duplicates:

list_of_pairs = [(p1, p2) for p1 in people for p2 in people if p1 != p2]

Result:

('Lisa', 'Pam')
('Lisa', 'Phil')
('Lisa', 'John')
('Pam', 'Lisa')
('Pam', 'Phil')
('Pam', 'John')
('Phil', 'Lisa')
('Phil', 'Pam')
('Phil', 'John')
('John', 'Lisa')
('John', 'Pam')
('John', 'Phil')

Unique pairs, where order is irrelevant:

list_of_pairs = [(people[p1], people[p2]) for p1 in range(len(people)) for p2 in range(p1+1,len(people))]

Result:

('Lisa', 'Pam')
('Lisa', 'Phil')
('Lisa', 'John')
('Pam', 'Phil')
('Pam', 'John')
('Phil', 'John')

Edit: After the rework to simplify this solution, I realised it is the same approach than Adam Rosenfield. I hope the larger explanation helps some to understand it better.

Answer 3

If you're just calling a function, you can't really do much better than:

for i in my_list:
    for j in my_list:
        foo(i, j)

If you want to collect a list of the results of calling the function, you can do:

[foo(i, j) for i in my_list for j in my_list]

which will return you a list of the result of applying foo(i, j) to each possible pair (i, j).

Answer 4

my_list = [1,2,3,4]

pairs=[[x,y] for x in my_list for y in my_list]
print (pairs)

Answer 5

Ben Bank's answer works well if you want the combinations to be ordered lexicographically. However, if you want the combinations to be randomly ordered, here's a solution:

import random
from math import comb


def cgen(i,n,k):
    """
    returns the i-th combination of k numbers chosen from 0,1,...,n-1
    
    forked from: https://math.stackexchange.com/a/1227692
    changed from 1-indexed to 0-indexed.
    """
    # 1-index
    i += 1
    
    c = []
    r = i+0
    j = 0
    for s in range(1,k+1):
        cs = j+1
        while r-comb(n-cs,k-s)>0:
            r -= comb(n-cs,k-s)
            cs += 1
        c.append(cs-1)
        j = cs
    return c


def generate_random_combinations(n, k, shuffle=random.shuffle):
    """
    Generate combinations in random order of k numbers chosen from 0,1,...,n-1.
    
    :param shuffle: Function to in-place shuffle the indices of the combinations. Use for seeding.
    """
    total_combinations = comb(n, k)
    combination_indices = list(range(total_combinations))
    shuffle(combination_indices)
    
    for i in combination_indices:
        yield cgen(i, n, k)

Example Usage

For N=100 and k=4:

gen_combos = generate_random_combinations(100, 4)

for i in range(3):
    print(next(gen_combos))

results in:

[4, 9, 55, 79]
[11, 49, 58, 64]
[75, 82, 83, 91]

Use Case

For my use case, I'm implementing an algorithm that's searching for a single (or a few) combination and halts when it finds a valid combination. On average, it traverses a very small subset of all possible combinations, so there's no need to build all possible combinations up front and then shuffle (the population size is too big to fit all combinations in memory, anyway).

The randomness is crucial to finding a solution quickly because lexicographic ordering results in a single value in the population being included in all combinations until it's exhausted. For example, if we have n=100 and k=4, then the results will be like:

index	combination
0	(0, 1, 2, 3)
1	(0, 1, 2, 4)
2	(0, 1, 2, 5)
...
156848	(0, 97, 98, 99)
156849	(1, 2, 3, 4)

If 0 is not part of a valid solution, then we will have searched 156849 combinations for no reason. Randomizing the order helps mitigate this issue (see example output above).