`
zhou_zhihao
  • 浏览: 55469 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

问题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!,由此类推,可以得到最终的数字,不说了,给代码:

 

/**
	 * 给出集合{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

分享到:
评论

相关推荐

    全排列算法 perm

    集X中元素的全排列记为Perm(X),(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳定义如下: 当n=1时,Perm(R)={r},r是集合R中唯一的元素. 当n&gt;1时,Perm(R)由(r1)Perm(R1),(r2)...

    Rogerspy#LeetCode-Py-1#剑指 Offer II 083. 没有重复元素集合的全排列1

    剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中

    finesure2017#LeetCode-Py-1#剑指 Offer II 084. 含有重复元素集合的全排列 1

    剑指 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...

    C#算法之全排列递归算法实例讲解

    比如:集合{ 1,2,3}的全排列为: 代码如下: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 我们可以将这个排列问题画成图形表示,即排列枚举树,比如下图为{1,2,3}的排列枚举树,此树和我们这里...

    tesla-peer#LeetCode-Python-#剑指 Offer II 083. 没有重复元素集合的全排列1

    剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中

    重复元素全排列

    计算重复元素的全排列。以文本文件的形式存储和输入输出。

    全排列——递归排序和字典序列

    从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典序排列 把升序的排列(当然,也可以实现为降序)作为当前排列开始,然后依次...

    Matlab实现全排列.doc

    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个元素的所有不同排列。 ...

    python递归全排列实现方法

    比如:集合{ 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&gt;1时,perm(R)由 (r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn...

    使用C语言解决字符串全排列问题

    问题 输入一个字符串,打印出该字符...如果能生成n-1个元素的全排列,就能生成n个元素的全排列。对于只有一个元素的集合,可以直接生成全排列。所以全排列的递归终止条件很明确,只有一个元素时。我们可以分析一下全排

    基于C++实现的改进版遗传算法解决TSP问题源码+项目说明.zip

    由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。 # 解决思路 由于NPC问题至今没有得到解决,TSP问题往往是通过启发式搜索(我觉得也可以叫暴力)算法来“猜”出最...

    stronglxp#learnNote#46.全排列1

    对于集合[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)全排列问题

    wangtechservices#Interview_apachecn#子集合问题1

    子集合问题子集合是全排列的好朋友,也是combination组合的好朋友,排列·组合·子集,他们三个都是好朋友.从空开始加同样先来看'ABC'市面流行思路市面上

Global site tag (gtag.js) - Google Analytics