Print Permutations in lexographical order

Question

To Print all Permutations of a string in lexicographical order

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.
Solution given in geeksforgeeks http://www.geeksforgeeks.org/lexicographic-permutations-of-string/ this says it as O(n*n!)
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

Brute force should be O(n!), unless you can somehow modify the permutation-generating algorithm to reject non sorted stings along the way without doing additional work. — Tim Biegeleisen
Is Brute force is the one ,that is generate permutations and sort it ? — Sahithi
You cannot reject any strings. Each individual string is not sorted, but all permutations of the string are sorted before printing. — arewm
Why sort all the permutations? You can sort the input string and then generate the permutations, if done correctly they will automatically be in lexicographical order. — maraca

arewm arewm · Accepted Answer · 2016-07-08T01:19:33

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)

Print Permutations in lexographical order

1 Answers