# Algorithm To Create A Binary-like Pattern

## 11 October 2019 - 1 answer

I have two numbers: `n` and `sp`. I want to create a pattern of list elements with `sp` elements that rotate like binary digits up to `n`. To elaborate more on the second part, here is an example:

``````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]
``````

Similarly:

``````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]
``````

I wish to maintain the order that I have given in the examples, that is the LSB is assigned first, then the next bit, and so on...

I could not think of any tactic to solve such a problem. All I could figure out is to use `sp` to create a temporary list of size `sp`, for instance, if `sp == 3`, the temp_list can be `[0 0 0]`. Then we iterate in a manner so that we get the pattern.

There is no constraint on the complexity of the algorithm, although a shorter algorithm would be very great.

One simple way of doing it is:

``````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],
])
``````