一道java算法题，测试你是否会使用java正则表达式

Question

题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。要求：使用java的正则表达式。使用java正则表达式只需要把第三位为4的，3与5相连的过滤掉就行了。

Answer 1

学习学习,什么叫使用java中的正规表达式?给举个例子,什么是正规表达式?

Answer 2

虽然不是很好，但能用，
其实还有更好的方式，应该可以把正则表达式可以写成一个，比如用lookahead等技术，但太费脑子了：
import java.util.regex.Pattern;
/**
 * 
 * 
 * 
 * @author jinxfei
 *
 */
public class Test {

private static int length=6;
static Pattern invalide1=Pattern.compile("^..4.*");
static Pattern invalide2=Pattern.compile(".*?(35|53).*");
static int[] numbers=new int[]{1,2,2,3,4,5};
static int[] indexs=new int[]{0,0,0,0,0,0};

public static void main(String[] args) throws Exception{ 
while(!indexOverflow()){
String str=getCurComposite();
boolean false1=invalide1.matcher(str).find();
boolean false2=invalide2.matcher(str).find();
if (!(false1 || false2)){
System.out.println("Match:"+str);
}
incIndex();
}
} 


private static String getCurComposite(){
StringBuffer sb=new StringBuffer();
for(int i=0; i<indexs.length;i++){
sb.append(numbers[indexs[i]]);
}
return sb.toString();
}
private static void incIndex(){
int addOn=1;
for(int i=0;i<indexs.length;i++){
if (indexs[i]+addOn<numbers.length){
indexs[i]+=addOn;
break;
}else{
indexs[i]=0;
}
}
}
private static boolean indexOverflow(){
boolean over=true;
for(int i=0;i<indexs.length;i++){
if (indexs[i]<numbers.length-1){
over=false;
break;
}
}
return over;
}
}

Answer 3

其实这个题的难度在于计算所有的组合，^_^，如果不费点心思，还真是难以写出比较好看的代码。六重循环最简单，但也最没技术含量。我用了一个六位长的数组，模拟六进制数，从000000开始，每次加1，一直加到555555，每次都按位到numbers这个数字索引里取出对应的数字组成一个字符串。我的数学不好，还是有些笨，期待更好的算法。

Answer 4

是排列（Permutation），不是组合（Combination）吧 ：-）
P.S. 已经有很好的排列实现算法了。

Answer 5

呵呵，当然，现在几乎什么线程的算法都有，google万能嘛。不过，既然要做题，就挑战一下自己的脑细胞吧。

Answer 6

