`

对一组数排列,包含相同元素

    博客分类:
  • java
阅读更多

题目:{3,2,2,6,7,8}排序输出,7不在第二位,68不在一起。

 

 

分析思考:

 

1.编写输出全部元素的排序组合,6位数共有6!个排序方式,即720个

 

2.由于有两个2,即重复元素,则最终将会有重复的排序方式,输出的个数720/2! = 360个,再去掉与7和68的限制相关的组合

 

 

全部元素排序

第一个位置有6种情况,取一个数放在第一位上,则第二位剩下5个元素,依次递归到最后一个元素,则得出一个排列组合。

按此方法,将全部排列输出

/**
	 * 分组排序
	 * @param source
	 */
	public static void group(int source[]) {
		for (int i = 0; i < source.length; i++) {

			int[] target = new int[source.length];

			// 第一个数有source.length种情况
			int first = source[i];

			int sourceStart = 0;
			target[sourceStart] = first;

			//通过下标移除已经选择的元素
			int[] leaveCollection = removeSelectIndex(i, source);
			groupNext(leaveCollection, sourceStart + 1, target,source.length);
		}
	}
	
	/**
	 * 通过下标移除已经选择的元素
	 * @param index
	 * @param source
	 * @return
	 */
	static int[] removeSelectIndex(int index , int[] source){
		int [] leaveCollection = new int[source.length -1];
		int leaveIndex = 0;
		for(int i = 0 ;i < source.length ;i++){
			if(index != i){
				leaveCollection[leaveIndex++] = source[i];
			}
		}
		return leaveCollection;
	}
	
	/**
	 * 第二个数有剩余source.length-1 种情况,第三个数从剩余中取,source.length-2种情况
	 * 
	 * @param source
	 * @param sourceStart
	 * @param target
	 */
	static void groupNext(int[] nextCollection, int sourceStart, int[] target,int sourceLength) {
		for (int l = 0; l < nextCollection.length; l++) {
			int second = nextCollection[l];

			target[sourceStart] = second;

			if (sourceStart + 1 < sourceLength) {
				// 递归下一位
				int[] copyOf = Arrays.copyOf(target, target.length);
				
				int[] source = removeSelectIndex(l, nextCollection);
				groupNext(source, sourceStart + 1, copyOf,sourceLength);
			} else {
				// 循环结束,输出结果
				println(target);
			}
		}
	}

 

由于有重复元素,在取剩下需要排序的集合时,不能用值去集合中删除,如在{22678}中删除2的元素,则剩下{678},通过下标移除是最好的方法。

 

 

删除不符合题意的组合

1.println(target)中,自行将7和68的限制去掉

 

2.由于有22存在,则在720个排列当中,有一半是重复的。需要把这些数据删除。最简单的做法通过Map,往Map中put进相同的元素,达到去重效果。

	static void println(int target[]) {
		StringBuffer bf = new StringBuffer();
		for (int i : target) {
			bf.append(i);
		}

		String value = bf.toString();
		
		if (value.indexOf("7") == 1)// except 7 in second position
			return;

		if (value.indexOf("68") != -1 || value.indexOf("86") != -1)// except adjoining
			return;

		rs.put(value, value);
	}

 

 

算法分析

 

解法二:

这种排序做法很早就看到过,通过将元素拼成两个数,再依次递增。判断输出结果:

 

public static void sort(String[] args) {
		// {3,2,2,6,7,8},其中7不能放在第二个位置,6和8不能相邻,打印所有的排列

		List<String> list = new ArrayList<String>();
		for (int i = 223678; i <= 876322; i++)
			list.add(i + "");

		int size = 0;// all size

		for (String s : list) {
			if (s.indexOf("0") != -1 || s.indexOf("1") != -1
					|| s.indexOf("4") != -1 || s.indexOf("5") != -1
					|| s.indexOf("9") != -1)// except 0,1,4,5,9
				continue;

			if (s.indexOf("2") == -1 || s.indexOf("3") == -1
					|| s.indexOf("6") == -1 || s.indexOf("7") == -1
					|| s.indexOf("8") == -1
					|| s.indexOf("2", s.indexOf("2") + 1) == -1)// contain all
				// 3,2,2,6,7,8
				continue;

			if (s.indexOf("7") == 1)// except 7 in second position
				continue;

			if (s.indexOf("68") != -1 || s.indexOf("86") != -1)// except
				// adjoining 6,8
				continue;
			size++;

			 System.out.println(s);
		}

		// System.out.println("All size --> " + size);// All size --> 198
	}

 

结果出来也是正确的。

 

但此算法循环的次数是876322-223678次=600000次,并且每次大约有10次的字符串indexOf操作,最终耗时500ms左右

 

而排序组合解法中,总共循环的次数为720次,耗时在15-50ms之间。

 

 

 

 

 

分享到:
评论
3 楼 yangkai 2010-02-02  
yangkai 写道
您好,对于你的排列组合,我个人认为有点复杂!
这里我有一个简单高效的算法:(如有问题请指正)

package com.ibm.common.arithmetic;

public class TraceBackSort {
	public static void main(String[] args) {
		TraceBackSort tc = new TraceBackSort();
		
                char a[] = {'3','2','2','6','7','8'};
		long start = System.currentTimeMillis();
		tc.perm(a, 0);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

	private void _swap(char[] a, int i, int j) {
		char temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void perm(char[] a, int node) {
		int len = a.length;
		if (node == len) {
			String nodeStr = String.valueOf(a);
			if (nodeStr.charAt(1) != '7'
					&& !(nodeStr.matches("^\\d[68][86]\\d*$"))) {
				System.out.println(nodeStr);
			}
		} else {
			for (int i = node; i < len; i++) {
				_swap(a, node, i);
				perm(a, node + 1);
				_swap(a, node, i);
			}
		}
	}
}


2 楼 yangkai 2010-02-02  
您好,对于你的排列组合,我个人认为有点复杂!
这里我有一个简单高效的算法:(如有问题请指正)

package com.ibm.common.arithmetic;

public class TraceBackSort {
	public static void main(String[] args) {
		TraceBackSort tc = new TraceBackSort();
		
                char a[] = {'3','2','2','6','7','8'};
		long start = System.currentTimeMillis();
		tc.perm(a, 0);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

	private void _swap(char[] a, int i, int j) {
		char temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void perm(char[] a, int node) {
		int len = a.length;
		if (node == len) {
			String nodeStr = String.valueOf(a);
			if (nodeStr.charAt(1) != '7'
					&& !(nodeStr.matches("^\\d[68][86]\\d*$"))) {
				System.out.println(nodeStr);
			}
		} else {
			for (int i = node; i < len; i++) {
				_swap(a, node, i);
				perm(a, node + 1);
				_swap(a, node, i);
			}
		}
	}
}

1 楼 yongyuan.jiang 2009-10-16  
一个同事给出另外一种思路。
5位先排序,再将重复的元素插入。

其实5位120次,再插入1位,结果依然是720次。

不过递归6位是否与5位有性能差别。还没去验证。

最终跑出来结果一样。

HashMap改由HashSet,虽然jdk HashSet源码是用HashMap事先的。但是结果却发现Set更加快。

package jyy.suanfa.zuhe;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Sort {

	public static void main(String[] args) {
		long l = 0;

		int time = 100;
		for (int i = 0; i < time; i++) {
			l += main1(null);
		}
		System.out.println("平均时间:"+l / time);
	}

	public static StringBuffer[] group(int[] source) {
		int length = 1;
		int count = 0;
		for (int i = 2; i <= source.length; i++) {
			length = length * i;
		}
		StringBuffer[] sbs = new StringBuffer[length];
		if (source.length <= 1) {
			sbs[count++] = new StringBuffer(String.valueOf(source[0]));
			return sbs;
		} else {
			for (int i = 0; i < source.length; i++) {
				int[] s = new int[source.length - 1];
				for (int j = 0; j < i; j++) {
					s[j] = source[j];
				}
				for (int j = i + 1; j < source.length; j++) {
					s[j - 1] = source[j];
				}
				StringBuffer[] reslut = group(s);
				for (int j = 0; j < reslut.length; j++) {
					StringBuffer sb = new StringBuffer(String
							.valueOf(source[i]));
					sb.append(reslut[j]);
					sbs[count++] = sb;
				}
			}
		}
		return sbs;
	}

	public static long main1(String[] args) {
		long first = System.nanoTime();
		int[] source = { 3, 2, 6, 7, 8 };
		StringBuffer[] group = group(source);
		Set<String> set = insert(group);

		long end = System.nanoTime();
		System.out.println("耗时:" + (end - first) + " nanoTime");
		return (end - first);
	}

	public static Set<String> insert(StringBuffer[] source) {
		Set<String> set = new HashSet<String>();
		for (int i = 0; i < source.length; i++) {
			StringBuffer sb = source[i];
			if (sb.indexOf("68") < 0 && sb.indexOf("86") < 0) {
				if (sb.charAt(0) == '7') {
					for (int j = 1; j <= sb.length(); j++) {
						StringBuffer temp = new StringBuffer(sb);
						set.add(temp.insert(j, '2').toString());
					}
				} else if (sb.charAt(1) == '7') {
					StringBuffer temp = new StringBuffer(sb);
					set.add(temp.insert(0, '2').toString());
					temp = new StringBuffer(sb);
					set.add(temp.insert(1, '2').toString());
				} else {
					for (int j = 0; j <= sb.length(); j++) {
						StringBuffer temp = new StringBuffer(sb);
						set.add(temp.insert(j, '2').toString());
					}
				}
			} else {
				int offset = sb.indexOf("68");
				if (offset < 0) {
					offset = sb.indexOf("86");
				}
				StringBuffer temp = new StringBuffer(sb);
				StringBuffer s = temp.insert(offset + 1, '2');
				if (sb.charAt(1) == '7') {
					continue;
				}
				set.add(s.toString());
			}
		}
		return set;
	}
}

相关推荐

    高中数学选修排列与组合排列与排列数PPT课件.pptx

    两个排列相同,当且仅当两个排列的元素按照一定的顺序排成一列完全相同排列顺序。 二、 排列数公式 排列数公式为n(n-1)(n-2)…[n-(m-1)],也可以写成n!/(n-m)!。在应用排列数公式时,需要注意排列数之间的关系,两...

    58巧解相同元素的排列问题[归类].pdf

    在排列组合问题中,处理相同元素的排列是一个挑战性较高的课题。在常规的高中数学教育中,主要关注的是不同元素的排列,而相同元素的排列则更多地出现在数学竞赛和部分高考模拟试题中。教师在教学中往往缺乏系统性的...

    Permutation with Repetition R={ r1,r2,… ,rn }是要进行排列的n 个元素。其中元素r1,r2,… ,rn可能相同。试设计一个算法,列出R的所有不同排列。

    具体来说,给定一个包含`n`个元素的集合`R={r1,r2,… ,rn}`,其中元素之间可能存在重复。目标是找出这个集合的所有不同的排列组合。 #### 输入格式 输入数据由多组测试数据组成。对于每组测试数据: - 第一行是一...

    vb写的排列组合相关小程序

    描述中提到的“实现从n个数中列举出那几个相加能够得到指定结果的所有情况”,这表明该程序的核心功能是解决一个经典的组合问题,即找出一组数字的所有可能组合,使得这些数字相加的结果等于一个特定的目标值。...

    8594有重复元素的排列问题

    题目要求实现一个程序来计算并输出给定字符序列中所有不同的排列情况,其中可能包含重复的元素。 #### 代码解析 首先,我们来看一下提供的代码实现: ```cpp #include int sum = 0; using namespace std; ...

    有重复元素的排列问题

    排列是将一组对象(在这里可能是数字或字符)按照特定顺序排列的所有可能方式。当这组对象中存在重复元素时,排列的数量会比没有重复元素的情况少,因为相同的元素在不同位置可以构成相同的排列。 对于这个问题,...

    8594 有重复元素的排列问题

    描述进一步解释了这个问题,指出需要处理的集合R包含n个可能相同的元素,并且要求列出所有可能的排列组合。 标签“重复元素”和“排列问题”强调了算法的核心难点在于处理重复值的情况,因为通常没有重复元素的排列...

    疯狂排列组合

    《疯狂排列组合》是一款专注于排列组合计算的软件,旨在帮助用户高效地理解和计算各种排列组合问题。在数学领域,排列组合是概率论、统计学和计算机科学中的基础概念,广泛应用于数据分析、算法设计以及问题求解等多...

    排列组合的算法作业 java

    首先,让我们看第一个题目,它涉及到有相同元素的排列。代码中定义了一个名为`Sort`的类,它包含了初始化、输入、交换、回溯和打印的方法。`init`方法用于设置初始参数,`scan`用于读取输入的元素,`swap`用于交换...

    排列组合公式排列组合计算公式.doc

    组合公式也可以通过排列公式推导得出,因为排列包含了顺序,所以组合数等于排列数除以m个元素的排列数,即m!。 排列组合在许多领域都有应用,比如计算机科学中的算法设计(如排序算法)、密码学(密码的组合可能性...

    排列组合demo

    9crimes这个文件名可能是这个项目中的一个示例或者测试用例,可能包含了一组特定的数据,用于检验排列组合算法的正确性。通常,测试用例会包括各种边界条件,如空集、只有一个元素的集合、所有元素都相同的集合等,...

    新建文本文档_排列组合_源码

    在给定的“新建文本文档_排列组合_源码”主题中,问题的核心是利用排列组合原理来确定由数字1、2、3、4可以组成多少个互不相同且无重复数字的三位数。 首先,我们要理解排列和组合的概念: 1. 排列:指的是从n个...

    华农8594有重复元素的排列问题

    它涉及到如何从一组元素中选取部分或全部元素进行重新排序的问题。当这组元素中存在重复元素时,问题的复杂度会进一步增加,因为需要避免生成相同的排列结果。 本篇讨论的“华农8594有重复元素的排列问题”,主要...

    高中数学讲义微专题80 排列组合中的常见模型.pdf

    “不同元素分组”和“相同元素分组”涉及将元素放入不同盒子或相同盒子的情况,其中“相同元素分组”由于元素相同,常用“挡板法”来考虑每个盒子中元素的数量,通过在元素排成一列的空隙中插入“挡板”来形成不同的...

    二级VB题型:一维数组元素排列

    Dim arr(9) As Integer '声明一个包含10个元素的整数数组,索引从0到9 ``` 3. **数组的初始化**: 声明数组后,我们可以用赋值语句一次性初始化所有元素,或者逐个赋值。一次性初始化可以这样写: ```vb arr =...

    数学排列和组合练习题 加详细解释.rar

    排列是指从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列的方法数。排列的计算公式是P(n, m) = n! / (n - m)!,其中"!"表示阶乘,例如5! = 5 × 4 × 3 × 2 × 1。排列注重的是元素的顺序,所以改变...

    Delphi排列组合小程序演示..rar

    3. **算法实现**:可能包含“next_permutation”(下一个排列)和“combinations”(组合)函数,分别用于生成所有可能的排列和组合。 4. **用户界面(UI)设计**:Delphi提供了可视化组件,如按钮、文本框等,...

    管理类考研数学之排列组合与概率.pdf

    - 问题涉及将编号元素一对一放入相同编号的位置,求配对的方式数。需要先选出配对元素,其余元素不配对。 5. **分相同元素问题** - 特征是将一些相同元素分给几个人,一般要求每人至少一个。使用隔板法,将元素...

    排列组合的全排列算法(交换算法)

    重复这个过程,直到整个序列都是有序的,然后改变指针的位置,继续对新的未排序序列进行相同的操作,直到所有元素都有序排列过。 以下是交换算法实现全排列的基本步骤: 1. 初始化:设定一个起始索引,通常是0,和...

Global site tag (gtag.js) - Google Analytics