title: Efficient combinations with replacement for multiple iterables, or order-independent product
body: <p>I'm trying to find a performant solution in Python that works like so:</p>
  
  <pre><code>&gt;&gt;&gt; func([1,2,3], [1,2])
  [(1,1), (1,2), (1,3), (2,2), (2,3)]
  </code></pre>
  
  <p>This is similar to <code>itertools.combinations_with_replacement</code>, except that it can take multiple iterables. It's also similar to <code>itertools.product</code>, except that it omits order-independent duplicate results.</p>
  
  <p>All of the inputs will be prefixes of the same series (i.e. they all start with the same element and follow the same pattern, but might have different lengths).</p>
  
  <p>The function must be able to take any number of iterables as input.</p>
  
  <p>Given a set of lists <em>A</em>, <em>B</em>, <em>C</em>, ..., here is a sketch of an algorithm that generates those results.</p>
  
  <pre><code>assert len(A) &lt;= len(B) &lt;= len(C) &lt;= ...
  for i in 0..len(A)
    for j in i..len(B)
      for k in j..len(C)
          .
          .
          .
        yield A[i], B[j], C[k], ...
  </code></pre>
  
  <h3>Things I can't do</h3>
  
  <ul>
  <li>Use <code>itertools.product</code> and filter the results. This has to be performant.</li>
  <li>Use recursion. The function overhead would make it slower than using <code>itertools.product</code> and filtering for a reasonable number of iterables.</li>
  </ul>
  
  <p>I suspect there's a way to do this with <code>itertools</code>, but I have no idea what it is.</p>
  
  <p><strong>EDIT:</strong> I'm looking for the solution that takes the least time.</p>
  
  <p><strong>EDIT 2:</strong> There seems to be some confusion about what I'm trying to optimize. I'll illustrate with an example.</p>
  
  <pre><code>&gt;&gt;&gt; len(list(itertools.product( *[range(8)] * 5 )))
  32768
  &gt;&gt;&gt; len(list(itertools.combinations_with_replacement(range(8), 5)))
  792
  </code></pre>
  
  <p>The first line gives the number of <strong>order-dependent</strong> possibilities for rolling 5 8-sided dice. The second gives the number of <strong>order-independent</strong> possibilities. Regardless of how performant <code>itertools.product</code> is, it'll take <strong>2 orders of magnitude</strong> more iterations to get a result than <code>itertools.combinations_with_replacement</code>. I'm trying to find a way to do something similar to <code>itertools.combinations_with_replacement</code>, but with multiple iterables that minimizes the number of iterations, or time performance. (<code>product</code> runs in <img src="https://latex.codecogs.com/gif.latex?%5Cinline%20O%28M%5EN%29" alt="math"> whereas <code>combinations_with_replacement</code> runs in <img src="https://latex.codecogs.com/gif.latex?%5Cinline%20O%5Cbinom%7BM&plus;N&plus;1%7D%7BN%7D" alt="math">, where M is the number of sides on the die and N is the number of dice) </p>