Permutations with replacement in Python Many a times, I've had the need to use a permutations with replacement function.

So, I've written a function to do just that:

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def permutations_with_replacement(n: int, m: int, cur=None):
    if cur is None:
        cur = []

    if n == 0:
        yield cur
        return

    for i in range(1, m + 1):
        yield from permutations_with_replacement(n - 1, m, cur + [i])

if __name__ == '__main__':
    n = int(input("Please enter 'N': "))
    m = int(input("Please enter 'M': "))

    for i in permutations_with_replacement(n, m):
        print(*i)


There's a better way to do this if we used itertools.product, but there's no fun in that!

from itertools import product

def permutations_with_replacement(n, m):
    for i in product(list(range(1, m + 1)), repeat=n):
        yield i

if __name__ == '__main__':
    n = int(input("Please enter 'N': "))
    m = int(input("Please enter 'M': "))

    for i in permutations_with_replacement(n, m):
        print(*i)


I don't like the way I've implemented cur in my code. Is there any better way to do that?
First of all, this is a very nicely written code.

Before writing about the cur implementation, a few notes:


I do not think n and m should be in main. It creates shadowing in the function.
I added type annotation to the return value of the function. Since it's a generator it should be: Iterator[List[int]].


So you said you do not like the way cur is implemented in your code, I thought of a way to take it out of the function declaration.
I created a sub function that is recursive taken out the cur variable. This is how it turned out:

def permutations_with_replacement(n: int, m: int) -&gt; Iterator[List[int]]:
    cur = []

    def permutations_with_replacement_rec(n_rec: int, m_rec: int) -&gt; Iterator[List[int]]:
        nonlocal cur

        if n_rec == 0:
            yield cur
            return

        for i in range(1, m_rec + 1):
            cur = cur + [i]
            yield from permutations_with_replacement_rec(n_rec - 1, m_rec)
            cur.pop()

    yield from permutations_with_replacement_rec(n, m)


Now notice that I needed to add a pop to the variable since now it keeps the elements after the call to the function.
Also I needed to use the nonlocal term so the function will know the cur variable.

The full code (with tests):

from itertools import product
from typing import Iterator, List

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)


def permutations_with_replacement(n: int, m: int) -&gt; Iterator[List[int]]:
    cur = []

    def permutations_with_replacement_rec(n_rec: int, m_rec: int) -&gt; Iterator[List[int]]:
        nonlocal cur

        if n_rec == 0:
            yield cur
            return

        for i in range(1, m_rec + 1):
            cur = cur + [i]
            yield from permutations_with_replacement_rec(n_rec - 1, m_rec)
            cur.pop()

    yield from permutations_with_replacement_rec(n, m)


def test_permutations_with_replacement():
    n = 3
    m = 4
    assert set(product(list(range(1, m + 1)), repeat=n)) == set(tuple(i) for i in permutations_with_replacement(n, m))


def main():
    n = int(input("Please enter 'N': "))
    m = int(input("Please enter 'M': "))

    for i in permutations_with_replacement(n, m):
        print(*i)


if __name__ == '__main__':
    main()