JAVA用1、2、2、3、4、5排列组合，最多能排列多少组合并打印出来。要求：4不能放在第三位，4和5不能相连

例如：225341、135224等等，用JAVA编程，思路是怎么样的，谢谢啦

推荐答案 2012-06-19

算法程序题：

该公司笔试题就1个，要求在10分钟内作完。

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

static int[] bits = new int[] { 1, 2, 3, 4, 5 };

/**
* @param args
*/
public static void main(String[] args) {
sort("", bits);
}

private static void sort(String prefix, int[] a) {
if (a.length == 1) {
System.out.println(prefix + a[0]);
}

for (int i = 0; i < a.length; i++) {
sort(prefix + a[i], copy(a, i));
}
}

private static int[] copy(int[] a,int index){
int[] b = new int[a.length-1];
System.arraycopy(a, 0, b, 0, index);
System.arraycopy(a, index+1, b, index, a.length-index-1);
return b;
}

**********************************************************************

基本思路：
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;
}
}

温馨提示：答案为网友推荐，仅供参考

当前网址：http://33.wendadaohang.com/zd/h4505W5cd.html

其他回答

第1个回答 2012-06-19

public class Test01 {

private int total = 0;
private ArrayList<String> arrangeList = new ArrayList<String>();
// public static void main(String[] args) {
// int sum = 0;
// for (int i = 1; i <= 100; i++) {
// if(i%2!=0){
// sum+=i;
// }
// }
// System.out.println(sum);
// }
public static void main(String[] args) {
String list[] = { "1", "2", "2", "4", "5" };
Test01 ts = new Test01();
ts.perm(list, 0, list.length-1);
for (int i = 0; i < ts.getArrangeList().size(); i++) {
System.out.println(ts.getArrangeList().get(i));
}
System.out.println("total:" + ts.total);
}

private ArrayList<String> getArrangeList() {
return arrangeList;
}

private void perm(String[] list, int k, int m) {
// TODO Auto-generated method stub
if (k > m) {
StringBuffer sb = new StringBuffer();
if(list[2]!="4" && !(list[0]=="4" && list[1]=="5") && !(list[3]=="4" && list[4]=="5")){
for (int i = 0; i <= m; i++) {

sb.append(list[i]).append(",");

}
if (sb.length()>0) {
sb.setLength(sb.length()-1);
}
arrangeList.add(sb.toString());
total++;
}
} else {
for (int i = k; i <= m; i++) {
swap(list, k, i);
perm(list, k + 1, m);
swap(list, k, i);
}
}
}

private void swap(String[] list, int k, int i) {
// TODO Auto-generated method stub
String c3 = list[k];
list[k] = list[i];
list[i] = c3;
}
}
运行结果：
1,2,2,5,4
1,2,5,4,2
1,2,5,2,4
1,2,2,5,4
1,2,5,4,2
1,2,5,2,4
1,4,2,2,5
1,4,2,5,2
1,4,2,2,5
1,4,2,5,2
1,4,5,2,2
1,4,5,2,2
1,5,2,4,2
1,5,2,2,4
1,5,2,4,2
1,5,2,2,4
2,1,2,5,4
2,1,5,4,2
2,1,5,2,4
2,2,1,5,4
2,2,5,4,1
2,2,5,1,4
2,4,2,1,5
2,4,2,5,1
2,4,1,2,5
2,4,1,5,2
2,4,5,1,2
2,4,5,2,1
2,5,2,4,1
2,5,2,1,4
2,5,1,4,2
2,5,1,2,4
2,2,1,5,4
2,2,5,4,1
2,2,5,1,4
2,1,2,5,4
2,1,5,4,2
2,1,5,2,4
2,4,1,2,5
2,4,1,5,2
2,4,2,1,5
2,4,2,5,1
2,4,5,2,1
2,4,5,1,2
2,5,1,4,2
2,5,1,2,4
2,5,2,4,1
2,5,2,1,4
4,2,2,1,5
4,2,2,5,1
4,2,1,2,5
4,2,1,5,2
4,2,5,1,2
4,2,5,2,1
4,2,2,1,5
4,2,2,5,1
4,2,1,2,5
4,2,1,5,2
4,2,5,1,2
4,2,5,2,1
4,1,2,2,5
4,1,2,5,2
4,1,2,2,5
4,1,2,5,2
4,1,5,2,2
4,1,5,2,2
5,2,2,4,1
5,2,2,1,4
5,2,1,4,2
5,2,1,2,4
5,2,2,4,1
5,2,2,1,4
5,2,1,4,2
5,2,1,2,4
5,4,2,2,1
5,4,2,1,2
5,4,2,2,1
5,4,2,1,2
5,4,1,2,2
5,4,1,2,2
5,1,2,4,2
5,1,2,2,4
5,1,2,4,2
5,1,2,2,4
total:84
速度给分，速度采纳
少了个3，自己加进去追问

思路呢？

追答

采纳后给思路，不解释

第2个回答 2017-08-19