转某位高手写的
public class Zuhe { public static void main(String[] args) { 
String s = "122345";//这里是要用到的所有数组成的一个字符串,其它字符同样适用 
char[] c = s.toCharArray(); 
new Zuhe().zuhe(c,c.length,0); 
System.out.println("可能的组合数："+kk); 
} 
static int kk=0; 
private void zuhe(char[] array, int n, int k) { 
if (n == k) { 
if(array[2]!='4'){//第三个位置不能出现4 
String str = new String(array); 
if(str.indexOf("53")<0&&str.indexOf("35")<0){//3，5不能连续出现 
System.out.println(str); 
++kk; 
} 
} 
} else { 
for (int i = k; i < n; i++) { 
swap(array, k, i); 
zuhe(array, n, k + 1); 
swap(array, i, k); 
} 
} 
} private void swap(char[] a, int x, int y) { 
char temp = a[x]; 
a[x] = a[y]; 
a[y] = temp; 
} 
} 
========结果========= 
122345 
122543 
123245 
123254 
123425 
123452 
125432 
125423 
125243 
125234 
122345 
122543 
123245 
123254 
123425 
123452 
125432 
125423 
125243 
125234 
132245 
132254 
132425 
132452 
132542 
132524 
132245 
132254 
132425 
132452 
132542 
132524 
142325 
142523 
143225 
143252 
143225 
143252 
142325 
142523 
145232 
145223 
145223 
145232 
152342 
152324 
152432 
152423 
152243 
152234 
152342 
152324 
152432 
152423 
152243 
152234 
212345 
212543 
213245 
213254 
213425 
213452 
215432 
215423 
215243 
215234 
221345 
221543 
223145 
223154 
223415 
223451 
225431 
225413 
225143 
225134 
232145 
232154 
232415 
232451 
232541 
232514 
231245 
231254 
231425 
231452 
231542 
231524 
242315 
242513 
243215 
243251 
243125 
243152 
241325 
241523 
245132 
245123 
245213 
245231 
252341 
252314 
252431 
252413 
252143 
252134 
251342 
251324 
251432 
251423 
251243 
251234 
221345 
221543 
223145 
223154 
223415 
223451 
225431 
225413 
225143 
225134 
212345 
212543 
213245 
213254 
213425 
213452 
215432 
215423 
215243 
215234 
231245 
231254 
231425 
231452 
231542 
231524 
232145 
232154 
232415 
232451 
232541 
232514 
241325 
241523 
243125 
243152 
243215 
243251 
242315 
242513 
245231 
245213 
245123 
245132 
251342 
251324 
251432 
251423 
251243 
251234 
252341 
252314 
252431 
252413 
252143 
252134 
322145 
322154 
322415 
322451 
322541 
322514 
321245 
321254 
321425 
321452 
321542 
321524 
325142 
325124 
325412 
325421 
325241 
325214 
322145 
322154 
322415 
322451 
322541 
322514 
321245 
321254 
321425 
321452 
321542 
321524 
325142 
325124 
325412 
325421 
325241 
325214 
312245 
312254 
312425 
312452 
312542 
312524 
312245 
312254 
312425 
312452 
312542 
312524 
315242 
315224 
315422 
315422 
315242 
315224 
342125 
342152 
342215 
342251 
342521 
342512 
341225 
341252 
341225 
341252 
341522 
341522 
342125 
342152 
342215 
342251 
342521 
342512 
345122 
345122 
345212 
345221 
345221 
345212 
422315 
422513 
423215 
423251 
423125 
423152 
421325 
421523 
425132 
425123 
425213 
425231 
422315 
422513 
423215 
423251 
423125 
423152 
421325 
421523 
425132 
425123 
425213 
425231 
432215 
432251 
432125 
432152 
432512 
432521 
432215 
432251 
432125 
432152 
432512 
432521 
431225 
431252 
431225 
431252 
431522 
431522 
412325 
412523 
413225 
413252 
413225 
413252 
412325 
412523 
415232 
415223 
415223 
415232 
452312 
452321 
452132 
452123 
452213 
452231 
451322 
451322 
451232 
451223 
451223 
451232 
452312 
452321 
452132 
452123 
452213 
452231 
522341 
522314 
522431 
522413 
522143 
522134 
523241 
523214 
523421 
523412 
523142 
523124 
521342 
521324 
521432 
521423 
521243 
521234 
522341 
522314 
522431 
522413 
522143 
522134 
523241 
523214 
523421 
523412 
523142 
523124 
521342 
521324 
521432 
521423 
521243 
521234 
542321 
542312 
542231 
542213 
542123 
542132 
543221 
543212 
543221 
543212 
543122 
543122 
542321 
542312 
542231 
542213 
542123 
542132 
541322 
541322 
541232 
541223 
541223 
541232 
512342 
512324 
512432 
512423 
512243 
512234 
513242 
513224 
513422 
513422 
513242 
513224 
512342 
512324 
512432 
512423 
512243 
512234 
可能的组合数：396 

Answer 7

zhimin8haomi 的代码虽然能解决问题，但是还是有个小小的问题。
用递归法来做全排列组合时,适用于六个数字都不相同的情况。如果这六个数字中有重复的情况，比如有两个2,这时排列出来的组合会有重复的情况。你的结果里就有两个543122。 

Answer 8

第三位不等于4的正则表达式：^..[^4].*
不包含35或53的正则表达式：不知道怎么写的。
综合火龙果@宝家族和zhimin8haomi 的答案，利用递归算法做全排列写出如下代码：import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Test03 
{
    private static final String REGEX = "(?!.*(?:35|53))(?!..4)[0-9]{6}";
    public void getExchange(int[] a,int first,int last)
{
int temp = a[first];
a[first]=a[last];
a[last]=temp;
}
public void change(int[] a, int begin,int end)
{
boolean flag = false;
if(begin==end)
{
          StringBuffer buffer = new StringBuffer();
          for(int i=0;i<a.length;i++)
           buffer.append(a[i]);
          String string = buffer.toString();
          Pattern p = Pattern.compile(REGEX);
          Matcher m = p.matcher(string);
          if(m.find())
          {
           System.out.println(string);
          }
}
else
{
for(int s=0;s<begin;s++)
 if(a[s]==1)
flag=true; 
 for(int j=begin;j<=end;j++)
   {
     getExchange(a,begin,j);  
     change(a,begin+1,end);
     getExchange(a,begin,j);
  }
}
}    public static void main(String[] args) {
int[] a= new int[]{1,2,2,3,4,5};
new Test03().change(a, 0, 5);
}}

Answer 9

上述代码仍然无法解决排列组合中有重复的问题，继续期待高人指点迷津。
感谢火龙果@宝家族，他为大家整理了java正则表达式：http://topic.csdn.net/u/20080306/17/f37a1818-3968-49b4-8f79-e5564486d63e.html。想研究正则表达式的可以看看啊，很好的资料。

