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, Jul 08 '16 at 00:56
Is Brute force is the one ,that is generate permutations and sort it ? — Sahithi, Jul 08 '16 at 01:04
You cannot reject any strings. Each individual string is not sorted, but all permutations of the string are sorted before printing. — arewm, Jul 08 '16 at 01:07
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, Jul 08 '16 at 01:20

score 3 · Accepted Answer · edited May 23 '17 at 10:34

3

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)

edited May 23 '17 at 10:34

Community

1
1

answered Jul 08 '16 at 01:19

arewm

649
3
12

Thanks for the explanation guys ...It really helped me :) – Sahithi Jul 08 '16 at 01:27
@user3519495 No problem. I added a little pseudocode for an algorithm if it would help. – arewm Jul 08 '16 at 01:32
`for (i=0; i – maraca Jul 08 '16 at 01:32
There's really no need to store the permutations, OP wants to print them. Also, the complexity has a tighter bound `O(e.n!)`, I think ... – Kedar Mhaswade Jul 08 '16 at 03:46
So if i sort the string first and then generate the permutations ...What could be the time complexity . Sorting :O(nlogn) + Permutations:O(n*n!)...So overall complexity would be O(n!)..Please correct me if am wrong – Sahithi Jul 08 '16 at 05:23
@KedarMhaswade For this implementation, you have to store the permutations so that you can pass them back up the stack. If you do not want to store them, you can instead pass them down the stack as a parameter to the function. – arewm Jul 08 '16 at 12:56
@user3519495 The time complexity would be the sorting plus the permutations, correct. I believe that the permutations are O(n*n!), but this cannot be simplified to O(n!). The time complexity would be O(n*n!). – arewm Jul 08 '16 at 12:58

Print Permutations in lexographical order

1 Answers1