Your solution is a bit different from what I was thinking about (I was
thinking about a generator function, with yield), but it works.
This line:
return itertools.chain(Can be written in a simpler way:
itertools.imap(lambda ys: x + ys, ncsub(xs, s + p1)),
ncsub(xs, s + p2))
return chain((x + ys for ys in ncsub(xs, s + p1)), ncsub(xs, s + p2))
I'll think more about all this,
bye and thank you,
bearophile