iterate through all L length sequences of N symbols, that include all N symbols

Question

What is an efficient way to do the following in python?
Given N symbols, iterate through all L length sequences of N symbols, that include all N symbols.

The order does not matter, as long as all sequences are covered, and each only once.

Let's call this iterator seq(symbols,L). Then, for example,
list(seq([1,2,3],2))=[]
list(seq([1,2,3],3))=[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
list(seq([1,2,3],4))=[(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), ...

Here's an intuitive, yet slow implementation:

import itertools

def seq(symbols,L):
  for x in itertools.product(symbols,repeat=L):
    if all(s in x for s in symbols):
      yield x

When N is large and L is close to N, there is a lot of wasted effort. For example, when L==N, it would be much better to use itertools.permutations(). Since every sequence needs to have all N symbols, it seems like a better solution would somehow start with the permuted solution, then add in the extra repeated symbols somehow, but I can't figure out how to do this without double counting (and without resorting to saving all previous output to check for a repeat).

Answer 1

An idea:

import itertools
def solve(size, symbols, todo = None):
  if todo is None: todo = frozenset(symbols)
  if size < len(todo): return
  if size == len(todo):
    yield from itertools.permutations(todo)  # use sorted(todo) here 
                                             # for lexicographical order
    return
  for s in symbols:
    for xs in solve(size - 1, symbols, todo - frozenset((s,))):
      yield (s,) + xs

for x in solve(5, (1,2,3)):
  print(x)

Will print all sequences of size 5 that contain each of 1,2,3 and 2 more arbitrary elements. You can use bitmasks instead of a set if you aim for efficiency, but I guess you're not since you are using Python :) The complexity is optimal in the sense that it is linear in the output size.

Some "proof":

 $ python3 test.py | wc -l                               # number of output lines
 150
 $ python3 test.py | sort | uniq | wc -l                 # unique output lines
 150
 $ python3 test.py | grep "1"|grep "2"|grep "3"| wc -l   # lines with 1,2,3
 150

Answer 2

You can do this by breaking the problem into two parts:

1. Find every possible multiset of size L of N symbols which includes every symbol at least once.

2. For each multiset, find all unique permutations.

For simplicity, let's suppose the N symbols are the integers in range(N). Then we can represent a multiset as a vector of length N whose values are non-negative integers summing to L. To restrict the multiset to include every symbol at least once, we require that the values in the vector all be strictly positive.

def msets(L, N):
  if L == N:
    yield (1,) * L
  elif N == 1:
    yield (L,)
  elif N > 0:
    for i in range(L - N + 1):
      for m in msets(L - i - 1, N - 1):
        yield (i + 1,) + m

Unfortunately, itertools.permutations does not produce unique iterations of lists with repeating elements. If we were writing this in C++, we could use std::next_permutation, which does produce unique iterations. There is a sample implementation (in C++, but it's straightforward to convert it to Python) on the linked page.