Generating Permutations in Lexicographic Order vs Sorting?

Question

I'm a little bit confused. How is the problem of generating permutations in Lexicographic Order any different from the problem of sorting? Can someone please explain it to me with an example? Thanks

Answer 1

These are two different things. There are N! permutations, but there is only one sorted order (the sorted permutation is the smallest lexicographically).

Here is an example of a sorted permutation:

brown fox quick

Here is a list of permutations in lexicographic order:

brown fox quick
brown quick fox
fox brown quick
fox quick brown
quick brown fox
quick fox brown

Here is a program in C++ to generate permutations in lexicographic order:

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
    vector<string> s;
    s.push_back("quick");
    s.push_back("brown");
    s.push_back("fox");
    sort(s.begin(), s.end());
    do {
        for(int i = 0 ; i != s.size() ; i++) {
            cout << s[i] << " ";
        }
        cout << endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

Answer 2

Permutations are not addressed in the problem of sorting.

One way that they could relate is if you generate Permutations that are not in lexicographic order then you sort to get it in lexicographical order. This however would require to have factorial space. Generation usually spits out one element at a time therefore not having to have all elements in memory.

Answer 3

There's a fairly easy way to generate the nth permutation in lexicographic order. The set of choices you make in selecting the permutation elements are: pick 1 of N, then 1 of N-1, then 1 of N-2, ... then 1 of 2, and finally there's just one left. Those choices, as index values into a running "what's left" list, can be looked at as a variable-base number.

You can develop the digits from right to left as d[1] = n%2, d[2] = (n/2)%3, d[3] = (n/6)%4, ... d[k] = (n/k!) % (k+1). The result has d[N-1]==0 for the first (N-1)! permutations, d[N-1]==1 for the next (N-1)!, and so on. You can see that these index values will be in lex. order. Then choose the symbols out of your sorted set (Any random-access collection will do if syms[0], syms[1], ... are in the order you want.)

Here's some code I whipped up for working on Project Euler problems. It just generates the index values, and allows for choosing permutations of k symbols out of n. The header file defaults k to -1, and the argument check code converts this to n and generates full length permutations. There's also a change of notation here: "index" is the number of the permutation ("n" above) and "n" is the set size ("N" above).

vector<int> pe_permutation::getperm(long long index, int n, int k)
{

if (n<0) throw invalid_argument("permutation order (n)");
if (k<0 || k>n) 
{
    if (k==-1) 
        k=n;
    else throw invalid_argument("permutation size (k)");
}
vector<int> sset(n, 0); // generate initial selection set {0..n-1}
for (int i=1; i<n; ++i)
    sset[i] = i;

//  Initialize result to sset index values.  These are "without replacement"
//  index values into a vector that decreases in size as each result value
//  is chosen.  

vector<int> result(k,0);
long long r = index;
for (int m=n-k+1; m<=n; ++m)
{
    result[n-m] = (int)(r % m);
    r = (r / m);
}

// Choose values from selection set:

for (int i=0; i<k; ++i)
{
    int j = result[i];
    result[i] = sset[j];
    sset.erase(sset.begin()+j);
}
return result;

} // getperm(long long, int, int)

Answer 4

import java.util.*;
public class Un{

    public static void main(String args[]){
        int[]x={1,2,3,4};

        int b=0;int k=3;
        while(b!=(1*2*3*4)){

            int count=0;
            while(count!=6){
                for(int i=2;i>0;i--){
                    int temp=x[i];
                    x[i]=x[3];
                    x[3]=temp;
                    count++;
                    System.out.println(x[0]+""+x[1]+""+x[2]+""+x[3]);
                 }

            } 
            b+=count;
            int temp=x[0];
            x[0]=x[k];
            x[k]=temp;
            k--;
       }            
 }


}