当前位置:首页 > 开发 > 编程语言 > Java > 正文

两种方法-用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412325等.要求:"4"不能在第三位

发表于: 2012-03-19   作者:bylijinnan   来源:转载   浏览次数:
摘要: package a.test; import java.util.HashSet; import java.util.Set; public class Perm { /** * 题目:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412325等. * 要求:"4"不能在第三位,
package a.test;

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

public class Perm {
	
	/**
	 * 题目:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412325等.
	 * 要求:"4"不能在第三位,"3"与"5"不能相连
	 * A(6,6)-A(5,5)-2*5*A(4,4)+2*3*A(3,3)=396,396/2=198
	 * two solutions:
	 * 1.Permutation
	 * 2.Graph,depthFirst
	 */

	public static final int BAD_INDEX = 3;
	public static final int BAD_VALUE = 4;
	public static final int FIRST_VALUE = 3;
	public static final int SECOND_VALUE = 5;
	/*use 'Set' to reject duplicate string.Maybe we should do this at the very beginning(create the string),but how?
I google it,and I find this:
1.let data = { 1, 2, 6, 3, 4, 5 };
2.get all the permutation of 'data',but only store the strings which match "str.matches("^.*6.*2.*$")" (or str.matches("^.*2.*6.*$"))
3.str.replace('6','2')
        */
	private Set<String> resultSet=new HashSet<String>();
	
	public static void main(String[] args) {
		Perm p = new Perm();
		int[] data = { 1, 2, 2, 3, 4, 5 };
		p.perm(data, 0, data.length - 1);
		Set<String> set=p.getResultSet();
		for(String str :set){
			System.out.println(str);
		}
		System.out.println(set.size());
		
	}

	//find all possible combination
	public void perm(int[] data, int begin, int end) {
		if (data == null || data.length == 0) {
			return;
		}
		if (begin == end) {
			boolean ok = check(data);//exclude the 'bad' string
			if (ok) {
				String str=stringOf(data);
				resultSet.add(str);
			}
		}
		for (int i = begin; i <= end; i++) {
			swap(data, begin, i);
			perm(data, begin + 1, end);
			swap(data, begin, i);
		}
	}

	//exclude the 'bad' string--"4"不能在第三位,"3"与"5"不能相连
       //we can also use regular expression:(!str.matches("^..4.*$")&&!str.matches("^.*((35)|(53)).*$")&&str.matches("^.*2.*6.*$"))
	public boolean check(int[] data) {
		if (data == null || data.length == 0) {
			return false;
		}
		for (int i = 0, len = data.length; i < len - 1; i++) {
			if (data[i] == FIRST_VALUE && data[i + 1] == SECOND_VALUE
					|| data[i + 1] == FIRST_VALUE && data[i] == SECOND_VALUE) {
				return false;
			}
			if (i + 1 == BAD_INDEX && data[i] == BAD_VALUE) {
				return false;
			}
		}
		return true;
	}

	//int[] data = { 1, 2, 2, 3, 4, 5 }-->"122345"
	public String stringOf(int[] x){
		StringBuilder sb=new StringBuilder();
		for(int i=0,len=x.length;i<len;i++){
			sb.append(x[i]);
		}
		return sb.toString();
	}
	
	public void swap(int[] x, int i, int j) {
		int tmp = x[i];
		x[i] = x[j];
		x[j] = tmp;
	}
	
	public Set<String> getResultSet(){
		return resultSet;
	}
}


package a.test;

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

public class Graph {

	/**
	 * 题目:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412325等.
	 * 要求:"4"不能在第三位,"3"与"5"不能相连
	 * A(6,6)-A(5,5)-2*5*A(4,4)+2*3*A(3,3)=396,396/2=198
	 * two solutions:
	 * 1.Permutation
	 * 2.Graph,depthFirst
	 */
	
	private static final int[] DATA={1,2,2,3,4,5};
	private static final int LENGTH=DATA.length;
	private boolean[] visited;
	private int[][] matrix;
	private StringBuilder resultString;
	private Set<String> resultSet;//use 'Set' to reject duplicate string.
	
	public static void main(String[] args) {
		Graph graph=new Graph();
		graph.initial();
		for(int i=0;i<LENGTH;i++){
			graph.depthFirst(i);//start from 1,2,2,3,4,5,find their corresponding DFS
		}
		graph.print();
	}

	public void initial(){
		resultString=new StringBuilder();
		resultSet=new HashSet<String>();
		int n=LENGTH;
		visited=new boolean[n];
		matrix=new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j){
					matrix[i][j]=0;
				}else{
					matrix[i][j]=1;
				}
			}
		}
		//"3"与"5"不能相连
		matrix[3][5]=0;
		matrix[5][3]=0;
	}
	
	public void depthFirst(int origin){
		//case 1.resultString includes DATA[origin]
		resultString.append(DATA[origin]);
		visited[origin]=true;
		if(resultString.length()==LENGTH){
			boolean ok=resultString.charAt(2)!='4';//"4"不能在第三位
			if(ok){
				resultSet.add(resultString.toString());
			}
		}
		for(int i=0;i<LENGTH;i++){
			if(!visited[i]&&matrix[origin][i]==1){
				depthFirst(i);
			}else{
				continue;
			}
		}
		//case 2.resultString don't include DATA[origin]
		resultString.deleteCharAt(resultString.length()-1);//remove DATA[origin]
		visited[origin]=false;
	}
	
	public void print(){
		for(String str:resultSet){
			System.out.println(str);
		}
		System.out.println(resultSet.size());
	}
}

两种方法-用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412325等.要求:"4"不能在第三位

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
2015/07/21 更新: 利用python写出1加到任意数关于range()函数的妙用的交互小程序 那模板都要被你们
/* * 程序的版权和版本声明部分: * Copyright (c) 2013.烟台大学计算机学院。 * All rights reserve
;============================================== ;1+...+n < 100 ;--------------------------
迅驰并非是CPU的代号,它是英特尔于2003年3月12日,面向笔记本电脑推出的无线移动计算技术的品牌名称
Sublime Text这是程序员最喜爱的编辑器,说说在win7下使用Sublime Text来编写as文件以及编译与运行s
为满足项目需求,我用java写了一个生成Box2D b2PolygonShape多边形顶点的工具。 也是一步一步完成的
Exercise1 print "Hello World!" print "Hello Again" print "I like typing this." print "This is
错误内容:No JVM could be found on your system. Please define EXE4J_JAVA_HOME to point to an
function fibo(n) { var f = []; for (var c = 0; c < n; ++c) { console.log(f.join("")) f.pus
一、查看字节码 在java中利用javap -verbose classname 可以生成类的字节码信息。 public class Cal
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号