一著名软件公司的java笔试算法题！

题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
=======================================================================
412345???

zsh6709(世界上没有后悔药吃的！！！) 你把代码写出来贴后面，让大家看看

int[] position1 = new int{1、2、2、3、4、5};
int[] position2 = new int{1、2、2、3、4、5};
int[] position3 = new int{1、2、2、3、4、5};
int[] position4 = new int{1、2、2、3、4、5};
int[] position5 = new int{1、2、2、3、4、5};
String tempstring = null;
int index= -1;
for (int i1=0;i1<6;i1++){
   for (int i2=0;i2<6;i2++){
       if (i2==i1)
           break;
       for (int i3=0;i3<6;i3++){
            if (i3==i1 || i3==i2 )
               break;
            if (i3==2)
               break;
             for (int i4=0;i4<6;i4++){
                if (i4==i1 || i4==i2 || i4==i3)
                  break;
                  for (int i5=0;i5<6;i5++){
                    if (i5==i1 || i5==i2 || i5==i3 || i5==i4 )
                       break;
tempstring =""+position1[i1]+position2[i2]+position3[i3]+position4[i4]+position4[i4];
if ((index=tempstring.indexof("3")) ){
     if (tempstring.subString(index+1,index+2).equals("5"))
     break;}
if ((index=tempstring.indexof("5")) ){
     if (tempstring.subString(index+1,index+2).equals("3"))
     break;}
                       System.err.println(position1[i1]+position2[i2]+position3[i3]+position4[i4]+position4[i4])
                  }
             }
        }
   }
}

private int[] num = new int[]{1,2,2,3,4,5};
private boolean[] selected = null;
public static void main(String[] args) throws Exception {
new Test().test();
}
private void test() {
selected = new boolean[num.length];
List<Integer> result = new ArrayList<Integer>();
next(result);
}private void next(List<Integer> result) {
if(result.size() == num.length)
printResult(result);
else {
for(int i = 0; i < num.length; i++) {
if(!selected[i]) {
selected[i] = true;
result.add(num[i]);
next(result);
result.remove(result.size() - 1);
selected[i] = false;
}
}
}
}
private void printResult(List<Integer> result) {
if(result.get(2).intValue() != 4) {
for(int i = 1; i < result.size(); i++)
if(result.get(i - 1).intValue() == 3 && result.get(i).intValue() == 5)
return;
for(int i = 0; i < result.size(); i++)
System.out.print(result.get(i));
System.out.println();
}
}

所以我使用selected数组，这个selected表示这个元素是否已经选择过而并不使用list中是否contains方法

哪来的两个4呢?如果两个4可以,那6个4可以不?
要是可以,对6位循环输入就成了,仅仅判断第三位不等于4,3和5不相邻就可以了.
public class Test03 { public static void main(String[] args) {
// TODO Auto-generated method stub
for(int i = 1 ; i <= 5 ; i++){
for(int j = 1 ; j <= 5 ; j++){
if(i==5&&j==3)
continue ;
if(i==3&&j==5)
continue ;
for(int k = 1 ; k <= 5 ; k++){
if(k==5&&j==3)
continue ;
if(k==3)
continue ;
for(int m = 1 ; m <= 5 ; m++){
if(k==5&&m==3)
continue ;
for(int n = 1 ; n <= 5 ; n++){
if(m==5&&n==3)
continue ;
if(m==3&&n==5)
continue ;
for(int p = 1 ; p <= 5 ; p++){
if(p==5&&n==3)
continue ;
if(p==3&&n==5)
continue ;
System.out.println(i+""+j+""+k+""+m+""+n+""+p) ;
}
}
}
}
}
}
}}
以上代码满足:"4"不能在第三位，"3"与"5"不能相连.但是没有去除重复
最后一个数字是555555,哈哈

写个思路
int soruce_value[] = {1,2,2,3,4,5}
如果没有重复值的话，直接一个6重循环就可以了，但是数组有重复元素。
这就可能出现数字的重复。
对于这道题目，我们可以把它看做先拼不重复的五位数，然后再对每一种拼法，在第一个"2"后面再插入第2个"2"。
---------------------------------------------------
这当然只是针对这道题目的做法。一般的，对于一个长度为n的数组a={ai, i=1,2,...n}，假设它包含m个不同的元素，我们可以把它看做是下列2个数组的联合:
A={ai,i=1,...,m}-- 代表a中各个不同的元素
B={bi,i=1,...,m}-- 代表A[i]出现的次数。
那么拼接的方式可以是：
step 1.利用m个不同的元素，拼接出数据B=a1',a2',...am'
step 2.
    While B的长度<n {
       (for i=1; i<=m; i++) {
          如果bi>1，在B的最后一个ai后，再插入一个ai，bi=bi-1
       }
    }
为了实现这种做法，应当会使用到嵌套函数的调用。

《TAOCP》第一章讲有讲这个。叫做Permutation.
具体算法基本的有三种,参看
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

汗, 搬出<TAOCP>来了...

这个题目出的好像不太严谨, 题目如下：用 [1、2、2、3、4、5这六个数字] ，用java写一个main函数，打印出所有不同的排列，如：[512234、412345] 等，要求："4"不能在第三位，"3"与"5"不能相连。如果是全排列, 应该是数字不能有重复, 我猜想题目应该是: 用1-6六个数字, 写函数打印所有全排列,要求是: 4不能在第三位,3与5不能相连.这个用图的遍历应该很简单吧,遍历的过程中加上条件即可.

