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.

Thanks!

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.

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.

Thanks!

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.

Thanks!