How To Nest Itertools Products?

Given a list, I can get the product of each item in a list as such: from itertools import product x = 'apple orange pair None'.split() [i + ' ' + j for i, j in product(x, x)] [out

Solution 1:

The point lies in that a recursive procedure naturally forms a recursive pattern.

To just illustrate the idea, the 'None' is not replaced with '' because of simplicity. In the further solution, it is done for the nested patterns.

def product_combine(a, b):
  return [i + ' ' + j for i, j in product(a, b)]

# for n times of nesting
def products_combine(x, n):
  if n == 0:
    return x
  else:
    return product_combine(x, products_combine(x, n-1)) + products_combine(x, n-1)

x = 'apple orange pair None'.split()    
print(products_combine(x, 3))

If in case, you need different data types to hold your result. A bit more generic solution allows more flexible choice of output data types:

# for different types of combination
def products_combine(combine):
  def products(x, n):
    if n == 0:
      return x
    else:
      return combine(x, products(x, n-1)) + products(x, n-1)
  return products

# combine to string ('None' is replaced for nested patterns, not for initial)
def tostr(a, b):
  NoneToEmpty = lambda x: '' if x == 'None' else x
  return [' '.join(map(NoneToEmpty, (i, j))).strip() for i, j in product(a, b)]

# combine to iterator (list/tuple)
def toiter(iter_type):
  def to_thatiter(a, b):
    return [iter_type((i,))+j if isinstance(j, iter_type) else iter_type((i, j)) for i, j in product(a, b)]
  return to_thatiter

tolist=toiter(list)
totuple=toiter(tuple)

products_str=products_combine(tostr)
products_list=products_combine(tolist)
products_tuple=products_combine(totuple)

x = 'apple orange pair None'.split()
print(products_str(x, 3))
print(products_list(x, 3))
print(products_tuple(x, 3))

The general form is for any binary function f(x, x), nest it to f(x, f(x, f(x,...f(x, f(x, x)). A generic approach for not only product but arbitrary binary operation would be:

def nest(f_binary, n):
  def g(x):
    if n == 1:
      return x
    else:
      return f_binary(x, nest(f_binary, n-1)(x))
  return g

add = lambda x, y: x + y
power = lambda x,y: x**y
concatenate = lambda l1, l2: l1 + l2

x = 'apple orange pair None'.split()
print(list(nest(product, 3)(x)))
print(nest(add, 3)(5))
print(nest(power,3)(5))
print(nest(concatenate, 3)(['a','b']))

A different idea is using number of arguments instead of explicit integer N to indicate the level of nesting. It looks weird, but it works.

def nest(f):
  def expand(x, *args):
    return x if not args else f(x, expand(*args))
  return expand

products = nest(product)

x = 'apple orange pair None'.split()

# instead of giving N, you call products with number n of argument x
# indicating n levels of nesting (here: 3 x, product(x, product(x, x))
print(list(products(x, x, x)))