CareerCup

can u explain last line elaborately..

Question Still not clear. Can u give the expected output?

I think, it means the following:
If we generate all the permutations of a given array and store these permutations in another array say PermuatedArray. Now we sort this PermuatedArray. The Answer to the question will be, PermuatedArray[k] in the sorted version of PermuatedArray.

Hope this makes it clear enough.

static public int[] FindKthPermutation(int[] input, int k)
{
if (k < 0 || factorial(input.Length) <= k)
throw new Exception("K invalid range");

Array.Sort(input);

bool[] used = new bool[input.Length];
for (int i = 0; i < used.Length; i++)
used[i] = false;

int[] output = new int[input.Length];


int outIdx=0;
for (int i = input.Length-1; i >0; i--)
{
int fact = factorial(i);
int pos = (int)(k / (double)fact);

int j = 0;
while (used[j])
j++;

int skipped=0;
// make an array of unused
while (skipped<pos)
{
if (!used[j])
skipped++;
j++;
}
output[outIdx++] = input[j];
used[j] = true;

Console.WriteLine("i:{0}, fact:{1}, k:{2}, pos:{3}, j:{4}", i, fact, k, pos,j);

k = k % fact;
}

// find the last unused digit
int x= 0;
while (x < input.Length)
{
if (!used[x])
break;
x++;
}

output[outIdx++] = input[x];
return output;
}

The basic algorithm of the above code is this:
sort the input array in ascending order
at each digit position i, find the next digit location using the possible range for a given k.

So, we don't need sorting here. Just pick the right index in every iteration.

get k th value.. store the value at kth place and store the number k..
on the remaining items.. do the regular permutation.
when even u are printing the output.. insert kth value at kth position and output it..

@smp for k=8 it is giving 2213 as output.

assume the set as 1,2,3,4 and rank is 8