http://community.csdn.net/Expert/topic/5068/5068524.xml?temp=.2967188发两个怎么

哎。。用了1个半小时。。
package test;import java.util.ArrayList;
import java.util.List;import javax.swing.JFrame;public class test extends JFrame {
    public static void main(String[] arsg) {
        List results = new ArrayList();
        String[] nums = new String[]{"1","2","2","3","4","5"};
        boolean[] used = new boolean[]{false,false,false,false,false,false};
        String cur = "";
        int i1,i2,i3,i4,i5,i6=0;
        for (i1 = 0; i1 < nums.length; i1++) {
            if (used[i1] == true) continue;
            used[i1] = true;
            for (i2 = 0; i2 < nums.length; i2++) {
                if (used[i2] == true) continue;
                used[i2] = true;
                for (i3 = 0; i3 < nums.length; i3++) {
                    if (used[i3] == true) continue;
                    used[i3] = true;
                    for (i4 = 0; i4 < nums.length; i4++) {
                        if (used[i4] == true) continue;
                        used[i4] = true;
                        for (i5 = 0; i5 < nums.length; i5++) {
                            if (used[i5] == true) continue;
                            used[i5] = true;
                            for (i6 = 0; i6 < nums.length; i6++) {
                                if (used[i6] == true) {
                                    continue;
                                }
                                used[i6] = true;
                                cur = nums[i1]+nums[i2]+nums[i3]+nums[i4]+nums[i5]+nums[i6];
                                if (check(cur) == true) {
                                    if (!results.contains(cur)) {
                                        System.out.println(cur);
                                        results.add(cur);
                                    }
                                }
                                used[i6] = false;
                            }used[i5] = false;
                        }used[i4] = false;
                    }used[i3] = false;
                }used[i2] = false;
            }used[i1] = false;
        }
        System.out.println("count: "+results.size());
    }    public static boolean check(String s) {
        if (s.substring(2,3).equals("4")) return false;
        if (s.substring(0,2).equals("35") || s.substring(0,2).equals("53")) return false;
        if (s.substring(1,3).equals("35") || s.substring(1,3).equals("53")) return false;
        if (s.substring(2,4).equals("35") || s.substring(2,4).equals("53")) return false;
        if (s.substring(3,5).equals("35") || s.substring(3,5).equals("53")) return false;
        if (s.substring(4,6).equals("35") || s.substring(4,6).equals("53")) return false;
        return true;
    }}

看见大家循环套循环，圈圈套圈圈的写法，我实在是忍无可忍了，6个数字还好，给你一百个数字，是不是准备百环大作战了？
我来实现一下我之前讲的基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
  1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
  2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
  3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。采用二维数组定义图结构，最后的代码是：import java.util.Iterator;
import java.util.TreeSet;public class TestQuestion {

private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet set = new TreeSet();

public static void main(String[] args) {
new TestQuestion().start();
}

private void start() {

// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
    a[i][j] = 1;
}
}
}

// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;

// Begin to depth　search.
for (int i = 0; i < n; i++) {
    this.depthFirstSearch(i);
}

// Print result treeset.
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}

private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}

// restore the result value and visited value after listing a node.
    result = result.substring(0, result.length() -1);
    visited[startIndex] = false;
}
}可以结贴了。

不就是一个排列组合嘛，搞那么复杂干吗！
package com.mahaixing;
public class Permute {

private int[] temp;
private boolean[] used;
private int[] array;
public int count = 0;

private void printArray() {
for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i]);
}
System.out.println();
}

private void permuteInternal(int pos) {

if (pos == array.length) {
count ++;
printArray();
return;
}

for (int i = 0; i < array.length; i++) {

if (used[i])
continue;

used[i] = true;
if ((pos == 3) && (array[i] == 4)) {
used[i] = false;
continue;
}

if (pos > 0) {
if ((temp[pos - 1] == 5) && (array[i] == 3)) {
used[i] = false;
continue;
}

if ((temp[pos - 1] == 3) && (array[i] == 5)) {
used[i] = false;
continue;
}
}
temp[pos] = array[i]; permuteInternal(pos+1);
used[i] = false;
}

}

public void permute(int[] array) {

this.temp = new int[array.length];
this.used = new boolean[array.length];
this.array = array;
permuteInternal(0);

}

public static void main(String args[]) {

int[] numbers = {1, 2, 3, 4, 5, 6};
Permute ng = new Permute();
ng.permute(numbers);
System.out.println("共有：" + ng.count + " 种排列"); }
}

