Big O time calculation for given string permutations

Question

def get_permutations(s):
    if(len(s) == 0):
        print("No string given.")
        return None
    
    if(len(s) > 2):
        permutations = get_permutations(s[:-1])
    
    last_letter = s[-1]

    #Creates a list 'permutations' for first two letters of string
    #like for s = 'abcd', permutations = ['ab', 'ba']
    if(len(s) == 2):
        permutations = []
        j = 0
        while j < len(s):
            perms = s[0:j] + last_letter + s[j:-1]
            permutations.append(perms)
            j += 1

    #Creates permutations by putting last letter of the string in all
    #possible positions of the string
    else:
        current_permutations_len = len(permutations)

        for elem in permutations[:current_permutations_len]:
            k = 0
            while k <= len(elem):
                perms = elem[0:k] + last_letter + elem[k:]
                permutations.append(perms)
                k += 1

        # Removes the permutations that came from previous recursion
        # and only saves the newly generated permutations
        permutations = permutations[current_permutations_len:]

    return permutations



s = 'abcd'    
permutations = get_permutations(s)

if(len(s) > 0): # To avoid traceback if len(permutations) == 0
    print("Total permutations: ", len(permutations))

print(permutations)

I can't callculate the Big O time of this code. The idea is: We generate all permutations of a string s(1) • • • s(n) by "chopping off" the last character and generating all permutations of s(1) • • • s(n-1). Once we have the list of all permutations of s(1) • • • s(n-1), we iterate through this list. For each string in it, we insert s(n) into every location of the string.

Here is a little presentation:

Case "ab" - -> {"ab", "ba"}

P("abc") insert "c" into all locations of all strings in {"ab","ba"}

P("abc") merge({"cab", ""acb", "abc"}, {"cba", abca", bac"})

P("abc") {"cab", "acb", "abc", "cba", "bca", bac"}

If possible, can someone suggest some improvements to reduce Big O time for this

Boze Boze · Accepted Answer · 2020-07-16T16:28:52

The time complexity for this algorithm is O(n!) because we iterate through the word and find all possible amounts of permutations per iteration.
So, if we had the word, we see that word[0] ("a") only has one permutation, word1 has a permutations of len(word1) * permutations(word[0]). permutation[word[2]) = len(word[2]) * permutations(word1), and we keep doing this until we have permutations of word[n].
This is actually a leetcode question that can be found here. You can see many ways the permutation problem has been solved and see many efficient ways of doing so.

Big O time calculation for given string permutations

1 Answers