Coded up a DP algorithm in python for computing all the permuations of the characters in a string. I know it’s not very space efficient but it can be made so because we only ever need the previous level of permutations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

input_str = input()

T = [[list() for _ in input_str] for __ in input_str]

for end_offset in range(len(input_str)+1):
    for start_index in range(len(input_str)):
        end_index = start_index + end_offset
        if end_index >= len(input_str):
            break
        if start_index == end_index:
            T[start_index][end_index].append(input_str[start_index])
        else:
            T[start_index][end_index] = list()
            sub_permutations = T[start_index+1][end_index]
            new_element = input_str[start_index]
            for sub_permutation in sub_permutations:
                for insert_index in range(len(sub_permutation) + 1):
                    sub_permutation_list = list(sub_permutation)
                    sub_permutation_list.insert(insert_index, new_element)
                    new_permutation = ''.join(sub_permutation_list)
                    T[start_index][end_index].append(new_permutation)

# Now print the permutations which are at T[0][len(input_str)-1]
for permutation in T[0][len(input_str)-1]:
    print(permutation)