问题描述如下:
“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!,由此类推,可以得到最终的数字,不说了,给代码:
/**
* 给出集合{0,1,2,3,4,5,6,7,8,9}的全排列从小到大的第1000000个的值
*
* @return
*/
public static String getNumber() {
int[] factorial = { 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
// 1!,2!,...,9!
String s = "0123456789";
int limit = 999999;
String result = "";
for (int i = factorial.length - 1; i >= 0; i--) {
// 取剩下字符串的第几位
int num = limit / factorial[i];
result += s.charAt(num);
limit = limit - num * factorial[i];
// 把确定的数从字符串中移取
s = remainNumber(s, num);
}
return result + s;
}
// 确定一位后,剩下的数
private static String remainNumber(String s, int index) {
return s.substring(0, index) + s.substring(index + 1);
}
下面给出的是Jhonson Trotter算法的java实现(从网上直接找的),如果不明白可以直接问我:
/**
* 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
分享到:
相关推荐
集X中元素的全排列记为Perm(X),(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳定义如下: 当n=1时,Perm(R)={r},r是集合R中唯一的元素. 当n>1时,Perm(R)由(r1)Perm(R1),(r2)...
剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中
剑指 Offer II 084. 含有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个可包含重复数字的序列 nums 。解题思路这道题跟「剑指 O
本篇文章介绍了,集合的子集与集合的全排列的相关系列问题说明,需要的朋友参考下
设R={r1,r2,…,rn}是要进行排列的n个元素,R的全排列记为perm(R),Ri=R-{ri},(ri)perm(Ri)表示集合Ri的全排列中每个排列前增加一个前缀所形成的所有排列。于是 当n=1时,perm(R)=(r),其中r是R中的唯一元素; 当n...
比如:集合{ 1,2,3}的全排列为: 代码如下: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 我们可以将这个排列问题画成图形表示,即排列枚举树,比如下图为{1,2,3}的排列枚举树,此树和我们这里...
剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中
计算重复元素的全排列。以文本文件的形式存储和输入输出。
从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典序排列 把升序的排列(当然,也可以实现为降序)作为当前排列开始,然后依次...
Matlab实现n个元素的全排列设集合R={r1, r2, …, rn}是要进行全排列的n个元素,Ri = R – {ri}。集合R中元素的全排列记为perm(R),(ri)perm(R)表示在全排列perm(R)的每一个排列前加上前缀ri得到的排列。R的...
Description 设集合R={r1,r2,...,rn}是要进行排列的n个元素,其中r1,r2,...,rn可能相同。 试着设计一个算法,列出R的所有不同排列。 即,给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。 ...
比如:集合{ 1,2,3}的全排列为: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 递归思想: 取出数组中第一个元素放到最后,即a[1]与a[n]交换,然后递归求a[n-1]的全排列 1)如果数组只有一个元素n...
集合X中元素的全排列记为perm(X); 设(ri)perm(X)表示每一个全排列前加上前缀 ri得到的排列. 当n=1时,perm(R)=(r) 其中r是唯一的元素,这个就是出口条件. 当n>1时,perm(R)由 (r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn...
问题 输入一个字符串,打印出该字符...如果能生成n-1个元素的全排列,就能生成n个元素的全排列。对于只有一个元素的集合,可以直接生成全排列。所以全排列的递归终止条件很明确,只有一个元素时。我们可以分析一下全排
由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。 # 解决思路 由于NPC问题至今没有得到解决,TSP问题往往是通过启发式搜索(我觉得也可以叫暴力)算法来“猜”出最...
对于集合[1, 2, 3],如果让我们在纸上写的话,很容易可以写出来[1, 2, 3],[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1,
全排列在很多程序都有...种不同的排列,如果给定集合是{a,b,c,d},可以用下面给出的简单算法产生其所有排列,即集合(a,b,c,d)的所有排列有下面的排列组成:(1)以a开头后面跟着(b,c,d)的排列(2)以b开头后面跟着(a
| 稳定婚姻问题 O(N^2) 7 | 拓扑排序 8 | 无向图连通分支(DFS/BFS 邻接阵) 8 | 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) 8 | 有向图最小点基(邻接阵)O(N^2) 9 | FLOYD 求最小环 9 | 2-SAT 问题 9 Network ...
本程序中包扩: (1)集合的交并运算 (2)栈的应用之元素的输出 (3)图的应用之最短路径 (4)链式存储学生信息 (5)二叉树之赫夫曼树编码 (6)全排列问题
子集合问题子集合是全排列的好朋友,也是combination组合的好朋友,排列·组合·子集,他们三个都是好朋友.从空开始加同样先来看'ABC'市面流行思路市面上