List comprehension behavior in python

Question

I am working with Codeskulptor on a rock collision problem. I want to check collisions between rocks and my rocks are in a list. I came up with the solution to build a list of combinations and then check for collision. I do not have itertools available. My combination list was created like this:

def combinations(items):
    n_items = [(n,item) for n,item in enumerate(items)]
    return [(item,item2) for n,item in n_items for m,item2 in n_items[n:] if n != m]

letters = ['A','B','C','D']
print combinations(letters)

[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

The result is ok.

I tried to do this in a one liner before with functions:

def combinations2(items):
    return [(item,item2) for n,item in enumerate(items) for m,item2 in enumerate(items[n:]) if n != m]

letters = ['A','B','C','D']
print combinations2(letters)

But the outcome is completely different and wrong:

[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'B'), ('B', 'D'), ('C', 'C'), ('C', 'D'), ('D', 'D')]

List comprehension is still a little black magic to me. I cannot explain this behavior, would like to understand the wrong out though. I know that my two line solution is much faster, since enumerate is only done once and than used. But the wrong output is unexplainable to me, especially as BC is missing and BB CC DD doubles are there while AA is missing.

Can someone help me?

Why don't you use https://docs.python.org/3.4/library/itertools.html#itertools.combinations? :) — Alessandro Suglia, May 19 '14 at 16:33
@AlessandroSuglia: first paragraph in the post: *I do not have itertools available*. — Martijn Pieters, May 19 '14 at 16:54

Martijn Pieters · Accepted Answer · 2014-05-19T16:54:19.910

First thing to do when understanding a list comprehension is to expand it to a regular set of for loops. Read the loops from left to right and nest accordingly.

Working code:

def combinations(items):
    n_items = []
    for n,item in enumerate(items):
        n_items.append((n,item))
    result = []
    for n, item in n_items:
        for m, item2 in n_items[n:]:
            if n != m:
                result.append((item, item2))
    return result

and your attempt that doesn't work:

def combinations2(items):
    result = []
    for n, item in enumerate(items):
        for m, item2 in enumerate(items[n:]):
            if n != m:
                result.append((item, item2))
    return result

Perhaps this way it is easier to see what goes wrong between the two versions.

Your version slices just items, not the indices produced by enumerate(). The original version slices [(0, 'A'), (1, 'B'), (2, 'C'), (3, 'D')] down to [(1, 'B'), (2, 'C'), (3, 'D')], etc. while your version re-numbers that slice to [(0, 'B'), (1, 'C'), (2, 'D')]. This in turn leads to your erroneous output.

Start the inner loop at the higher index by adding a second argument to the enumerate() function, the index at which to start numbering:

def combinations2(items):
    result = []
    for n, item in enumerate(items):
        for m, item2 in enumerate(items[n:], n):
            if n != m:
                result.append((item, item2))
    return result

Back to a one-liner:

def combinations2(items):
    return [(item, item2) for n, item in enumerate(items) for m, item2 in enumerate(items[n:], n) if n != m]

This then works correctly:

>>> def combinations2(items):
...     return [(item, item2) for n, item in enumerate(items) for m, item2 in enumerate(items[n:], n) if n != m]
... 
>>> letters = ['A','B','C','D']
>>> combinations2(letters)
[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

Note that you can simplify it further; the only time when n == m is True is for the first iteration of each inner loop. Just slice the items list for the inner list one value further; start the outer enumerate() at 1, drop the inner enumerate() and drop the n != m test:

def combinations3(items):
    result = []
    for n, item in enumerate(items, 1):
        for item2 in items[n:]:
            result.append((item, item2))
    return result

or as a list comprehension:

def combinations3(items):
    return [(item, item2) for n, item in enumerate(items, 1) for item2 in items[n:]]

Thank you very much. Now it is clear. I'll save your technique rewriting in a for loop for later. Also I hadn't in mind that enumerate can start at any index. Somehow logic, but nevertheless overseen by me. — Johannes Maria Frank, May 19 '14 at 16:50

score 1 · Answer 2 · answered May 19 '14 at 16:53

1

Just skip the clashes in the iterator.

>>> letter = ['A', 'B', 'C', 'D']
>>> list ( (x,y) for n, x in enumerate(letter) for y in letter[n+1:])
[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

answered May 19 '14 at 16:53

Charles Beattie

5,739
1
29
32

Wow, very short. Thank you. – Johannes Maria Frank May 19 '14 at 16:59

score 0 · Answer 3 · answered May 19 '14 at 16:41

0

Suppose you just want to get the list of combinations.

def combinations2(items):
    return filter(lambda (i,j): i <> j, [(i,j) for i in items for j in items])

letters = ['A','B','C','D']
print combinations2(letters)

The output I got is:

[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'),    ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]

answered May 19 '14 at 16:41

chapter3

914
2
12
21

Don't use `<>`; it is a deprecated alias for `!=` that has been removed from Python 3 altogether. – Martijn Pieters May 19 '14 at 16:42
Your code won't work correctly with `letters = ['A', 'A', 'B', 'B']`. – Martijn Pieters May 19 '14 at 16:42

List comprehension behavior in python

3 Answers3

Linked