Lexicographic permutation of Number/String

A Util class for Lexicographically sorted permutations of number/string. Get N-th element of the result or next element for a given element without calculating all the permutations.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the smallest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies condition k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

package permute;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LexicographicPermutation {

	public static boolean nextPermutation(int[] p) {

		int a = p.length - 2;
        while (a >= 0 && p[a] >= p[a + 1]) {
        	a--;
        }
        if (a == -1) {
            return false;
        }
        int b = p.length - 1;
        while (p[b] <= p[a]) {
        	b--;
        }

        int t = p[a];
        p[a] = p[b];
        p[b] = t;
        for (int i = a + 1, j = p.length - 1; i < j; i++, j--) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
        }
        return true;
    }

	private static int factorial(int i){
		if (i <= 1) {
	        return 1;
	    }

	    int p = 1;
	    for (int j = 1; j <= i; j++) {
	        p *= j;
	    }
	    return p;
	}

	public static String nThPermutation(List<String> in, int index){

		if(in.size()==1)
			return in.get(0);

		int N = in.size();		
		int residue = index;
		int noOfPerm = factorial(N-1);
		int outputIndex = 0;

		if(noOfPerm<residue){
			outputIndex = residue/noOfPerm;
			if(residue%noOfPerm==0){
				outputIndex--;
			}
			residue = residue -(outputIndex * noOfPerm);			
		}
		String indexDigit = in.get(outputIndex);
		in.remove(outputIndex);
		return indexDigit + nThPermutation(in, residue);
	}

	public static void main(String[] args) {

		String[] in1={"a","b","c"};
		List<String> inp =  new ArrayList<String>(Arrays.asList(in1));
		System.out.println("Nth permutation elem:\n"+nThPermutation(inp,5));
		System.out.println("\n--------------------------");

		int[] in2 = {2,4,7,9,3,1};
		nextPermutation(in2);
		System.out.println("next permutation element:");
		for(int ch:in2)
			System.out.print(ch);
		System.out.println("\n--------------------------");

		/** Generate all permutations in lex order **/
		while(nextPermutation(in2)){
			System.out.println();

			for(int ch:in2)
				System.out.print(ch);
		}
	}

}