import java.util.ArrayList;
import java.util.Iterator;public class Test { /**
* @param args
*/
public static void main(String[] args) {
Test test = new Test();
int[] data = { 1, 2, 2, 3, 4, 5 };
ArrayList result = new ArrayList();
int startPoint = 0;
test.returnArrange(data, startPoint, result);
Iterator it = result.iterator();
System.out.println("ArraySizeBefore=" + result.size());
while (it.hasNext()) {
int[] dataMe = (int[]) it.next();
test.printArray(dataMe);
}
result = test.filter(result);
it = result.iterator();
System.out.println("ArraySizeAfterFitler=" + result.size());
while (it.hasNext()) {
int[] dataMe = (int[]) it.next();
test.printArray(dataMe);
}
} public ArrayList getResult(int[] data) {
ArrayList result = new ArrayList();
int startPoint = 0;
returnArrange(data, startPoint, result);
result = filter(result);
return result;
} private ArrayList filter(ArrayList result) {
ArrayList resultList = new ArrayList();
Iterator it = result.iterator();
while (it.hasNext()) {
int[] dataMe = (int[]) it.next();
if (isOK(dataMe)) {
resultList.add(dataMe);
}
}
return resultList;
} private boolean isOK(int[] data) {
return data[2] != 4 && checkConnection(data);
} private boolean checkConnection(int[] data) {
boolean result = true;
for (int i = 0; i < data.length - 1; i++) {
if ((data[i] == 3 && data[i + 1] == 5)
|| (data[i] == 5 && data[i + 1] == 3))
return false;
}
return result;
} private void printArray(int[] data) {
String s = "";
for (int i = 0; i < data.length; i++) {
s += ","+data[i] ;
}
System.out.println(s.substring(1));
} private void returnArrange(int[] data, int startPoint, ArrayList resultList) {
int currentStart = startPoint;
if (isDESC(data, startPoint)) {
resultList.add(copyArray(data));
return;
} else {
returnArrange(data, startPoint + 1, resultList);
for (int index = data.length - 1; index > startPoint; index--) {
if (data[index] > data[startPoint]) {
int anotherStartPoint = startPoint + 1;
exchangeData(data, index, startPoint);
ascArrayByFrom(data, anotherStartPoint);
returnArrange(data, anotherStartPoint, resultList);
}
}
} } private void exchangeData(int[] data, int positionA, int positionB) {
int temp = data[positionA];
data[positionA] = data[positionB];
data[positionB] = temp;
} private int findSmallerPositionBeforeCurrent(int[] data, int current,
int end) {
int i = -1;
int currentNum = data[current];
for (int index = end; index >= current; index--) {
if (data[index] > currentNum) {
return index;
}
}
return i;
} private int[] copyArray(int[] data) {
int[] copy = new int[data.length];
for (int i = 0; i < data.length; i++) {
copy[i] = data[i];
}
return copy; } private boolean isDESC(int[] data, int index) {
for (int i = index; i < data.length; i++) {
int tempMax = data[i];
for (int j = i + 1; j < data.length; j++) {
if (data[j] > tempMax) {
return false;
}
}
}
return true;
} private void ascArrayByFrom(int[] data, int index) {
for (int i = index; i < data.length; i++) {
int tempMin = data[i];
for (int j = i + 1; j < data.length; j++) {
if (data[j] < tempMin) {
tempMin = data[j];
data[j] = data[i];
data[i] = tempMin;
}
}
}
}
}

核心都在returnArrange(),其余都是辅助.

我好象还没看明白题目"写一个main函数" 是不是意味着不能用递归,更不能定义其它的类啊?

arbiter(同济流氓)的那个思路才是王道~!!!
支持~!!!
... ...
...
有点羞于启齿...
... 可不可以把思路再讲解得详细一些?!
虽然看懂了,但是还没有开窍.
请务必帮忙.弄清这道问题,将对我帮助很大.有劳

总算遇到知音了，哪里不清楚的，你可以说出来，我针对你的问题再回答。否则无的放式。
我可以再多说点：3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
代码中请注意这几行：
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;只要这样定义图，根本不用在代码中写IF ELSE语句。
实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一
性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。关于图形数据结构建议先看看数据结构的书，主要是将如何利用二维数组描述图结构，再看看图的深度遍历实现原理。最后再应用到这个问题上来，自然就不难明白了。

都强啊
本来我以为10分钟可以搞定的，结果编写出来后n多错误，看来一个小时也未必能搞定，关键是思想。我觉得
arbiter(同济流氓)
的思想很好，以前学数据结构时没发现有那么大用处，现在总算知道一点了，看来数据结构不能丢~~~~~~~~~

我说说我的思路，递归。
n 个数字求不重复的全排列。
第一个数字可以为这 n 个中的一个，拿出一个，求剩下 n-1 个全排列，拼接在第一个后面。将第一个数字轮换，重复以上操作。

半个小时
不过好像算法不怎么样，以前学的算法都忘光了！！
public class Temp { public static void main(String[] args) {
// TODO Auto-generated method stub
int count =0;
int[] a={1,2,2,3,4,5};
for(int i0=0;i0<6;i0++)
for(int i1=0;i1<6;i1++)
for(int i2=0;i2<6;i2++)
for(int i3=0;i3<6;i3++)
for(int i4=0;i4<6;i4++)
for(int i5=0;i5<6;i5++)
if(check(i0,i1,i2,i3,i4,i5)){
System.out.println(""+a[i0]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]);
count++;
}
System.out.println("总计："+count);
} public static boolean check (int i0,int i1,int i2,int i3,int i4,int i5){
if (i0==i1||i0==i2||i0==i3||i0==i4||i0==i5||i1==i2||i1==i3||i1==i4||i1==i5||i2==i3||i2==i4||i2==i5||i3==i4||i3==i5||i4==i5)
return false;
if(i2==4)
return false;
if ((i0==3&&i1==5)||(i1==3&&i2==5)||(i2==3&&i3==5)||(i3==3&&i4==5)||(i4==3&&i5==5))
return false;
if ((i0==5&&i1==3)||(i1==5&&i2==3)||(i2==5&&i3==3)||(i3==5&&i4==3)||(i4==5&&i5==3))
return false;
int[] b = {i0,i1,i2,i3,i4,i5};
int start=0;
int end=0;
for (int i=0;i<6;i++){
if (b[i]==1)
start = i;
if(b[i]==2)
end =i;
}
if(start<end)
return false;
return true;
}
}

