Find all possible arrangements of 2 different items, arrangement has a max of k consecutive elements

297

The problem involves finding the total number of possible arrangements of two different types of items. For example a red item is 'r' and a blue item is 'b'.
Arrangement can only have max k consecutive elements.

if r=2, b=1, and k=1, the only solution is 'rbr'

if r=3, b=2, and k=2, -> 'rbrbr', 'brrbr', 'rrbbr', 'rbrrb', 'rrbrb', 'brbrr', 'rbbrr'

def order(r, b, k):
    arrange('', r, b, k, 'r')

def arrange(seq, r, b, k, c):
    # print(seq)
    # check consecutive
    past = seq[-k - 1:]
    check = c * (k + 1)

    if past == check:
        return

    # check empty
    if (r == 0):
        if b <= k:
            new = seq
            new += ('b' * b)
            s.add(new)
        return

    elif (b == 0):
        if r <= k:
            new = seq
            new += ('r' * r)
            s.add(new)
        return

    arrange(seq + 'r', r - 1, b, k, 'r')
    arrange(seq + 'b', r, b - 1, k, 'b')

The problem here, is at bigger values of r and b, it takes too long to complete. Is there a better algorithm to get the answer faster?

s = set([])
r = 3
b = 2
k = 2

order(r, b, k)
print(len(s))
print(s)

{'rbrbr', 'brrbr', 'rrbbr', 'rbrrb', 'rrbrb', 'brbrr', 'rbbrr'}

Comments (1)