Java/PermutationSequence.java at master · rjtsdl/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

public class PermutationSequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	public String getPermutation(int n, int k) {

		int[] arr = new int[n];
		int seq = 1;
		for(int i=0; i<n; i++)
		{
			arr[i] = i+1;
		}

		while(seq<k)
		{
			int j= n-1;
			while(j-1>=0 && arr[j]<arr[j-1])
			{
				j--;
			}

			if(j==0)
			{
				int i =0;
				int p = n-1;
				while(i<p)
				{
					int temp = arr[i];
					arr[i] = arr[p];
					arr[p] = temp;
					i++;
					p--;
				}
			}
			else
			{
				int i= j-1;

				while(j+1<n && arr[j+1] > arr[i])
				{
					j++;
				}

				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;

				i++;
				int p = n-1;
				while(i<p)
				{
					temp = arr[i];
					arr[i] = arr[p];
					arr[p] = temp;
					i++;
					p--;
				}
			}

			seq ++;

		}

		String ret = "";
		for(int i=0; i<n; i++)
		{
			ret += arr[i];
		}
		return ret;

    }

}