回复"一著名软件公司的java笔试算法题"有兴趣请进

Question

一著名软件公司的java笔试算法题！算法程序题：
    该公司笔试题就1个，要求在10分钟内作完。
    题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
这是javaliu2006 ()的帖子内容.
我写了一个程序,得到结果是396个,但是我看回复的兄弟们有说198的还有216的,我也搞不清楚哪个对的,请高手判断一下吧.源程序如下:
public class MathTest
{
 public static void main(String args[])
 {
  String[] a = {"1","2","2","3","4","5"};
   int m = 0;
    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;
   }
  }
}
        }
       }
      }
 System.out.println ("count "+m);
   }
}方便大家判断我把结果也贴上
122345
122543
123245
123254
123425
123452
125234
125243
125423
125432
122345
.
.
.
542231
542312
542321
543122
543122
543212
543221
543212
543221
count 396

Answer 1

先全排，p66 =6*5*4*3*2=720
减去 4在第三位的p55 =120  剩600
减去 35相连的p22*p55=240 剩360
加上 4在第三位并且35相连的p22*p44= 48 剩312
最后因为有2个2，对等交换是不变的，所以除2 156个
10分钟时间，笔试以前没研究过全排列的算法的话估计搞不定。无视效率的话全排列出来
再判断“35”，“53”，以及第三位为4的就ok了，哈，不知道会不会过。

Answer 2

如果不考虑执行效率的话，我给出的应该是正确答案。/**
 * 
 */
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(3) == '4') 
|| (result.indexOf("35")>-1)
|| (result.indexOf("53")>-1)) continue; 
System.out.println(result);
count++;
}
System.out.println("Total:" + count);
}
}执行结果：
122345
122543
123245
123254
124325
124523
125234
125243
132245
132254
132524
132542
134225
134252
134522
142325
142523
542213
542231
542312
542321
543122
543212
543221
Total:198

Answer 3

~计算结果肯定是198个！
~wxg1008(嘻嘻哈哈)在加上的部分算错了：c31*p33*2=36（4确定，35捆绑算一个书，这样先把35位置确定c31，剩下三个数全排列p33，最后35交换*2〕这样总数396/2=198
~楼主忽略了所给的六个数中有两个“2”，这样每个六位数楼主都统计了两次~

Answer 4

谢谢lower0661()同学的指正，我的算法的确有问题。虽然能修改正确，但是这么多循环的确恶心，我在向“同济流氓”学习，图形遍历的思想很好，我以前写的一个五子棋就是用到这种思想不过没有这个复杂，我刚进行业不久，不足之处还得多向各位请教，在这里谢一下那些不惜赐教的同行们。

Answer 5

感谢lower0661指正，呵呵