4

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?

5
  • 1
    you return immediately on your first, inner, iteration. You need to materialize and return a list to have the equivalent function Jun 17, 2019 at 0:03
  • @juanpa.arrivillaga This part? if n == 0: return [[]] If so, how do you mean? I thought the empty case was returning a list, within which is an empty list?
    – Eddie
    Jun 17, 2019 at 0:14
  • In the else clause. Again, you return immediately after the first iteration. return [j + [i]] Jun 17, 2019 at 2:45
  • @juanpa.arrivillaga Aren't they both issuing a return statement immediately after the else clause? It could be I'm misunderstanding something about List Comprehension... What is the list comprehension statement doing that the nested for loops are not?
    – Eddie
    Jun 17, 2019 at 3:26
  • 2
    Simply stated, the list comprehension creates a list, whereas your for-loop does not. It simply returns the first element of the list that would have been created immediately Jun 17, 2019 at 4:48

2 Answers 2

4

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)
5
  • This is helpful. Thank you. However, it doesn't answer the question of why the return statement in the first function is functioning differently than the return function in the second function. I understand that yield let's you return more than one item as a generator, but how come the return in the first function has the desired effect, compared to the 2nd function?
    – Eddie
    Jun 17, 2019 at 1:45
  • @Eddie because you're in a for loop. It gets executed multiple times
    – flakes
    Jun 17, 2019 at 1:55
  • Isn't the List Comprehension function also in a loop? What is going on in the list comprehension that is not going on in the nested for loops?
    – Eddie
    Jun 17, 2019 at 3:27
  • Just to nitpick, in Python 3, iter(range(1000...)) creates an iterator. range(...) creates a range object, which happens to be iterable, but is not itself a generator. Jun 17, 2019 at 5:09
  • Thanks flakes! I appreciate the added clarity.
    – Eddie
    Jun 18, 2019 at 16:37
1
> 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 ..
3
  • 2
    Dont create the result list outside the method. This causes unintended side effects for multiple calls to the method.
    – flakes
    Jun 17, 2019 at 4:44
  • yeahh my bad.. to explain him better i made list outside the function Jun 17, 2019 at 4:46
  • Also, as it stands this method will create a list of list of list, not a list of list. The result of j + [i] is already a list, meaning that you create [[j0 + [i0]], [j1 + [i1]], ...] instead of something like [j0 + [i0], j1 + [i1], ...]. I find it helpful to pump my code through an interpreter as a sanity check before posting.
    – flakes
    Jun 17, 2019 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.