Algorithm to generate length $n$ strings of $4$ colors such that no two subsequent colors are the same

Question

Alice is preparing decorations to decorate the classroom for Children's Day. She is using beads in the colors red (r), green (g), blue (b), and yellow (y) to create strings of beads. During the class meeting, it was established that two beads of the same color cannot be placed next to each other.

Help Alice design the strings of beads and write a function called "beads(lk)" where the result is a sorted list of words representing the strings that can be constructed using all available beads. The parameter "lk" is a four-element list of numbers that specify the number of red, green, blue, and yellow beads, respectively. The maximum total number of beads is n=10.

Here is my solution using permutation, but the complexity is high.

from itertools import permutations

def beads(lk):
    colors = ['r', 'g', 'b', 'y']
    all = []
    for i in range(len(lk)):
        for j in range(lk[i]):
            all.append(colors[i])
    all_possible_combinations = []
    
    for perm in permutations(all):
        valid = True
        for i in range(len(perm) - 1):
            if perm[i] == perm[i + 1]:
                    valid = False
                    break
        if valid:
            all_possible_combinations.append("".join(perm))
    unique_combinations = sorted(set(all_possible_combinations))

    return unique_combinations

I am looking for a better complexity algorithm, now is O(n!). Can you provide me with some ideas?

Edit

Thanks @Yves for your suggestion:

def beads(lk):
    def recursive_beads(prev_color, remaining, current_string):
        valid_strings = []
        if sum(remaining) == 0:
            return [current_string]
        for color, count in enumerate(remaining):
            if count > 0 and color != prev_color:
                new_remaining = list(remaining)
                new_remaining[color] -= 1
                valid_strings.extend(recursive_beads(color, new_remaining, current_string + colors[color]))

        return valid_strings

    colors = ['r', 'g', 'b', 'y']
    result = []
    valid_strings = recursive_beads(4, lk, "")

    return valid_strings

Answer 1

Use a recursive function that takes as input

• the string assembled so far,

• the remaining amounts of beads of every color.

In this function, you will try and add a bead of every color (if available, and different from the previous), and recurse until no bead remains.

---

I believe that this is close to optimal, but the complexity is pretty difficult to evaluate.