Ad

Algorithm To Create A Binary-like Pattern

- 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.

Ad

Answer

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],
])
Ad
source: stackoverflow.com
Ad