CODEWITHSUNDEEP
algorithmpermutation
Sahithi
Sahithi

Reputation: 81

Print Permutations in lexographical order

To Print all Permutations of a string in lexicographical order

  1. Can I just find all the permutations of a string and then sort it ? This would be just the time complexity O(n!) ->for find permutations and then sort it it is O(nlogn) (if quick sort or merge is considered as sorting algorithm). O(n!)+O(nlogn) would be the complexity.

  2. Solution given in geeksforgeeks http://www.geeksforgeeks.org/lexicographic-permutations-of-string/ this says it as O(n*n!)

  3. I found another solution at https://www.educative.io/page/11000001/90001

Can someone explain which among them is the best to follow and what the time complexity is? Please explain

Upvotes: 3

Views: 678

Answers (1)

arewm
arewm

Reputation: 649

If you determine all of the permutations and then sort it, your time complexity is a little off. Say you have an n character long string. Based on a couple resources found from a quick search (complexity of recursive string permutation function, Time complexity of this code to list all permutations?), the time complexity for determining the permutations is Theta(n*n!)

This will generate n! different permutations. Now, to sort these permutations, it will take Theta(n! lg n!), for a total time complexity of:

Theta(n*n!) + Theta(n! lg n!)

You can remove the need to do that expensive sort at the end by constructing an algorithm that generates the permutations, preserving the sorted order.

I am imagining some recursive algorithm that takes each successive character as the initial character of the permutation and then determines the permutation of the rest of the string (which will be sorted as well).

Something like (sorry for the partially pseudo-code, partially Python):

def sorted_permute(str):
    if len(str) == 1:
        return [str]
    all_permutations = []
    for pos in len(str):
        next_str = str[:pos] + str[pos+1:]
        permutations = sorted_permute(next_str)
        permutations.prepend_to_all(str[pos])    # This could be expensive
        all_permutations.append(permutations)
    return all_permutations

***** EDIT *****

If you do not want to store the permutations and you really just care about printing the permutations, you can do something like the following:

def sorted_permute(str, head):
    if len(str) == 0:
        print(head)
    for pos in len(str):
        next_str = str[:pos] + str[pos+1:]
        new_head = head + str[pos]
        sorted_permute(next_str, new_head)

Upvotes: 3

Related Questions