Algorithmic complexity of this algorithm to find all ordered permutations of length X
def generate_permutations(symbols, permutations_length):



These are not permutations. They are Cartesian products. In addition, calling the function generate_something suggests that what's returned might be a generator, which is probably what you want for a function which returns a stupendously large data structure, but is not what you get from this function.




    for symbol in symbols:
        for tail in tails:
            permutation = [symbol] + tail

            permutations.append(permutation)



If you use extend instead of append then you give better hints as to how much underlying buffers might need to be increased:

    for tail in tails:
        result.extend([symbol] + tail for symbol in symbols)




Performance: with an alphabet of size \$L\$ let \$T_L(X)\$ be the cost of calling this function for products of length \$X\$. Then \$T_L(1) = L\$ and \$T_L(X+1) = T_L(X) + L L^X (X+2)\$ assuming that constructing the list [symbol] + tail takes time proportional to its length and extending the list of results take amortised constant time per element added. This gives \$\Theta(L^{X}X)\$ complexity.



The same complexity but much better memory efficiency can be achieved with a true generator approach which is based on the fact that all you really need to do is count to \$L^X\$ and convert into base \$L\$.