题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
-----------------------1、2、2、3、4、5 6个数字能组出412345？

to: arbiter(同济流氓)
刚才运行了一下你的程序，好像你的有重复吧。头3个结果：
122345
122543
123245最后3个结果
543122
543212
543221

笨笨的硬写一个:结果好像有198个.
public static void main(String args[]) {
    int[] a = new int[6];
    int[] b = new int[6];
    int total = 0;
    outer:for (int i = 122345; i <= 543221; i++) {
      for (int k = 0; k < b.length; k++) {
        b[k] = 0;
      }
      a[0] = i / 100000;
      a[1] = i / 10000 - i / 100000 * 10;
      a[2] = i / 1000 - i / 10000 * 10;
      a[3] = i / 100 - i / 1000 * 10;
      a[4] = i / 10 - i / 100 * 10;
      a[5] = i / 1 - i / 10 * 10;
      if (a[2] == 4)
        continue outer;
      for (int j = 0; j < a.length; j++) {
        if (a[j] > 5)
          continue outer;
        if (a[j] == 3) {
          if (j != 5 && a[j + 1] == 5)
            continue outer;
          if (j != 0 && a[j - 1] == 5)
            continue outer;
        }
        switch (a[j]) {
        case 1:
          b[1]++;
          break;
        case 2:
          b[2]++;
          break;
        case 3:
          b[3]++;
          break;
        case 4:
          b[4]++;
          break;
        case 5:
          b[5]++;
          break;
        }
      }
      if (b[0] == 0 && b[1] == 1 && b[2] == 2 && b[3] == 1 && b[4] == 1 &&
          b[5] == 1) {
        total++;
        System.out.println(i);
      }
    }
    System.out.println("total=" + total);
  }

各位看下我的程序，应该没问题了：
/**
* (c) 2006 Siemens AG
*
* Project    Corba 3GPP North-Bound Interface Agent
* Subproject test
* File       proTest.java
* Created on Oct 17, 2006 by CN1SY082. (TODO check user name)
*
* History:
* Date(Y.M.D) User           Reason (plus CR, LM, Fault number)
*
*/package test1;import java.awt.List;public class proTest {
    private static int[] num = new int[]{1,2,2,3,4,5};

    private static int MAX = num.length;    private static boolean state[] = new boolean[MAX + 1];    private static int item[] = new int[MAX + 1];

    static List numList = new List();

    public static void proNum(){
        String tempNum = "";//store the num String
        int tempIndex = 0;

        DoPermutation(1);

        removeNum(numList);

    }

    public static void DoPermutation(int pos) {
        String tt = "";
        if (pos > MAX) {
            for (int j = 1; j <= MAX; j++){
                tt = tt.concat(String.valueOf(num[item[j]-1]));
            }

            boolean reComp = compareBefor(tt,numList);

            if(reComp == true){
                System.out.println("there is the same elements : " + tt);
            }else{
                numList.add(tt);
            }

            return;
        }
        for (int i = 1; i <= MAX; i++) {
            if (!state[i]) {
                state[i] = true;
                item[pos] = i;
                DoPermutation(pos + 1);
                state[i] = false;
            }
        }
    }

    public static boolean compareBefor(String temNum,List temList){
        boolean bol = false;//if return false , then there are no same String , if return true , then there is the same String

        for(int i = 0; i < temList.countItems(); i++){
            String getList = temList.getItem(i);
            if(getList.equalsIgnoreCase(temNum)){
                bol = true;
            }else{
                bol = false;
            }
        }

        return bol;
    }

    public static void removeNum(List listnum){
        int i = 0;
        for(;i< listnum.countItems(); i++){
            String sdd = listnum.getItem(i);
            if(String.valueOf(sdd.charAt(3)).equals("4")){
                listnum.remove(i);
                break;
            }else if(sdd.contains("35")||sdd.contains("53")){
                listnum.remove(i);
                break;
            }else{
                continue;
            }
        }

        if(i<listnum.countItems()){
            removeNum(listnum);
        }else{
            numList = listnum;
        }
    }    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        proNum();
        for(int i = 0 ; i < numList.countItems(); i++){
            System.out.println(numList.getItem(i));
        }    }
}
/* EOF */

to: arbiter(同济流氓) 抱歉，我弄错了。怪我没看清他的题目，没有考虑到重复的情况。结果应该是198个。

vulner(猪猪) 我想对你说一个字"牛"！你的编程思想！简直是．．．．

