Алгоритм создания бинарного шаблона

Question

У меня есть два числа: n и sp. Я хочу создать шаблон элементов списка с элементами sp, которые вращаются как двоичные цифры до n. Чтобы подробнее остановиться на второй части, вот пример:

n = 2, sp = 3
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

Аналогично:

n = 3, sp = 3
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 2, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 1]
[0, 2, 2]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 2, 0]
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 2, 2]
[2, 0, 0]
[2, 0, 1]
[2, 0, 2]
[2, 1, 0]
[2, 2, 0]
[2, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 2, 2]

Я хочу сохранить порядок, который я дал в примерах, то естьСначала назначается LSB, затем следующий бит и так далее ...

Я не мог придумать какой-либо тактики для решения такой проблемы. Все, что я мог понять, это использовать sp для создания временного списка размером sp, например, если sp == 3, temp_list может быть [0 0 0]. Затем мы выполняем итерацию таким образом, чтобы получить шаблон.

Нет никаких ограничений на сложность алгоритма, хотя более короткий алгоритм был бы очень хорош.

Answer 1

Я написал это

n = 4 # base
sp = 2 # length

def fix(num, base):
    for j in range(len(num)):
        if num[j] == base:
            num[j] = 0
            num[j+1] += 1
    return num

num= [ 0 for _ in range(sp)]
print(num)
for i in range(n**sp -1):
    num[0] += 1
    num= fix(num, n)
    print(num[::-1])

Answer 2

Один простой способ сделать это:

def get_patterns(n, sp):
    ans = []

    def _get_patterns(so_far):
        if len(so_far) == sp:
            ans.append(so_far[:])
            return

        for i in range(n):
            so_far.append(i)
            _get_patterns(so_far)
            so_far.pop()

    _get_patterns([])
    return ans

n = 3
sp = 3

assert get_patterns(n, sp) == sorted([
    [0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], 
    [0, 2, 0], [0, 1, 1], [0, 1, 2], [0, 2, 1], [0, 2, 2],

    [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 1, 0],
    [1, 2, 0], [1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2],

    [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 1, 0], 
    [2, 2, 0], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2],
])