public class NextPermutation {
	public String getPermutation(int n, int k){
		List<Integer> remains = new ArrayList<>();
		int[] fact = new int[n+1];
		fact[0] = 1;
		for(int i = 1; i <= n; i++){
			fact[i] = fact[i-1] * i;
			remains.add(i);
		}

		k--;

		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= n; i++){
			int index = k / fact[n - i];
			sb.append(remains.remove(index));
			k -= index * fact[n-i];
		}

		if(sb.isEmpty()){
			return "0";
		}
		return sb.toString();
	}

	public void nextPermutation(int[] nums){
        if(nums == null || nums.length <= 1) return;				
		int length = nums.length, last = nums[length-1], index = -1;
		for(int i = length - 2; i >= 0; i--){
			if(nums[i] < last){
				index = i; 
				break;
			}
			last = nums[i];
		}

		if(index < 0){
			reverse(nums, 0, length - 1);
			return;
		}

		for(int i = length - 1; i > index; i--){
			if(nums[index] < nums[i]){
				swap(nums, index, i);
				break;
			}
		}

		reverse(nums, ++index, length - 1);
	}

	private void reverse(int[] nums, int low, int high){
		while(low < high){
			swap(nums, low++, high--);
		}
	}

	private void swap(int[] nums, int a, int b){
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;
	}
}
@@ -1219,10 +1219,512 @@
  tmp;%0A%09%7D
+%0A%0A%09// can given s permute and become a palindrome?%0A%09public boolean palindromePermutation(String s)%7B%0A%09%09int%5B%5D counts = new int%5B256%5D;%0A%09%09int odd = 0;%0A%09%09for(char c : s.toCharArray())%7B%0A%09%09%09odd += ++counts%5Bc%5D %25 2 == 1 ? 1 : -1;%0A%09%09%7D%0A%0A%09%09return odd %3C= 1;%0A%09%7D%0A%0A%09// return all s permutation (without dup) that is palindrome%0A%09public List%3CString%3E allPalindromePermutation(String s)%7B%0A%09%09List%3CString%3E result = new ArrayList%3C%3E();%0A%09%09if(s == null %7C%7C s.isEmpty() %7C%7C !palindromePermutation(s)) return result;%0A%09%09%0A%09%09permute()%0A%09%7D
 %0A%7D

palindrome permutation