高手才进来：求一个复杂算法

例如 int i[]={1,2,3,4,5,6};能不能在屏幕上打印出以整形数组i中的4个数为一组，所有可能出现的组合，每个组合中都不能有重复的数字例如  1,2,3,4
4,3,2,1
2,3,4,1
3,1,4,5
5,4,1,3
5,6,1,2...........把所有可能的组合都打印出来这样的不打印，因为有重复数字
5,5,2,3
2,2,6,5这个算法应该怎么写呢?
如果能写出一个通用的函数，就最好了，例如private static void showAllPossibilities(int i,int[] numberScale);
{
   .............;
}
public static void main(String args[])
{
  int numberScale[]={1,2,3,4,5,6};
  showAllPossibilities(4,numberScale);  //打印所有以4个数为一组的组合.
}谢谢。

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

public static void main(String[] args) {
// 整形数组i中的4个数为一组，
//所有可能出现的组合，每个组合中都不能有重复的数字
int csdn[]={1,2,3,4,5,6};
int i,j,k,l;
for ( i = 1; i < csdn.length+1; i++) {
for ( j = 1; j < i; j++) {
for (k = 1; k < j; k++) {
for ( l = 1; l < k; l++) {
System.out.println(i+","+j+","+k+","+l);
}
}
}
}
}
刚回答了一个类似的问题，只需要改变改算法中的numbers和index数组就可以达到你的要求。
import java.util.Set;
import java.util.TreeSet;/**
*
*
*
* @author jinxfei
*
*/
public class Test {

static int[] numbers=new int[]{1,2,3,4,5,6};
static int[] indexs=new int[]{0,0,0,0};

public static void main(String[] args) throws Exception{
while(!indexOverflow()){
if (!hasDuplicate()){
String str=getCurComposite();
System.out.println("合法组合:"+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 hasDuplicate(){
Set set=new TreeSet();
for(int i=0; i<indexs.length;i++){
set.add(numbers[indexs[i]]);
}
return set.size()!=indexs.length;
}

//判断是否所有的可能性都已经尝试完毕
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;
}
}
N多年前写过排列组合，隐约还有点印象
写一个试试看，没环境没能调试private static int[][] getPa(int[] a, int n) { //排列，如a={1，2，3}， n=2，从a中取出2个数字进行排列，即12，13，21，23，31，32
    if (n == 1) {
        int[][] b = new int[a.length][1];
        for (int i=0; i<a.length; i++) {
            b[i][0] = a[i];
            return b;
        }
    }
    int[][] c = new int[0][n];
    int[] sub = new int[a.length-1];
    for (int i=0; i<a.length; i++) {
        for (int j=0, k=0; j<a.length; j++) {
            if (i != j) {
                sub[k++] = a[j];
            }
        }
        int[][] t = getPa(sub, n-1);
        int[][] b = c;
        c = new int[t.length+b.length][n];
        for (int j=0; j<b.length; j++) {
            System.arraycopy(b[j], 0, c[0], 0, n);
        }
        for (int j=0; j<t.length; j++) {
            System.arraycopy(t[j], 0, c[b.length+j], 1, n-1);
            c[b.length+j][0] = a[i];
        }
    }
    return c;
}private static void showAllPossibilities(int i,int[] numberScale) {
    int[][] c = getPa(numberScale, i);
    for (int j=0; j<c.length; j++) {
        for (int k=0; k<i-1; k++) {
            System.out.printf("%d,", c[j][k]);
        }
        System.out.printf("%d\n", c[j][i-1]);
    }
}
写了一个递归版本的，可以灵活设置打印的长度.C#版OK,没有java环境，java版未测        static void Main(string[] args)
        {
            int[] csdn = { 1, 2, 3, 4};
            for (int index = 0; index < csdn.Length; index++)
                Print(csdn, index, 3, new List<int>() { csdn[index] });
        }        static void Print(int[] csdn, int index, int count, List<int> added)
        {
            if (count <= 1)
            {
                foreach (int n in added) Console.Write(n + "\t");
                Console.WriteLine();
                return;
            }
            for (int i = 0; i < csdn.Length; i++)
            {
                if (i != index && !added.Contains(csdn[i]))
                {
                    List<int> added2 = added.ToList();
                    added2.Add(csdn[i]);
                    Print(csdn, i, count - 1, added2);
                }
            }
        }        static void main(string[] args)  {
            int[] csdn = { 1, 2, 3, 4};
            for (int index = 0; index < csdn.length; index++){
                ArrayList<int> list = new ArrayList<int>();
                list.add(csdn[index]);
                print(csdn, index, 3, list);
            }
        }        static void print(int[] csdn, int index, int count, ArrayList<int> added)
        {
            if (count <= 1)
            {
                for (int j=0;j<added.size();j++) System.out.print(added.get(j) + "\t");
                System.out.println();
                return;
            }
            for (int i = 0; i < csdn.length; i++)
            {
                if (i != index && !added.contains(csdn[i]))
                {
                    ArrayList<int> added2 = (ArrayList<int>)added.clone();
                    added2.Add(csdn[i]);
                    print(csdn, i, count - 1, added2);
                }
            }
        }输出
1       2       3
1       2       4
1       3       2
1       3       4
1       4       2
1       4       3
2       1       3
2       1       4
2       3       1
2       3       4
2       4       1
2       4       3
3       1       2
3       1       4
3       2       1
3       2       4
3       4       1
3       4       2
4       1       2
4       1       3
4       2       1
4       2       3
4       3       1
4       3       2
应该是有P6,4 = 6*5*4*3 =360种可能。思路就是先取出不重复的4个数字，再全排列。public class AllSort{
static int count = 0;    public static void main(String[] args) {
        char[] buf = {'1', '2', '3', '4', '5', '6'};
        char[] temp = new char[4];

        for(int i=0; i<buf.length; i++)
         for (int j=0; buf[j] < buf[i]; j++)
         for (int k=0; buf[k] < buf[j]; k++)
         for (int l=0; buf[l] < buf[k]; l++){
         temp[0] = buf[i];
         temp[1] = buf[j];
         temp[2] = buf[k];
         temp[3] = buf[l];
         perm(temp,0,temp.length-1);
         }
        System.out.println("In total: "+ count);
    }
    public static void perm(char[] buf, int start, int end){
        if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
            for(int i=0;i<=end;i++){
                System.out.print(buf[i]);
            }
            count ++;
            System.out.println();
        }
        else{//多个字母全排列
            for(int i=start;i<=end;i++){
                char temp=buf[start];//交换数组第一个元素与后续的元素
                buf[start]=buf[i];
                buf[i]=temp;

                perm(buf,start+1,end);//后续元素递归全排列

                temp=buf[start];//将交换后的数组还原
                buf[start]=buf[i];
                buf[i]=temp;
            }
        }
    }
}
谢谢您的代码，但是，如果数字不是一位，而是两位的，你就算法就失效了例如 char[] buf = {'1', '21', '63', '4', '55', '6'};
Integer[] num = {1,2,3,4,5,6};
Collections.shuffle(Arrays.asList(num),new Random());
System.out.println(Arrays.toString(num).substring(1, 11));
一楼的好像不对唉，他是基于顺序数的前提啊，
如果数组是int csdn[]={1,2,3,4,5,6,6};打印就不对了
package com.syj.csdn;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/**
* <p>
* Title:全排列算法
* </p>
*
* <p>
* Copyright: http://blog.csdn.net/sunyujia/archive/2009/04/26/4124011.aspx
* </p>
*
* @author 孙钰佳
* @main [email protected]
* @date 2009-04-25 23:57:23 PM
*/
public class FullSort {
    //将NUM设置为待排列数组的长度即实现全排列
    private static int NUM = 3;    /**
     * 递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列
     *
     * @param datas
     * @param target
     */
    private static void sort(List datas, List target) {
        if (target.size() == NUM) {
            for (Object obj : target)
                System.out.print(obj);
            System.out.println();
            return;
        }
        for (int i = 0; i < datas.size(); i++) {
            List newDatas = new ArrayList(datas);
            List newTarget = new ArrayList(target);
            newTarget.add(newDatas.get(i));
            newDatas.remove(i);
            sort(newDatas, newTarget);
        }
    }    public static void main(String[] args) {
        String[] datas = new String[] { "a", "b", "c", "d" };
        sort(Arrays.asList(datas), new ArrayList());
    }}
我这个是基于对象来写的，不管是int还是string，或者是object 都一样。与待排序目标对象类型内容无关唯一的前提就是给定的数组中不能有重复，如果要求给定的数组中忽略重复的话，只要在这个算法前面写个排除重复的算法就可以了。
从你给出的例子可以看出你给定的数组是没有重复数据的。楼主可以试试有没有bug，我刚刚写完，没一会，中间还吃了顿饭。^_^
修改2楼代码public static void fullSort(int...num){
    int i,j,k,l;
    int len = num.length+1;
    for(i=1;i<=len;i++){
      for(j=1;j<len;j++){
     for(k=1;k<len;k++){
        for(l=1;l<len;l++){
     if(i==j||i==k||i==l||j==k||j==l||k==l)
     continue;
     System.out.printf("%d%d%d%d\n",i,j,k,l);
     }
     }
     }
    }
}result：
1234
1235
1236
1243
1245
1246
1253
1254
1256
1263
1264
1265
1324
1325
1326
1342
1345
1346
1352
1354
1356
1362
1364
1365
1423
1425
1426
1432
1435
1436
1452
1453
1456
1462
1463
1465
1523
1524
1526
1532
1534
1536
1542
1543
1546
1562
1563
1564
1623
1624
1625
1632
1634
1635
1642
1643
1645
1652
1653
1654
2134
2135
2136
2143
2145
2146
2153
2154
2156
2163
2164
2165
2314
2315
2316
2341
2345
2346
2351
2354
2356
2361
2364
2365
2413
2415
2416
2431
2435
2436
2451
2453
2456
2461
2463
2465
2513
2514
2516
2531
2534
2536
2541
2543
2546
2561
2563
2564
2613
2614
2615
2631
2634
2635
2641
2643
2645
2651
2653
2654
3124
3125
3126
3142
3145
3146
3152
3154
3156
3162
3164
3165
3214
3215
3216
3241
3245
3246
3251
3254
3256
3261
3264
3265
3412
3415
3416
3421
3425
3426
3451
3452
3456
3461
3462
3465
3512
3514
3516
3521
3524
3526
3541
3542
3546
3561
3562
3564
3612
3614
3615
3621
3624
3625
3641
3642
3645
3651
3652
3654
4123
4125
4126
4132
4135
4136
4152
4153
4156
4162
4163
4165
4213
4215
4216
4231
4235
4236
4251
4253
4256
4261
4263
4265
4312
4315
4316
4321
4325
4326
4351
4352
4356
4361
4362
4365
4512
4513
4516
4521
4523
4526
4531
4532
4536
4561
4562
4563
4612
4613
4615
4621
4623
4625
4631
4632
4635
4651
4652
4653
5123
5124
5126
5132
5134
5136
5142
5143
5146
5162
5163
5164
5213
5214
5216
5231
5234
5236
5241
5243
5246
5261
5263
5264
5312
5314
5316
5321
5324
5326
5341
5342
5346
5361
5362
5364
5412
5413
5416
5421
5423
5426
5431
5432
5436
5461
5462
5463
5612
5613
5614
5621
5623
5624
5631
5632
5634
5641
5642
5643
6123
6124
6125
6132
6134
6135
6142
6143
6145
6152
6153
6154
6213
6214
6215
6231
6234
6235
6241
6243
6245
6251
6253
6254
6312
6314
6315
6321
6324
6325
6341
6342
6345
6351
6352
6354
6412
6413
6415
6421
6423
6425
6431
6432
6435
6451
6452
6453
6512
6513
6514
6521
6523
6524
6531
6532
6534
6541
6542
6543
7123
7124
7125
7126
7132
7134
7135
7136
7142
7143
7145
7146
7152
7153
7154
7156
7162
7163
7164
7165
7213
7214
7215
7216
7231
7234
7235
7236
7241
7243
7245
7246
7251
7253
7254
7256
7261
7263
7264
7265
7312
7314
7315
7316
7321
7324
7325
7326
7341
7342
7345
7346
7351
7352
7354
7356
7361
7362
7364
7365
7412
7413
7415
7416
7421
7423
7425
7426
7431
7432
7435
7436
7451
7452
7453
7456
7461
7462
7463
7465
7512
7513
7514
7516
7521
7523
7524
7526
7531
7532
7534
7536
7541
7542
7543
7546
7561
7562
7563
7564
7612
7613
7614
7615
7621
7623
7624
7625
7631
7632
7634
7635
7641
7642
7643
7645
7651
7652
7653
7654
public static void fullSort(int...num){
     int i,j,k,l;
     int len = num.length;
     for(i=1;i<=len;i++){
     for(j=1;j<=len;j++){
     for(k=1;k<=len;k++){
     for(l=1;l<=len;l++){
     if(i==j||i==k||i==l||j==k||j==l||k==l)
     continue;
     System.out.printf("%d%d%d%d\n",i,j,k,l);
     }
     }
     }
     }
     }
MathUtils.fullSort(1,2,3,4,5,6);
最笨最简单的方法：
public class test{
public static void main(String[]lsg){
int i[]={1,2,3,4,5,6};
for(int k1 = 0; k1 < i.length; k1++){
for(int k2 = 0; k2 < i.length; k2++){
for(int k3 = 0; k3 < i.length; k3++){
for(int k4 = 0; k4 < i.length; k4++){
if(k1!=k2&&k1!=k3&&k1!=k4&&k2!=k3&&k2!=k4&&k3!=k4){
System.out.println(i[k1]+","+i[k2]+","+i[k3]+","+i[k4]);
}
}
}
}

}
}
}
这是效率最好，而且代码量最少的public class test {
int i[] = { 1, 2, 3, 4, 5, 6 };
int result[] = new int[4]; public test() {
for (int k = 0; k < i.length; k++) {
result[0] = i[k];
getE(k, k, i.length, 4);
} } public void getE(int start, int firstIndex, int length, int n) {
for (int k = (start + 1) % length; k != firstIndex; k = (k + 1)% length) {
result[5 - n] = i[k];
if ((n - 1) != 1) {
getE(k, firstIndex, i.length, n - 1);
} else {
System.out.println(result[0] + "," + result[1] + ","+ result[2] + "," + result[3]);
} }
} public static void main(String[] lsg) { new test(); }
}
我上面的代码是下面代码和下面代是等价的
public class test{
public static void main(String[]lsg){
int i[]={1,2,3,4,5,6};
for(int k1 = 0; k1 < i.length; k1++){
for(int k2 = (k1 + 1) % i.length; k2 != k1 ; k2 = (k2 + 1) % i.length){
for(int k3 = (k2 + 1) % i.length; k3 != k1; k3 = (k3 + 1) % i.length){
for(int k4 = (k3 + 1) % i.length; k4 != k1; k4 = (k4 + 1) % i.length){
System.out.println(i[k1]+","+i[k2]+","+i[k3]+","+i[k4]);
}
}
}
}
}
}
用了递归，怎么可能是效率最高。组合数学的经典问题了，有现成的算法，google一下就可以了。

高手才进来： 求一个复杂算法

解决方案 »

高手才进来：求一个复杂算法