Expanding python's list comprehension into nested for loops -- strange results

user_1110324 0
Viewed 143

I came across this function to return every combination of N values from an array:

def combs(a, n):
   if n == 0:
       return [[]]
   else:
       return [(x + [y]) for x in combs(a,n-1) for y in a]

For my own comprehension, I tried to convert it into a function using nested for loops:

def combinations(array,n):
    if n == 0:
        return [[]]
    else:
        for i in array:
            for j in combinations(array, n-1):
                return [j + [i]]

But I am getting different results than I am expecting.

>>> threes = ['aA','bB','cC']
>>> 
>>> combs(threes,2)
[['aA', 'aA'], ['aA', 'bB'], ['aA', 'cC'], ['bB', 'aA'], ['bB', 'bB'], ['bB', 'cC'], ['cC', 'aA'], ['cC', 'bB'], ['cC', 'cC']]
>>> 
>>> combinations(threes,2)
[['aA', 'aA']]
>>>

I've tried various versions of the line return [j+[i]] all with no success. Here are some examples:

                return (j + [i])

Traceback (most recent call last):
  File "...", line 24, in <module>
    print(combinations(threes,2))
  File "...", line 16, in combinations
    return (j + [i])
TypeError: can only concatenate str (not "list") to str

.

                return j + [i]

Traceback (most recent call last):
  File "...", line 24, in <module>
    print(combinations(threes,2))
  File "...", line 16, in combinations
    return j + [i]
TypeError: can only concatenate str (not "list") to str

Why is the first function's list comprehension returning something different then my expanded nested for loops version?

What would be the correct (functioning) method to convert the first function's list-comprehension and return value into the nested for loop strategy?

list-comprehension python-3.x python
2 Answers

If you really want to make this equivalent then you need to do a single return. When you perform a comprehension you're creating the list somewhat atomically, i.e the list is not accessible until it is fully constructed// there is no way to access the list until the list comprehension (construction) is complete. To perform it without the list comprehension you'll need to fill a mutable container and then do a single return at the end:

def combinations(array,n):
    if n == 0:
        return [[]]
    else:
        result = []
        for i in array:
            for j in combinations(array, n-1):
                result.append(j + [i])
        return result

This is a valid way of solving the problem, but I would also explore creating a generator function instead. Unlike the usual case where you can only return once from a function, a generator allows you to yield multiple times times from the function.

This strategy is helpful in cases where you don't want to block during creation, you don't want to force a particular container to be used, or generally if you want to simplify some logic. Additionally, if you only need to iterate over the result and don't actually need the whole list at once, then it has the added advantage of not loading the entire sequence into memory.

Generally I find these advantages a compelling enough reason to create most functions like this as generators. For short lists, a comprehension or standard list creation (as seen in the example above), are suitable enough for solving the problem.

One caveat is that you may have to pack the results into a container depending on what your application needs. This is because the generator creates each new entry on demand, and simply streams the results:

def combinations(array,n):
    if n == 0:
        yield []
    else:
        for i in array:
            for j in combinations(array, n-1):
                yield j + [i]

>>> print(list(combinations(['aA','bB','cC'], 2)))
[['aA', 'aA'], ['bB', 'aA'], ['cC', 'aA'], ['aA', 'bB'], ['bB', 'bB'], ['cC', 'bB'], ['aA', 'cC'], ['bB', 'cC'], ['cC', 'cC']]

If you want to use a comprehension with the advantages of a generator, then you can use the generator comprehension (with ( ) instead of [ ]) and the yield from statement:

def combs(a, n):
   if n == 0:
       yield []
   else:
       yield from (x + [y] for x in combs(a, n - 1) for y in a)
user_32805380 
> The list comprehension always returns a result list. 
> 
> But in your nested loop case you are not returning list so little
> modify in your case
> 
> 
  def combinations(array,n):
>     if n == 0:
>         return [[]]
>     else:
          result=[]
>         for i in array:
>             for j in combinations(array, n-1):
>                 result.append([j + [i]])
>         return result 
 In this you are returning the list of all iterations ..
user_96451540
Related