How to nest itertools products?

Question

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]:

['apple apple',
 'apple orange',
 'apple pair',
 'apple None',
 'orange apple',
 'orange orange',
 'orange pair',
 'orange None',
 'pair apple',
 'pair orange',
 'pair pair',
 'pair None',
 'None apple',
 'None orange',
 'None pair',
 'None None']

If I want to nest the output of product(list, list) with the initial list, I could do:

from itertools import product
x = 'apple orange pair None'.split()
for i, j in product(x, x):
    i = '' if i == 'None' else i
    j = '' if j == 'None' else j
    y = i + ' ' + j
    y = y.strip()
    print(y)
    for k, l in product(x, [y]):
        k = '' if k == 'None' else k
        l = '' if l == 'None' else l
        z = k + ' ' + l
        z = z.strip()
        print(z) 

[out]:

apple apple
apple apple apple
orange apple apple
pair apple apple
apple apple
apple orange
apple apple orange
orange apple orange
pair apple orange
apple orange
apple pair
apple apple pair
orange apple pair
pair apple pair
apple pair
apple
apple apple
orange apple
pair apple
apple
orange apple
apple orange apple
orange orange apple
pair orange apple
orange apple
orange orange
apple orange orange
orange orange orange
pair orange orange
orange orange
orange pair
apple orange pair
orange orange pair
pair orange pair
orange pair
orange
apple orange
orange orange
pair orange
orange
pair apple
apple pair apple
orange pair apple
pair pair apple
pair apple
pair orange
apple pair orange
orange pair orange
pair pair orange
pair orange
pair pair
apple pair pair
orange pair pair
pair pair pair
pair pair
pair
apple pair
orange pair
pair pair
pair
apple
apple apple
orange apple
pair apple
apple
orange
apple orange
orange orange
pair orange
orange
pair
apple pair
orange pair
pair pair
pair

apple
orange
pair

If I want to get to another level of nesting, I could hard code it:

from itertools import product
x = 'apple orange pair None'.split()
for i, j in product(x, x):
    i = '' if i == 'None' else i
    j = '' if j == 'None' else j
    y = i + ' ' + j
    y = y.strip()
    print(y)
    for k, l in product(x, [y]):
        k = '' if k == 'None' else k
        l = '' if l == 'None' else l
        z = k + ' ' + l
        z = z.strip()
        print(z)
        for m, n in product(x, [z]):
            m = '' if m == 'None' else m
            n = '' if n == 'None' else n
            zz = m + ' ' + n
            zz = zz.strip()
            print(zz)

But is there some other way to achieve the same output without hard coding it?

Answer 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)))