/**
* 1,2,2,3,4,5  4不能在第三位,3和5不能相链
* @author 小伟
*/
public class Demo1 {
  public static void main(String[] args) {
        char[] s = {'1','2','2','3','4','5'};
          permutation(s, 0, 5);
  }
    private static void printInfo(char[] a) {
        String s = "";
        for (int i = 0; i < a.length; i++) {
            s+=a[i]+"";
        }
        String regex = "[1-5]{2}[1235][1-5]{3}";
        boolean result = s.matches(regex);
        if (result) {
            if (!(s.contains("35")||s.contains("53"))) {
                System.out.println(s);
            }
        }
    }
    public static void permutation(char[] s,int from,int to) {
        if(to <= 1)
            return;
        if(from == to) {
            printInfo(s);
        } else {
            for(int i=from; i<=to; i++) {
                swap(s,i,from); //交换前缀，使其产生下一个前缀
                permutation(s, from+1, to);
                swap(s,from,i); //将前缀换回，继续做上一个前缀的排列
            }
        }
    }
    public static void swap(char[] s,int i,int j) {
    char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

第3个回答 2012-06-19

循环遍历122345-543221 符合条件的打印
public static void main(String[] args) {
// TODO Auto-generated method stub
int su[]={1,2,2,3,4,5};
for(int i=122345;i<543221;i++){
char s[]=new Integer(i).toString().toCharArray();
int s1=0;int s2=0;int s3=0;int s4=0;int s5=0;boolean flag=true;
for(int j=0;j<s.length;j++){
if(s[j]=='1'){s1++;}
if(s[j]=='2'){s2++;}
if(s[j]=='3'){s3++;}
if(s[j]=='4'){s4++;}
if(s[j]=='5'){s5++;}
if(j!=s.length-1)
{
if(s[j]=='3'&&s[j+1]=='5'||s[j]=='5'&&s[j+1]=='3'){
flag=false;
}

}
}
if(s[2]=='4'){
flag=false;
}
if(s1==1&&s2==2&&s3==1&&s4==1&&s5==1&&flag){
System.out.println(i);
}
}

}
122345
122543
123245
123254
123425
123452
125234
125243
125423
125432
132245
132254
132425
132452
132524
132542
142325
142523
143225
143252
145223
145232
152234
152243
152324
152342
152423
152432
212345
212543
213245
213254
213425
213452
215234
215243
215423
215432
221345
221543
223145
223154
223415
223451
225134
225143
225413
225431
231245
231254
231425
231452
231524
231542
232145
232154
232415
232451
232514
232541
241325
241523
242315
242513
243125
243152
243215
243251
245123
245132
245213
245231
251234
251243
251324
251342
251423
251432
252134
252143
252314
252341
252413
252431
312245
312254
312425
312452
312524
312542
315224
315242
315422
321245
321254
321425
321452
321524
321542
322145
322154
322415
322451
322514
322541
325124
325142
325214
325241
325412
325421
341225
341252
341522
342125
342152
342215
342251
342512
342521
345122
345212
345221
412325
412523
413225
413252
415223
415232
421325
421523
422315
422513
423125
423152
423215
423251
425123
425132
425213
425231
431225
431252
431522
432125
432152
432215
432251
432512
432521
451223
451232
451322
452123
452132
452213
452231
452312
452321
512234
512243
512324
512342
512423
512432
513224
513242
513422
521234
521243
521324
521342
521423
521432
522134
522143
522314
522341
522413
522431
523124
523142
523214
523241
523412
523421
541223
541232
541322
542123
542132
542213
542231
542312
542321
543122
543212

第4个回答 2012-06-19

public class PermutationAlgo {
private int count = 0;

public void calculate(){
String eleStr = "122345";
depthSearch(eleStr, "");
System.out.println("符合条件的总结果数为:"+count+"条");
}

/**
* @param eleStr - 待分配字符组成的串
* @param rstStr - 已分配字符组成的串
*/
public void depthSearch(String eleStr, String rstStr) {
if (eleStr.length() == 0) {
count++;
System.out.println(rstStr);
return;
}
for (int i = 0; i < eleStr.length(); i++) {
String currEle = eleStr.substring(i, i + 1); //取出当前位的值
if (rstStr.length() == 2 && "4".equals(currEle)) continue; //剪掉第三位为4的分支
if (rstStr.endsWith("3") && "5".equals(currEle)) continue; //剪掉"35"相连的分支
if (rstStr.endsWith("5") && "3".equals(currEle)) continue; //剪掉"53"相连的分支
if (eleStr.substring(0, i).indexOf(currEle) != -1) continue; //剪掉同一位上字符重复的分支(此题即剪掉重复的2)
depthSearch(eleStr.substring(0, i) + eleStr.substring(i + 1), rstStr + currEle); //用剩余的合法串继续递归
}
}

public static void main(String[] args) {
new PermutationAlgo().calculate();
}
}

1 2 下一页

相似回答

...函数打印出所有的排序。要求4不能在第三位,3与5不能相连答：String temp = str + rest.substring(i, i + 1);if (temp.indexOf("4") != 2 && temp.indexOf("35") == -1 && temp.indexOf("53") == -1) {// 过滤显示条件,如果去掉此处的判断，就是列出所有字符集的排列组合 if (temp.length() > 4) { System.out.println(temp);if (!

java排列组合算法?答：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不...

怎样将几个数字进行组合排列答：要把他组成4个为一组如下:1,2,3,4|1,2,... 有几个数字,个数不等,从5个到100个左右,要将他们组合,4个数为一组,且不重复,比如:有5个数字,1,2,3,4,5。要把他组成4个为一组如下:1,2,3,4|1,2,3,5|1,2,4,5|2,3,4,5|2,3,4,1|2,3,5,1|3,4,5,1|3,4,5,2|3,4,5,1 ...

大家正在搜

a52排列组合等于多少单双最多能连多少排列组合c(5,2)怎么算 4选2排列组合 c42排列组合公式 c和a排列组合最多能得多少分借呗最多能借多少期借呗最多能借多少次