package yan;public class RroTest {

static int [] v={1,2,2,3,4,5};
static void check4(int i){
if(v[i]==4){
//continue;
}
}
static void check35(int i, int j){
if((v[i]==3 & v[j]==5)||(v[i]==5 & v[j]==3) ){

}
}
public static void main(String[] args) {
for(int k1=0; k1<6; k1++){
int b1=v[k1];
for(int k2=0; k2<6; k2++){
if((v[k1]==3 & v[k2]==5)||(v[k1]==5 & v[k2]==3) ){
continue;
}
int b2=v[k2];
for(int k3=0; k3<6; k3++){
if(v[k3]==4){
continue;
}
if((v[k2]==3 & v[k3]==5)||(v[k2]==5 & v[k3]==3) ){
continue;
}
int b3=v[k3];
for(int k4=0; k4<6; k4++){
if((v[k3]==3 & v[k4]==5)||(v[k3]==5 & v[k4]==3) ){
continue;
}
int b4=v[k4];
for(int k5=0; k5<6; k5++){
if((v[k4]==3 & v[k5]==5)||(v[k4]==5 & v[k5]==3) ){
continue;
}
int b5=v[k5];
for(int k6=0; k6<6; k6++){
if((v[k5]==3 & v[k6]==5)||(v[k5]==5 & v[k6]==3) ){
continue;
}
int b6=v[k6];
System.out.println(""+b1+b2+b3+b4+b5+b6);
}
}
}
}
}
} }
}

不好意思...重新发过:
按题目要求..我算到结果有:29358种...用了半个钟
package yan;
public class RroTest {
  static int [] v={1,2,2,3,4,5};
  public static void main(String[] args) {
int nunber=0;
for(int k1=0; k1<6; k1++){
   int b1=v[k1];
   for(int k2=0; k2<6; k2++){
if((v[k1]==3 & v[k2]==5)||(v[k1]==5 & v[k2]==3) ){continue;}
int b2=v[k2];
       for(int k3=0; k3<6; k3++){
if(v[k3]==4){ continue;}
if((v[k2]==3 & v[k3]==5)||(v[k2]==5 & v[k3]==3) ){continue;}
int b3=v[k3];
for(int k4=0; k4<6; k4++){
if((v[k3]==3 & v[k4]==5)||(v[k3]==5 & v[k4]==3) ){continue;}
int b4=v[k4];
for(int k5=0; k5<6; k5++){
if((v[k4]==3 & v[k5]==5)||(v[k4]==5 & v[k5]==3) ){continue;}
int b5=v[k5];
for(int k6=0; k6<6; k6++){
if((v[k5]==3 & v[k6]==5)||(v[k5]==5 & v[k6]==3) ){continue;}
int b6=v[k6];
nunber++;
System.out.println(""+nunber+" :"+b1+b2+b3+b4+b5+b6);
}
}
}
}
}
} }
}

public class test
{
public static boolean boo(int i,int j)
{
if(i==2 && j==4 || i==4 && j==2)
return true;
return false;
}
public static void main(String[] args)
{
String str;
int[] arr1={1,2,3,4,5};
int[] arr2={1,2,3,4,5};
int[] arr3={1,2,3,4,5};
int[] arr4={1,2,3,4,5};
int[] arr5={1,2,3,4,5};
for(int i1=0;i1<5;i1++)
{
for(int i2=0;i2<5;i2++)
{
if(boo(i1,i2))
continue;

for(int i3=0;i3<5;i3++)
{
if(boo(i2,i3) || i3==3)
continue;
for(int i4=0;i4<5;i4++)
{
if(boo(i3,i4))
continue;
for(int i5=0;i5<5;i5++)
{
if(boo(i4,i5))
continue;
str=arr1[i1]+""+arr2[i2]+""+arr3[i3]+""+arr4[i4]+""+arr5[i5];
System.out.println(str);
}
}
}
}
}
}
}
1780个结果，无重复

to:yanxiantong() 见笑，见笑:P，数据结构纯属是重修的补考过的，基本没什么概念，得系统的学习下了。

to: arbiter(同济流氓) 、
    mahaixing(猪的克星)、
    seeing2000(飞扬的秋)、
    fifadxj(坦克车)、
    vulner(猪猪)    请教一下，
   你们的结果都不超过 300 个，但我觉得结果应该会超过 400 个，因为6个数的所有排列是： 720 个( 6 * 5 * 4 * 3 * 2 * 1 = 720 ) , 去除少量不符合要求的（应该不会超过 1/3 )，应该会超过 400 个。
   不知我的分析对否，请指正。

to: arbiter(同济流氓) 我跑过上面的程序，我很佩服你们算法，但我总觉得结果会超过 198 个。

to: arbiter(同济流氓)
想法不错，但是，个人认为，如果不是利用set来去处重复项，
就十全十美了。

下面是我以前所能研究出的最精简的序列算法(当然只是对于我来说,肯定还有比这更好的多的算法).我利用了递归算法,一个缺点是不能执行太多个数的序列,否则递归太深会抛出异常,但可以把递归改成for循环,就会避免这个问题,但因为我对递归比较着迷,所以就没去改.至于楼主说的那些不满足的条件,可以加个validate方法,在打印时验证一下即可.本人较懒所以没去做,只是研究算法而已,那些附加条件没什么技术含量.(在这提一点,千万别认为用一大堆for循环算出答案也算是种算法,那跟逐个打印出来没什么两样,试想一下,给你N个数的序列,你该怎么办)public class TestMain {
    public TestMain() {
    }    public static void main(String[] args) {
        TestMain testmain = new TestMain();
        char[] c=new char[]{'1','2','3','4','5'};
        testmain.start(c);
        System.out.println(testmain.count(c.length));
    }    public void start(char[] c){
        start(c,c.length,this.count(c.length),1);
    }    private void start(char[] c,int size,int count,int n){
        if(n>count) return;
        int f1=n%size;
        int f2=f1-1;
        if(f2<0) f2=size-1;
        char temp = c[f1];
        c[f1] = c[f2];
        c[f2] = temp;
        System.out.println(c);
        start(c,size,count,++n);
    }    private int count(int n){
        if(n==1) return 1;
        return n*count(--n);
    }
}

