问题24－给出集合｛0,1,2,3,4,5,6,7,8,9｝的全排列从小到大的第1000000个的值
问题描述如下：
“1，2，3的全排列是123 132 213 231 312 321，其全排列第3个的值为213，求｛0,1,2,3,4,5,6,7,8,9｝的全排列的第1000000个的值？”
?
我们可以知道｛0,1,2,3,4,5,6,7,8,9｝的全排列有10!个，如果要给出所有的全排列，那么昨天所说的Jhonson Trotter算法是比较高效的。在文章最后会给出其代码，有兴趣可以瞧瞧。
就本题而言，要确定每一位的值，从0开始的数有9!个，1...9开头的排列也一样，那第一个数就可以确定为999999/9!=2,第二个数就为（999999－999999/9!）/8!,由此类推，可以得到最终的数字，不说了，给代码：
?
/** * Johnson-trotter 算法 * * @param str * @return */public static String[] permutation(String str) {ArrayList<String> myList = new ArrayList<String>();char[] strChars = str.toCharArray();char temp;long times = 1;int pos = strChars.length - 2;int increment = -1;for (int i = 1; i < strChars.length + 1; i++) {times *= i;// (strChars.length + 1)!}for (int i = 1; i < times; i++) {temp = strChars[pos];strChars[pos] = strChars[pos + 1];strChars[pos + 1] = temp;myList.add(new String(strChars));pos += increment;if (pos == -1) {increment = 1;pos = 0;temp = strChars[strChars.length - 2];strChars[strChars.length - 2] = strChars[strChars.length - 1];strChars[strChars.length - 1] = temp;myList.add(new String(strChars));i++;} else if (pos == strChars.length - 1) {increment = -1;pos = strChars.length - 2;temp = strChars[0];strChars[0] = strChars[1];strChars[1] = temp;myList.add(new String(strChars));i++;}}return myList.toArray(new String[0]);}?到此结束。
?
请不吝赐教。
@anthor ClumsyBirdZ