Equivalent Nested Loop Structure with Itertools

Question

Accepted Answer

There's no exact `itertools` solution, but a simple combination of `itertools` functions will suffice:

```
def chain_imap_accumulate(seq, f):
    def acc_f(x):
        for n in f(x[-1]):
            yield x + (n,)
    return chain.from_iterable(imap(acc_f, seq))

def accumulative_product(*generators):
    head, tail = generators[0], generators[1:]
    head = imap(tuple, head())
    return reduce(chain_imap_accumulate, tail, head)
```

A quick test. Definitions:

```
from itertools import chain, imap, izip
chain_ = chain.from_iterable

def A():
    yield 'A'
    yield 'B'

def B(x):
    yield int(x, 16)
    yield int(x, 16) + 1

def C(x):
    yield str(x) + 'Z'
    yield str(x) + 'Y'
```

And the result:

```
>>> list(accumulative_product(A, B, C))
[('A', 10, '10Z'), ('A', 10, '10Y'), 
 ('A', 11, '11Z'), ('A', 11, '11Y'), 
 ('B', 11, '11Z'), ('B', 11, '11Y'), 
 ('B', 12, '12Z'), ('B', 12, '12Y')]
```

Almost all the complexity comes from the accumulation of inputs, as a quick "derivation" of the above code shows. The final (`c`) values can be generated using just a couple of nested `itertools` constructs:

```
>>> list(chain_(imap(C, chain_(imap(B, (A()))))))
['10Z', '10Y', '11Z', '11Y', '11Z', '11Y', '12Z', '12Y']
```

This can be generalized with `reduce`. To work with `reduce`, `chain_imap` can't use the standard `imap` argument order. It has to be swapped:

```
def chain_imap(seq, f):
    return chain.from_iterable(imap(f, seq))
```

This gives the same results:

```
>>> list(reduce(chain_imap, [B, C], A()))
['10Z', '10Y', '11Z', '11Y', '11Z', '11Y', '12Z', '12Y']
```

The final task is accumulating the initial values, so that you have access to `a`, `b`, and `c`. This takes a bit of thought to get right, but the implementation is fairly simple -- we just have to convert `f` into a function that ignores all input values but the last, and appends new values to the full input:

```
def chain_imap_accumulate(seq, f):
    def acc_f(x):
        for n in f(x[-1]):
            yield x + (n,)
    return chain.from_iterable(imap(acc_f, seq))
```

This requires that the first inputs be wrapped in tuples, so we map `A` with `tuple`:

```
>>> list(reduce(chain_imap_accumulate, [B, C], imap(tuple, A())))
[('A', 10, '10Z'), ('A', 10, '10Y'), 
 ('A', 11, '11Z'), ('A', 11, '11Y'), 
 ('B', 11, '11Z'), ('B', 11, '11Y'), 
 ('B', 12, '12Z'), ('B', 12, '12Y')]
```

Rewrite the above for clarity, and the code at the top of this answer results.

By the way, `chain_imap_accumulate` can be rewritten a bit more tersely using a genex. This can be combined with a shorter version of `accumulative_product` for a very compact definition (if you're interested in that kind of thing). This also happens to eliminate the itertools dependency entirely:

```
def chain_map_accumulate(seq, f):
    return (x + (n,) for x in seq for n in f(x[-1]))

def accumulative_product2(*gens):
    return reduce(chain_map_accumulate, gens[1:], (tuple(x) for x in gens[0]()))
```

Equivalent Nested Loop Structure with Itertools

Solution

Problem