在这里面 arbiter(同济流氓) 图构的思想是最好的,向往之!用图构思路非常清析,但用来解决这道题有点大材小用,效率不够好.(欢迎拍砖,被拍得越惨,就学到越多)

public class Test
{
public static void main(String[] args)
{
int[] a = {1,2,2,3,4,5};
int sum = 0;
for(int i = 0 ; i < a.length ; i++ )
{
for(int j = 0 ; j < a.length ; j++ )
{
if(j == i||i == 3 && j == 5 || j == 3 && i == 5 )continue;
for(int k = 0 ; k < a.length ; k++ )
{
if(k == i || k == j || k == 4 || j == 3 && k == 5 || k == 3 && j == 5)continue;
for(int t = 0 ; t < a.length ; t++)
{
if(t == i || t == j || t == k || k == 3 && t == 5 || t == 3 && k == 5)continue;
    for(int s = 0 ; s < a.length ; s++ )
    {
     if(s == i || s == j || s == k || s == t || s == 3 && t == 5 || t == 3 && s == 5)continue;
     for(int n = 0 ; n < a.length ; n++ )
     {
     if(n == i || n == j || n == k || n == t || n == s || s == 3 && n == 5 || n == 3&& s == 5)continue;
     System.out.println("第"+ sum++ +"种:"+i+j+k+t+s+n);
     }
    }
}
}
}
}

}
}
我用的笨办法,为什么结果有395个?请问哪有问题吗

pirateRocy(海盗罗西):实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一
性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。所以不想用TREESET，可以把心思花在构造唯一性的图上，我这里用TREESET只是偷懒的做法，有兴趣的，可以把符合题目要求的图构造出来，然后直接深度遍历图求解。理论上确实存在你说的十全十美的解法。
TO:guzuoshantou(孤小小) 图的深度遍历原理也是递归，好处在于它首先构造了模型，再处理模型，模型代码和处理模型的代码是松耦合的，自然思路就很清晰，至于说到效率，其实并不低，你可以比较一下，我没跑过你的程序，但是我比较过的其它算法，这是最快的。

再 to: arbiter(同济流氓)如果我没有看错的话，你的结果没有包含排列：532412
253241
531242
531422
412532
453212
453221
453122
241253
242531
253124
421253
221534
212534
425321
415322
253412
153242
532142
142532
215342
245321
425312
122534当然，我只列举了一部分。

做了一下，10分钟太难了，不过觉得自己这个思路比较简单，仅供大家参考。因为是数字数列实际上如果不考虑重复情况，6个数就有6×5×4×3×2×1＝720种情况，程序就是要编写出这个数列，然后重复不重复就很好解决了。我是用字符串解决的。

我谈一下我自己的思路，假设3个字符，1，2，3

传递 1，2，3 数组
取出  1
  传递 2，3 数组
      取出  2
         传递  3  数组
         得到 123
      返回

      取出  3
         传递  2  数组
         得到132
      返回
  返回

取出  2
  传递 1，3 数组
      取出  1
         传递  3  数组
         得到 213
      返回
      取出  3
         传递  1  数组
         得到 231
      返回
  返回

取出  3
  传递 1，2 数组
      取出  1
         传递  2  数组
         得到 312
      返回
      取出  2
         传递  1  数组
         得到 321
      返回
  返回
即依次在数组中抽取一个元素，然后将抽取后的数组传递下去，进行下一次抽取，直到剩下一个元素

现在考虑4个元素 1，2，3，4

应该是这样的结果

1  2  3  4
1  2  4  3
1  3  2  4
1  3  4  2
1  4  2  3
1  4  3  2

2  1  3  4
2  1  4  3
2  3  1  4
2  3  4  1
2  4  1  3
2  4  3  1

3  1  2  4
3  1  4  2
3  2  1  4
3  2  4  1

4  1  2  3
4  1  3  2
4  2  1  3
4  2  3  1
4  3  1  2
4  3  2  1

所以根据这个思路必须使用递归函数。根据这个思路写了以下一段程序

关键是2点，一个是递归的时候，每递归一次，传递一个新数组，数组元素去掉1个
第二是必须把丢掉的数组元素也一并传递进去，否则字符串就少了。

package Test;
public class PrintListTest1 {
  //计算总共有多数符合条件的列表
  private static int i=0;