Answer 10

        static void Test()
{
char[] c = {'1','2','3','4','5','6'};
Func(c, 0, 5);
int i=0;
for(Iterator<String> it = list.iterator();it.hasNext();)
{
System.out.print(it.next() + "--");
i++;
if(i%10==0)
System.out.println();
}
System.out.println("\nTotal:" + list.size());
}

    static List<String> list = new ArrayList<String>();
    static void Func(char[] n, int beg, int end)
    {
        if (beg == end)
        {
            String result = new String(n);
            if(result.matches(".{2}4.{3}")||result.matches(".*([3][5]|[5][3]).*"))
             return;
            list.add(result);
            return;
        }
        for (int i = beg; i <= end; i++)
        {
            Swap(n, beg, i);
            Func(n, beg + 1, end);
            Swap(n, beg, i);
        }
    }    static void Swap(char[] n, int a, int b)
    {
        char temp = n[a];
        n[a] = n[b];
        n[b] = temp;
    }
123456--123465--123654--123645--125436--125463--125634--125643--126543--126345--
132456--132465--132546--132564--132654--132645--136452--136425--136542--136524--
136254--136245--143256--143265--143652--143625--142365--142563--145236--145263--
145632--145623--146523--146325--152436--152463--152346--152364--152634--152643--
156423--156432--156243--156234--156324--156342--163452--163425--163254--163245--
165432--165423--165234--165243--162543--162345--213456--213465--213654--213645--
215436--215463--215634--215643--216543--216345--231456--231465--231546--231564--
231654--231645--236451--236415--236541--236514--236154--236145--243156--243165--
243651--243615--241365--241563--245136--245163--245631--245613--246513--246315--
251436--251463--251346--251364--251634--251643--256413--256431--256143--256134--
256314--256341--263451--263415--263154--263145--265431--265413--265134--265143--
261543--261345--321456--321465--321546--321564--321654--321645--325416--325461--
325146--325164--325614--325641--326451--326415--326541--326514--326154--326145--
312456--312465--312546--312564--312654--312645--315426--315462--315246--315264--
315624--315642--316452--316425--316542--316524--316254--316245--341256--341265--
341526--341562--341652--341625--342156--342165--342516--342561--342651--342615--
345216--345261--345126--345162--345612--345621--346251--346215--346521--346512--
346152--346125--361452--361425--361542--361524--361254--361245--365412--365421--
365142--365124--365214--365241--362451--362415--362541--362514--362154--362145--
423156--423165--423651--423615--421365--421563--425136--425163--425631--425613--
426513--426315--432156--432165--432516--432561--432651--432615--431256--431265--
431526--431562--431652--431625--436152--436125--436512--436521--436251--436215--
413256--413265--413652--413625--412365--412563--415236--415263--415632--415623--
416523--416325--451326--451362--451236--451263--451623--451632--452136--452163--
452316--452361--452631--452613--456123--456132--456213--456231--456321--456312--
463152--463125--463251--463215--461325--461523--465132--465123--465231--465213--
462513--462315--523416--523461--523146--523164--523614--523641--521436--521463--
521346--521364--521634--521643--526413--526431--526143--526134--526314--526341--
543216--543261--543126--543162--543612--543621--542316--542361--542136--542163--
542613--542631--541236--541263--541326--541362--541632--541623--546213--546231--
546123--546132--546312--546321--513426--513462--513246--513264--513624--513642--
512436--512463--512346--512364--512634--512643--516423--516432--516243--516234--
516324--516342--563412--563421--563142--563124--563214--563241--561432--561423--
561342--561324--561234--561243--562413--562431--562143--562134--562314--562341--
623451--623415--623154--623145--625431--625413--625134--625143--621543--621345--
632451--632415--632541--632514--632154--632145--631452--631425--631542--631524--
631254--631245--643251--643215--643152--643125--642315--642513--645231--645213--
645132--645123--641523--641325--652431--652413--652341--652314--652134--652143--
651423--651432--651243--651234--651324--651342--613452--613425--613254--613245--
615432--615423--615234--615243--612543--612345--
Total:396请问那个能将我那两个正则给连起来啊？就是把两个正则写成一个。

Answer 11

import java.util.regex.*;public class T {
static StringBuilder c = new StringBuilder("122345");
static Matcher m = Pattern.compile("[0-6]{2}[4][0-9]{3}").matcher(c), 
   n = Pattern.compile(".*35|53.*").matcher(c);
static long total = 0;

static void print(int now) {
if(now == 5) {
m.reset();
n.reset();
if(m.find() == false && n.find() == false) {
total++;
System.out.format(c+"\n");
}
return;
}
for(int i=now; i<6; i++) {
if(i == now || c.charAt(i) != c.charAt(now)) {
char tmp = c.charAt(i);
c.setCharAt(i, c.charAt(now));
c.setCharAt(now, tmp);
print(now+1);
tmp = c.charAt(i);
c.setCharAt(i, c.charAt(now));
c.setCharAt(now, tmp);
}
}
}

public static void main(String[] args) {
T.print(0);
System.out.println("total = " + total);
}

}