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

题目：{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;
	}
}