  //结果字符串
  String resultstr="" ;

//将数组转换成字符串  也可以合并成一个数组什么的
  private String getList(int[] a){
    String result="";
    for(int len=0;len<a.length;len++)
      result=result+a[len];
    return result;
  }
  //判断是否符合条件这个对程序意义不大的
  private boolean isValidStr(String str){
    if (str.charAt(2)=='4')
      return false;
    if (str.indexOf("35")>-1)
      return false;
    if (str.indexOf("53")>-1)
      return false;
    return true;
  }
  /*
  传递去除元素的数组，好像数组没有直接方法可以删除一个元素
  只能再造一个数组
  */
  private int[] DelArray(int[] a,int pos){
    if (pos>a.length-1) return a;
    int len=a.length-1;
    int[] newArray=new int[len];
    for(int i=0;i<len+1;i++){
      if (i<pos) newArray[i]=a[i];
      if (i>pos) newArray[i-1]=a[i];
    }
    return newArray;
  }
  void GetList(String prestr,int[] a){
  /*
    prestr 就是被抽取得数组元素，为了简便使用字符串
    大家也可以使用数组什么的
  */
    /*
    这个是符合题目的一段，但是觉得打印出
    完整数列才是题目的意义，符合条件什么的就很简单了
    判断是否符合条件，判断是否重复
    if (a.length<2){
      String result;
      result=prestr+getList(a);
      if(isValidStr(result)){
      //if(true){
        if (resultstr.indexOf(result)==-1){
          i++;
          resultstr=resultstr+result+"\n";
        }
      }
      return;
    }
    */
    //以下这段是得到完整数列
    if (a.length<2){
      i++;
      String result=prestr+getList(a);
      resultstr=resultstr+result+"\n";
      return;
    }
    for(int i=0;i<a.length;i++)
      GetList(prestr+a[i],DelArray(a,i));
  }

  public static void main(String[] args) {
    PrintListTest1 printlisttest1 = new PrintListTest1();
    int[] a={1,2,2,3,4,5};
    printlisttest1.GetList("",a);
    System.out.println(printlisttest1.resultstr);
    System.out.println("共有"+printlisttest1.i+"种排列");
  }}

共 198 个排列。

不好意思，上面写的乱了，我就把打印所有数组排列结果的程序重新列一下吧，条件判断其实不难的。自己加就行了。package Test;public class PrintListTest1 {  //计算总共有多少列表
  private static int i=0;
  //保存所有排列结果
  String resultstr="";  //将数组转换成字符串
  private String getList(int[] a){
    String result="";
    for(int len=0;len<a.length;len++)
      result=result+a[len];
    return result;
  }  /*
  传递去除元素的数组
  */
  private int[] DelArray(int[] a,int pos){
    if (pos>a.length-1) return a;
    int len=a.length-1;
    int[] newArray=new int[len];
    for(int i=0;i<len+1;i++){
      if (i<pos) newArray[i]=a[i];
      if (i>pos) newArray[i-1]=a[i];
    }
    return newArray;
  }  void GetList(String prestr,int[] a){
    //只有一个数组元素的时候就返回结果了
    if (a.length<2){
      String result= prestr+getList(a);  //结果
      resultstr=resultstr+result+"\n" ;
      i++;
      return;
    }    //关键是下面一句，递归
    for(int i=0;i<a.length;i++)
      GetList(prestr+a[i],DelArray(a,i));
  }
    public static void main(String[] args) {
    PrintListTest1 printlisttest1 = new PrintListTest1();
    int[] a={1,2,2,3,4,5};
    printlisttest1.GetList("",a);  //得到所有排列
    System.out.println(printlisttest1.resultstr);
    System.out.println("共有"+printlisttest1.i+"种排列");
  }
}

我很喜欢vulner(猪猪) 的算法，简单易懂arbiter(同济流氓)的算法也很喜欢，就是看起来累，学图论和数据结构的时候睡觉去了，呵呵

最土的算法
    public static void main(String[] args) {
        for (int i = 122345; i <= 543221; i++) {
            String s = "" + i;
            if (s.substring(2,3).equals("4")|| s.indexOf("35") > 0 ||
                s.indexOf("53") > 0) {
                continue;
            }
            if (s.indexOf("1") >= 0 && s.indexOf("2") >= 0 &&
                s.indexOf("3") >= 0 && s.indexOf("4") >= 0 &&
                s.indexOf("5") >= 0 && s.indexOf("2") != s.lastIndexOf("2")) {
                System.out.println(s);
            }
        }
    }

我的想法.这个是一个笔试题.就是说从这个题上考官不只想看到你的算法.他看到的会更多.十分钟对于最优算法来说明显不够.可能有些牛人能做到.但是那个人应该做考官.不应该被考.就好像做项目的时候.最适当才是最好.一切追求最优的人很可能给项目带来不可预测的麻烦.不是程序上的.而是时间上的.能够权衡利弊才能把项目作好.有些情况下为了开发周期必须放弃最优.就好像放弃汇编而使用java一样.估计这个考官要的是一个看到题目就知道自己十分钟内做不到最优而权衡利弊的人.这种情况下,用一个粗浅的,垃圾的,甚至令人恶心的算法来解决这个问题很可能是更优的.完全可以用随机排列判断是否符合规则并去除重复的方法来做(或者更垃圾的).十分钟一定够.虽然从效率上会低很多,甚至几个数量级.但是对于题目的情况,还是可以接受的.如果快一点,我们甚至可以用五分钟完成并用五分钟做review甚至cut以提高稳定性.

