1
\$\begingroup\$

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars.

For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'a'], ['b', 'b'], ..., ['d', 'd']]

I'm not sure about its algorithmic complexity though (at least I know it's pretty horrible). I would say it's something around:

O(X * N^(L + X))

(where L is the number of different chars, 4 here because we have 'A', 'B', 'C', 'D', and X the length of the permutations we want to generate). Because I have 2 nested loops, which will be run X times (well, X-1 because of the special case when X = 1). Is it correct?

def generate_permutations(symbols, permutations_length):
    if permutations_length == 1:
        return [[symbol] for symbol in symbols]

    tails = generate_permutations(symbols, permutations_length-1)
    permutations = []

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

            permutations.append(permutation)

    return permutations

print(generate_permutations(['a', 'b', 'c', 'd'], 2))

By the way: I know this is not idiomatic Python and I apologize if it's ugly but it's just some prototyping I'm doing before writing this code in a different, less expressive language. And I also know that I could use itertools.permutations to do this task. By the way, I'd be interested if someone happens to know the algorithmic complexity of itertool's permutations function.

\$\endgroup\$
  • \$\begingroup\$ "And I also know that I could use itertools.permutations to do this task." So why didn't you? \$\endgroup\$ – Mast Apr 27 '18 at 11:25
  • \$\begingroup\$ For the sake of the exercise and to learn how to do things by myself. \$\endgroup\$ – user168305 Apr 27 '18 at 11:53
1
\$\begingroup\$
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\$.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for this explanation! And I agree that generate_something was not the best way to name it. May I ask how you would do the same thing with a generator instead? \$\endgroup\$ – user168305 Apr 27 '18 at 11:55
  • \$\begingroup\$ @Matthieu: suppose that instead of 'a', 'b', 'c', 'd' your elements are 0, 1, 2, 3 and the Cartesian products are 00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33. Does that make it clear what I mean by counting to 16 and converting into base 4? \$\endgroup\$ – Peter Taylor Apr 27 '18 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy