Interview Question for SWE at Google:

You need to store and update a status vector to decide which permutation to generate next.

class Permutation
{
    int *orig;
    int *curr;
    int n;
    int *perm;
    int *temp;

public:
    Permutation(int *o, int s)
    {
        n = s;
        orig = new int[n];
        memcpy(orig, o, n * sizeof(int));
        curr = new int[n];
        memcpy(curr, o, n * sizeof(int));
        perm = new int [n];
        memset(perm, 0, sizeof(int) * n);
        temp = new int[n];
        memset(temp, 0, sizeof(int) *n);
    }

    int *GetCurr()
    {
        return curr;
    }

    bool GenNext()
    {
        int i;

        for (i = n-1; i >= 0; --i)
        {
            if (perm[i] != n - i)
            {
                ++perm[i];
                break;
            }
        }

        if (i < 0)
        {
            return false;
        }

        for (int i = 0; i < n; ++i)
        {
            int r = -1;
            for (j = 0; j < n &&; ++j)
            {
                if (temp[j] == 0)
                {
                    ++r;
                    if (r == perm[i])
                    {
                        curr[i] = orig[j];
                        temp[j] = 1;
                        break;
                    }
                }
            }
        }

        memset(temp, 0, sizeof(int) *n);

    }
}

It can also be done this way:
assuming string is ACEF.
A simple function to generate a unique digit for each character of the string. Assuming each character is unique in the string. Can also use Ascii. It will be of the order O(n).
say ACEF translates to 1234

Get the smallest number and the largest number
1234 and 4321.Can be done in liner amount of time if sorting algorithms like counting algo is used.

keep generating numbers between1234 and 4321 in which all the digits fall. Will involve incrementing numbers, mod (to find digits of the number) and binary search therefore running time of constant [to increment] + O(n)[to find digits] + O(nlogn) [to search it in the intial set of digits [1,2,3,4]]

Memory: Original as char array, used as fixed size boolean array

void PermPrint(char[] originals, boolean[] used, int processIndex, String previousString)
    {
        if(processIndex==originals.length)//done
        {
            System.out.println(previousString);
            return;
        }
        else
        {
            for(int i=0; i<originals.length;i++)
            {
                if(!used[i])
                {
                    used[i] = true;//firstly choose this unused char
                    PermPrint(originals, used, processIndex+1, previousString+originals[i]);
                    used[i] = false;//without choosing the char
                }
            }
        }
    }

1. Sort the array in lex order.

2. call the following function

public static void generatePermutation(String str /*sorted string*/) {
        char[] A = str.toCharArray();
        System.out.println(str);

        if (A.length == 0) {
            return;
        }

        /*Find the largest k, s.t. A[k] < A[k+1]*/
        while (true) {
            int i = A.length - 2, j = A.length - 1;
            while (i >= 0 && A[i] >= A[i + 1]) {
                i--;
            }

            if (i >= 0) {
                while (A[i] >= A[j]) {
                    j--;
                }
                char tmp1 = A[i];
                A[i] = A[j];
                A[j] = tmp1;

                /*reverse string from i+1 to A.length-1*/
                for (int k = i + 1, l = A.length - 1; k < l; k++, l--) {
                    char tmp2 = A[k];
                    A[k] = A[l];
                    A[l] = tmp2;

                }
                System.out.println(A);
            } else
                break;
        }

    }