不用算法可以吗，这样做。
public class Test { /**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
String s = "";
int j = 0;
for (int i = 122345; i < 543221; i++) {
s = String.valueOf(i);
if (s.contains("1") && s.contains("2") && s.contains("3")
&& s.contains("4") && s.contains("5") && !s.contains("0")
&& !s.contains("6") && !s.contains("7") && !s.contains("8")
&& !s.contains("9") && !s.contains("35")
&& !s.contains("53") && !s.contains("222")
&& s.indexOf("4") != 3 && exitCount(s, "1")
&& exitCount(s, "3") && exitCount(s, "4")
&& exitCount(s, "5")) {
System.out.println(s);
j++;
}
}
System.out.println(j);
} private static boolean exitCount(String s, String i) {
if (s.indexOf(i) == s.lastIndexOf(i))
return true;
else
return false;
}}

我的算法,以前算过九宫格问题,受点哪个影响.结果应该对(不对的话请兄弟留言).
public class MathTest
{
    public static void main(String args[])
    {
        String[] a = {"1","2","2","3","4","5"};
for (int i1 = 0; i1<a.length; i1++)
{
for (int i2 = 0; i2<a.length; i2++)
{
if((i2==i1)||(i1==3&&i2==5)||(i1==5&&i2==3)) continue;
for (int i3 = 0; i3<a.length; i3++)
{
if((i3==i1)||(i3==i2)||(i3==3&&i2==5)||(i3==5&&i2==3)||i3==4)continue;
for (int i4 = 0; i4<a.length; i4++)
{
if((i4==i1)||(i4==i2)||(i4==i3)||(i4==3&&i3==5)||(i4==5&&i3==3))continue;
for (int i5 = 0; i5<a.length; i5++)
{
if((i5==i4)||(i5==i3)||(i5==i2)||(i5==i1)||(i5==3&&i4==5)||(i5==5&&i4==3))continue;
for (int i6 = 0; i6<a.length; i6++)
{
if((i6==i5)||(i6==i4)||(i6==i3)||(i6==i2)||(i6==i1)||(i6==3&&i5==5)||(i6==5&&i5==3))continue;
System.out.println (a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]);
m = m+1;
}
}
}
}
}
}
    }
}

也来个简单的，楼上的判断有重复public static void main(String[] args) {
    int count = 0;
    for (int i = 122345; i < 543221; i++) {
      String s = Integer.toString(i);
      if (s.indexOf("1") > -1 && s.indexOf("2") > -1 && s.indexOf("3") > -1 &&
          s.indexOf("4") > -1 && s.indexOf("5") > -1 &&
          s.indexOf("2") != s.lastIndexOf("2") &&
          s.indexOf("4") != 2 &&
          s.indexOf("35") < 0 && s.indexOf("53") < 0)
     {
        System.out.println(++count + ":" + s);
      }
    }
  }满足条件的结果，197个。

唉，如果是面试你算法水平的话，写那么长的代码还有点意义。
如果是面试你的Java水平的话，写那么长的代码是浪费人家公司的纸。
看看JDK的Document，使用SET接口的话，可以避免重复的问题，最困难的部分Java都帮你解决了，唉。

// 改编自  acd123456(低智商野蛮人)class a{
public static void main(String[] args) {
java.util.List list = new java.util.ArrayList();
        for (int i = 122345; i <= 543221; i++) {
            String s = "" + i;
            if (s.substring(2,3).equals("4")|| s.indexOf("35") > 0 || s.indexOf("53") > 0){
                continue;
            }
            if (   s.indexOf("1") == -1
             || s.indexOf("2") == -1
             || s.indexOf("3") == -1
             || s.indexOf("4") == -1
             || s.indexOf("5") == -1
             || !(s.indexOf("1") == s.lastIndexOf("1"))
             || !(s.indexOf("3") == s.lastIndexOf("3"))
                || !(s.indexOf("4") == s.lastIndexOf("4"))
                || !(s.indexOf("5") == s.lastIndexOf("5"))
                || (s.indexOf("2") == s.lastIndexOf("2"))){
                //System.out.println(s);
                continue;
            }else{
             System.out.print(s+"><");
             list.add(s);
            }
        }
         System.out.println("total : "+list.size());
}
}

to acd123456(低智商野蛮人),你给出的下列数字不符合条件。
351224
351242
351422
352124
352142
352214
352241
352412
352421
531224
531242
531422
532124
532142
532214
532241
532412
532421我顺便给出我的垃圾答案。
/**
*
*/
package zhangshu.test.samples;import java.util.Iterator;
import java.util.TreeSet;/**
* @author wdman
*
*/
public class Test { /**
* @param args
*/
public static void main(String[] args) {
char[] charSets = {'1','2','2','3','4','5'};
TreeSet resultSet = new TreeSet();

for (int a=0; a<charSets.length; a++) {
for (int b=0; b<charSets.length; b++) {
if (b==a) continue;
for (int c=0; c<charSets.length; c++) {
if(c==a || c==b) continue;
for (int d=0; d<charSets.length; d++) {
if (d==a || d==b || d==c) continue;
for (int e=0; e<charSets.length; e++) {
if (e==a || e==b || e==c || e==d) continue;
for (int f=0; f<charSets.length; f++) {
if (f==a || f==b || f==c || f==d || f==e) continue;
char[] result = {charSets[a],charSets[b],charSets[c],charSets[d],charSets[e],charSets[f]};
resultSet.add(new String(result));
}
}
}
}
}
}

//output
int count = 0;
Iterator it = resultSet.iterator();
while(it.hasNext()) {
String result = (String)it.next();
if ((result.charAt(2) == '4')
|| (result.indexOf("35")>-1)
|| (result.indexOf("53")>-1)) continue;
System.out.println(result);
count++;
}
System.out.println("Total:" + count);
}
}大家运行一下可以知道，得出的正确答案是198

调试易

一著名软件公司的java笔试算法题！

解决方案 »