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

原题如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求： "4 "不能在第三位， "3 "与 "5 "不能相连.
我看了回贴都没有很好解决，主要是没有排除重复。
解决思路：强化题目，用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路：显然是递归，初始序列122345，先从末两位(45)变化(45,54),然后末三位(345)   ...   直到最后六位.怎样解决重复问题？很简单，由于是递增序列，每生成新序列可与前一生成序列比较，如 <放弃当前序列。当然有更好效率，如预先预测。

方法一代码如下：

class   test 
{   
    //   当前固定部分 
    private   String   CurFixPart; 
    private   String   PreGenNum; 
    
public   static   void   main(String[]   args) 
{ 
  test   t=new   test(); 
  t.GenControll( "122345 "); 
} 

//   调整字符串s位置pos字符到最前 
private   String   shift(String   s,   int   pos) 
{ 
String   newStr; 
if   (s.length()> pos+1) 
    newStr=s.substring(pos,   pos+1) 
                +s.substring(0,   pos) 
                +s.substring(pos+1); 
else 
    newStr=s.substring(pos) 
                +s.substring(0,   pos); 
return   newStr; 
} 

protected   int   Validate(String   newNum) 
{ 
    String   newGenNum=CurFixPart+newNum; 
    if   (Integer.valueOf(newGenNum) <=Integer.valueOf(PreGenNum)) 
        return   0; 
    if   (newGenNum.substring(2,3).equals( "4 ")   ||   
              (newGenNum.indexOf( "35 ")!=-1)   ||   (newGenNum.indexOf( "53 ")!=-1))   
        return   0; 
            
    PreGenNum=newGenNum; 
System.out.println(newGenNum); 
return   0; 
} 
  
public   void   GenControll(String   Base) 
{ 
    PreGenNum= "0 "; 
CurFixPart= " "; 
GenNext(Base,   0); 
} 

void   GenNext(String   varPart,   int   curPos) 
{ 
if   (varPart.length()==2) 
{ 
    Validate(varPart); 
    Validate(shift(varPart,   1)); 
    return; 
  } 
//   Next   Layer 
String   newGen=shift(varPart,   curPos); 
String   SavedFixPart=CurFixPart; 
CurFixPart=CurFixPart+newGen.substring(0,1); 
GenNext(newGen.substring(1),   0); 
CurFixPart=SavedFixPart; 
//   同层递增 
if   (curPos==varPart.length()-1)     
    return; 
GenNext(varPart,   curPos+1); 
} 
} 
序列122345测试通过。 

 

方法二

其中输入的数组长度和重复的数字可以调整。但是规则是固定的。以后再考虑怎么完善成可以处理任意的字符串，规则也可以考虑用一个可配置的数组来表示。

大体的思路就是先对原始数组排序。并生成重复数字的标记数组。
在主算法的每一层循环对原始数组中的某一位数字的所有可能的位置做全枚举，同时当该位数字不是第一次出现的时候，其位置只能是上一位数字（重复数字）右侧。然后递归调用。 

用 122345 和 1222345 测试 OK

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author Owen Luo
 * @version Created at 2008-11-6 下午12:51:48 用 ArrayList 和 StringBuffer 来实现较少的资源占用。
 */

public class CSDN_ArrayQuest_081106 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        long   beginTime   =   System.currentTimeMillis(); 
        CSDN_ArrayQuest_081106 newProcess = new CSDN_ArrayQuest_081106();
        newProcess.preJobs();
        for (int a = 0; a < newProcess.arrayLength; a++) {
            newProcess.process(newProcess.posAL, a, 0);
        }
        long   endTime   =   System.currentTimeMillis(); 
        System.out.println(newProcess.counter);
        System.out.println( "Computation   time:   "+   (endTime-beginTime)); 
        
        

    }

    // pozAL 剩下的位置列表，从小到大，顺序排列
    // pozIndex 位置列表中遍历的起始位置
    // digitIndex 目前正在遍历处理的数字在原始排序数组中的位置

    public void process(ArrayList<Integer> pozAL, int pozIndex, int digitIndex) {

        // make a copy of pozAL
        ArrayList<Integer> tempAL = new ArrayList<Integer>(pozAL.size());
        for (int i = 0; i < pozAL.size(); i++) {
            tempAL.add(Integer.valueOf(pozAL.get(i).intValue()));
        }

        posArray[digitIndex] = tempAL.get(pozIndex).intValue();
        tempAL.remove(pozIndex);
        int nextPozIndex;
        if (digitIndex != arrayLength - 1) {
            if (flagArray[digitIndex + 1] == 1) {
                nextPozIndex = 0;
            } else {
                nextPozIndex = pozIndex; //如果是重复对象，只放右边
            }
            for (int i = nextPozIndex; i < tempAL.size(); i++) {
                process(tempAL, i, digitIndex + 1);
            }
        } else {
            genResult(posArray); //这里用一个 StringBuffer 对象，避免String类型的变量占用过多资源。
            // 条件筛出 “35”，“53”，“4”在第二位的情况
            if (result.indexOf("35") == -1 & result.indexOf("53") == -1
                    & result.indexOf("4") != 2) {
                counter++;
                System.out.println(result.toString());
            }
        }

    }

    public void preJobs() {

        // sorting original number array
        Arrays.sort(numArray);

        // initialize posArray
        posArray = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {
            posArray[i] = i;
        }

        posAL = new ArrayList<Integer>(arrayLength);
        for (int i = 0; i < arrayLength; i++) {
            posAL.add(Integer.valueOf(i));
        }

        // initialze flagArray
        flagArray = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {

            if (i == 0) {
                flagArray[i] = 1;
            } else {
                flagArray[i] = (numArray[i - 1] == numArray[i]) ? 0 : 1;
            }

        }

    }

    public void genResult(int[] pozIndex) {

        result.ensureCapacity(arrayLength);
        for (int i = 0; i < arrayLength; i++) {
            result.insert(pozIndex[i],numArray[i]);
            result.delete(pozIndex[i]+1,pozIndex[i]+2);
        }
        
    }

    int[] numArray = { 1, 2, 2, 2 ,3, 4, 5 };
    int[] posArray;
    int[] flagArray;
    int arrayLength = numArray.length;
    StringBuffer result = new StringBuffer("");
    int counter = 0;
    int counterALL = 0;
    ArrayList<Integer> posAL;

}

  

方法三

对于任意一个串利用递归进行排列时，我们是循环串中的每个字符到第一个字符进行递归。如果串中字符出现重复的话，则重复的字符只可以利用递归算法一次，即只要与前面相同的字符循环到第一个字符时不调用递归就可以避免重复，为此，我们只需要按如下方式修改算法：

import   java.util.*; 
public   class   test   { 
static   int   count=0; 
        public   static   void   main(String[]   arg)   { 
                Scanner   r=new   Scanner(System.in); 
                String   s=r.nextLine(); 
                Pailie(s, " "); 
                System.out.println( "Total: "+count); 
        } 
        static   void   Pailie(String   s,String   p)   { 
                if(s.length() <1)   { 
                System.out.println(p);//字符串长度小于1，换行 
                count++; 
                } 
                else   { 
                int   index[]=new   int[s.length()]; 
                for(int   i=0;   i <s.length();   i++)//该循环将所有字符的第一次出现的位置记录在数组index中 
                index[i]=s.indexOf(s.charAt(i)); 
                for(int   i=0;   i <s.length();   i++)   { 
                if(i==index[i])//只有当循环数与第一次记录数相等时才递归，保证相同字符中的第一个调用 
                Pailie(s.substring(1),p+s.substring(0,1));//递归，打印其它字符 
                s=s.substring(1)+s.substring(0,1);//循环移位 
                        } 
                } 
        } 
} 
这样，由于相同的字符只递归调用了一次，则避免了重复串的排列。下面是几个典型的运算结果： 
2222222（输入。当串中的所有字符相同时，应该递归调用1次） 
2222222 
Total:1 

122222（输入。当串中只有一个字符不同时，该字符应该循环所有不同位置） 
122222 
222221 
222212 
222122 
221222 
212222 
Total:6 

1223（输入。szlhj的例子） 
1223 
1232 
1322 
2231 
2213 
2312 
2321 
2123 
2132 
3122 
3221 
3212 
Total:12 

122345（输入。本题的要求，最后结果为360个，其它的我就不列出来了，大家可以自己测试） 
122345 
122354 
122453 
122435 
122534 
…… 
543221 
543212 
Total:360