数组中的元素重新组合问题,高手进

Question

假如我有一个String类型的数组 {"1","2","3","4","5"},我怎么才能得到一个集合(或输出)["12345","1234","1235","1345","2345","123","124","125","234","235","345","12","13","14","15","23","24","25","34","35","45","1","2","3","4","5"];
其中的排列顺序可以随便
一个很大的前提是:这个数组的长度实际上是不确定的,长度可不是5哟,奖励规则
答案必须是代码,不要思路,提醒数组长度不为5
第一个出答案者20分,
最易懂思路的代码20分,
最少代码20分,
可累计.
其余可执行代码平均给分,
相同思路的代码,第一个给分,
5种不同思路的答案==结贴.

Answer 1

写的很挫啊，先贴上来。package com.cn;public class Test1 {
public static void main(String[] args) {
print2(5);//print2(n)
} private static void print(String str,int b, int n, int m) {

for (int i = b; i <=n; i++) {
for (int j = b; j <= n; j++) {
if (j > i) {
System.out.println("\""+ str + i + "" + j + "\"");
}
}
}

}
private static void print2(int m) {

for (int i = 1; i <= m; i++) {
String str = "";
for (int j = 1; j < i; j++)
str = str + j;
print(str,i,m,m);
}
}
}再改进，，

Answer 2

LZ你的要求好像有点苛刻哦  ?
package com.jeelon.sort.sortcomple;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class CompleteSot { private static final int NUM = 5;//根据需要调整要打印出满足条件的数字组合长度，这里是5个数组的组合
/**
 * 全排列
 * @param datas1
 * @param datas2
 */
private static void sort(List<String> datas1, List<String>datas2){
if(datas2.size() == NUM){
for(Object object: datas2){
System.out.print(object);
}
System.out.println();
}

for(int i = 0; i<datas1.size(); i++){
List<String> newDatas1 = new ArrayList<String>(datas1);
List<String> newDatas2 = new ArrayList<String>(datas2);
newDatas2.add(newDatas1.get(i));
newDatas1.remove(i);
sort(newDatas1, newDatas2);
}
}

public static void main(String[] args) {
String []array = new String[]{"1", "2", "3", "4" ,"5"};
sort(Arrays.asList(array), new ArrayList<String>());
}
}

Answer 3

基本原理,利用2进制遍历数组,比如2进制11111就对应12345, 11011对应1245
不多说了,上代码import java.util.ArrayList;public class Permutation
{
private String[] elements;
private ArrayList thePermutation;
public static void main(String[] args)
{
Permutation p=new Permutation(new String[]{"1","2","3","4","5","6","7","8","9","10"});
p.permutateElements();
p.print();
}
public Permutation(String[] elements)
{
this.elements=elements;
thePermutation=new ArrayList();
}
public void permutateElements()
{
for(int i=1;i<Math.pow(2, elements.length);++i)
{
ArrayList<Integer> al=new ArrayList<Integer>();
int s=i;
while(s>0)
{
int index=s%2;
s/=2;
al.add(index);
}
StringBuffer sb=new StringBuffer();
for(int j=0;j<al.size();++j)
{
sb.append(al.get(j)==0?"":elements[j]);
}
thePermutation.add(sb.toString());
}
}
public void print()
{
for(int i=0;i<thePermutation.size();++i)
{
System.out.print(i==0?thePermutation.get(i):","+thePermutation.get(i));
}
System.out.println();
}
}6个元素数组的输出为
1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234,5,15,25,125,35,135,235,1235,45,145,245,1245,345,1345,2345,12345,6,16,26,126,36,136,236,1236,46,146,246,1246,346,1346,2346,12346,56,156,256,1256,356,1356,2356,12356,456,1456,2456,12456,3456,13456,23456,123456

Answer 4

找不到帖子，现写一个，非递归的，稍候再改进
import java.util.*;class Combine {
    public static void main(String[] args) {
        String[] a = {"1", "2", "3", "4", "5"};
        List<String> list = new ArrayList<String>();
        for (int i=a.length; i>0; i--) {
            list.addAll(combine(a, i));
        }
        System.out.println(list);
    }
    
    public static List<String> combine(String[] a, int n) {
        if (n > a.length) {n = a.length;}
        if (n < 1) {return new ArrayList<String>();}
        
        int[] idx = new int[a.length];
        for (int i=0; i<idx.length; i++) {
            if (i<a.length-n) {idx[i] = 0;}
            else {idx[i] = 1;}
        }
        
        int cnt, m;
        List<String> result = new ArrayList<String>();
        while (true) {
            cnt = 0;
            m = 0;
            for (int i=0; i<idx.length; i++) {
                if (idx[i]==1) {
                    cnt++;
                    if (i<n) {m++;}
                }
            }
            
            if (cnt == n) {
                StringBuilder buf = new StringBuilder();
                for (int i=0; i<idx.length; i++) {
                    if (idx[i]==1) {buf.append(a[i]);}
                }
                result.add(0, buf.toString());
            }
            
            if (m==n) {break;}
            
            idx[idx.length-1]++;
            for (int i=idx.length-1; i>0; i--) {
                if (idx[i] == 2) {
                    idx[i] = 0;
                    idx[i-1]++;
                } else {break;}
            }
            
        }
        
        return result;
    }
}

Answer 5

可以构造一棵树，以5个为例：构造完后打印出根节点到各个末节点的路劲，上图还只是打印出结点1到其它结点的可能，以相同的方式构造以2、3、4、5为根的树
以下是我写的程序：import java.util.*;public class BiTree 
{
public static ArrayList<BiTreeNode> list = new ArrayList<BiTreeNode>(); //用于保留访问路径

public static void main(String[] args)
{
BiTreeNode root;
String[] strings = {"1", "2", "3", "4", "5", "6", "7", "8", "9"};

Arrays.sort(strings); //先排序，确保顺序唯一
for (int i = 0; i < strings.length; i++)
{
root = new BiTreeNode(strings, strings[i]); //每一个数字都做一次根节点
print(root); //打印该根节点所能组成的可能性
}
}

public static void print(BiTreeNode root)
{
list.add(root); //将根节点加到访问路径中
for (int i = 0; i < root.children.size(); i++)
{
print(root.children.get(i)); //遍历该根节点的子节点
}

StringBuilder str = new StringBuilder();
for (int i = 0; i < list.size(); i++)
{
str.append(list.get(i).data); //保存访问路径到字符串
}
System.out.println(str); //打印该条访问路径

list.remove(list.size() - 1); //移除根节点
}
}class BiTreeNode
{
public ArrayList<BiTreeNode> children = new ArrayList<BiTreeNode>(); //用于保存子节点
public String data; //保存当前节点数据

public BiTreeNode(String[] args, String s) //递归构造树
{
data = s;
int p = Arrays.binarySearch(args, s);
for (int i = p + 1; i < args.length; i++)
{
children.add(new BiTreeNode(args, args[i]));
}
}
}

Answer 6

再来个递归的吧
import java.util.*;class Combine {
    public static void main(String[] args) {
        String[] a = {"1", "2", "3", "4", "5"};
        List<String> list = new ArrayList<String>();
        for (int i=a.length; i>0; i--) {
            list.addAll(combine2(a, i));
        }
        System.out.println(list);
    }
    
    public static List<String> combine2(String[] a, int n) {
        if (n > a.length) {n = a.length;}
        if (n < 1) {return new ArrayList<String>();}
        
        List<String> result = new ArrayList<String>();
        if (n == a.length) {
            StringBuilder buf = new StringBuilder();
            for (int i=0; i<a.length; i++) {
                buf.append(a[i]);
            }
            result.add(buf.toString());
            return result;
        } else if (n == 1) {
            for (int i=0; i<a.length; i++) {
                result.add(a[i]);
            }
            return result;
        }        for (int i=0; i<a.length; i++) {
            String[] tmp = Arrays.copyOfRange(a, i+1, a.length);
            if (tmp.length >= n-1) {
                List<String> list = combine2(tmp, n-1);
                for (String s : list) {
                    result.add(a[i] + s);
                }
            }
        }        return result;
    }
}

Answer 7

package com.cn;import java.util.ArrayList;
import java.util.List;
/**
 * 借用别人的基本原理：基本原理,利用2进制遍历数组,比如2进制11111就对应12345, 11011对应1245
 * @author Administrator
 *
 */
public class Redemption {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list = combine(5);
System.out.println(list);
}
public static List<String> combine(int n) {
List<String> list = new ArrayList<String>();
int[] i = new int[n];
int[] m = new int[n];
//i全部初始为0,m初始为1,2,3,4......
for (int j = 0; j < i.length; j++) {
i[j] = 0;
m[j] = j+1;
}
int index = 1;
//得到总个数 如： 00001---11111
for (int j = 0; j < n; j ++) {
index *= 2;
}

/**
 * 每次在二进制数的基础上+1，然后得到一个结果
 */
for (int j = 0; j < index - 1; j++) {
forward(n,i);
StringBuffer sb = new StringBuffer();
for (int u = 0; u < n; u++) {
if (i[u] == 1) {
sb.append(m[u]);
}
}
list.add(sb.toString());
}
return list;
}

/**
 * 模拟二进制的+1
 * @param n
 * @param m
 */
public static void forward(int n, int[] m) {
if (n > 0 && m[n - 1] == 1 ) {
m[n -1 ] = 0;
forward(n-1,m);
}
else {
if(n > 0)
m[n - 1]  = 1;
for(int i = 0; i < m.length; i++)
System.out.print(m[i]);
System.out.println();
return;
}

}
}
看的别人的算法，，

Answer 8

再来一个，和之前的非递归差不多，只是之前的是分次取出组合，这个是一次取得全组合import java.util.*;class Combine {
    public static void main(String[] args) {
        String[] a = {"1", "2", "3", "4", "5"};
        List<String> list = combine(a);
        System.out.println(list);
    }
    
    public static List<String> combine(String[] a) {
        if (a.length < 1) {
            return new ArrayList<String>();
        }
        
        int[] idx = new int[a.length];
        Arrays.fill(idx, 0);
        idx[idx.length-1] = 1;
        List<List<String>> list = new ArrayList<List<String>>();
        for (int i=0; i<a.length; i++) {
            list.add(new ArrayList<String>());
        }
        
        int cnt;
        while (idx[0] < 2) {
            cnt = 0;
            StringBuilder buf = new StringBuilder();
            for (int i=0; i<idx.length; i++) {
                if (idx[i]==1) {
                    cnt++;
                    buf.append(a[i]);
                }
            }
            if (cnt > 0) {
                list.get(cnt-1).add(0, buf.toString());
            }
            
            idx[idx.length-1]++;
            for (int i=idx.length-1; i>0; i--) {
                if (idx[i] == 2) {
                    idx[i] = 0;
                    idx[i-1]++;
                } else {break;}
            }
            
        }
        
        List<String> result = new ArrayList<String>();
        for (int i=list.size()-1; i>=0; i--) {
            result.addAll(list.get(i));
        }
        
        return result;
    }
}

Answer 9

public static ArrayList<ArrayList<String>> c(String[] ss) {
int n=ss.length;
ArrayList<ArrayList<String>> r = new ArrayList<ArrayList<String>>();
int x = (int)Math.pow(2, n);
for (int i=0; i<x; i++) {
ArrayList<String> l = new ArrayList<String>();
for (int j=0; j<n; j++)
if ((x>>>j&1)==1) l.add(ss[j]);
r.add(l);
}
return r;
}

Answer 10

 r.add(l); or r.addAll(l)???

Answer 11

是r.add(l)没错，不过我倒发现了一个粗心的错误，该用i位移而不是x
修正一下    public static ArrayList<ArrayList<String>> c(String[] ss) {
        int n=ss.length;
        ArrayList<ArrayList<String>> r = new ArrayList<ArrayList<String>>();
        int x = (int)Math.pow(2, n);
        for (int i=1; i<x; i++) { //从1开始循环意味着不要空集合
            ArrayList<String> l = new ArrayList<String>();
            for (int j=0; j<n; j++)
                if ((i>>>j&1)==1) l.add(ss[j]); //此处修正
            r.add(l);
        }
        return r;
    }

Answer 12

贴个我的，递归，没考虑优化
  public static void main(String[] args) throws Exception {
    String[] array = new String[] {
        "1", "2", "3", "4", "5", "6"
    };    System.out.println(find(array, "", 0));
  }  static List<String> find(String[] array, String prefix, int start) {
    if (start >= array.length) {
      return Collections.emptyList();
    }
    List<String> list = new LinkedList<String>();
    for (int i = start; i < array.length; i++) {
      String str = prefix + array[i];
      list.add(str);
      list.addAll(find(array, str, i + 1));
    }
    return list;
  }

Answer 13

可以解释一下这句吗？(i >>> j & 1)

Answer 14

为什么别人的处理我看不懂呢，，for (int i=1; i<x; i++) { //从1开始循环意味着不要空集合
            ArrayList<String> l = new ArrayList<String>();
            for (int j=0; j<n; j++)
                if ((i>>>j&1)==1) l.add(ss[j]); //此处修正
            r.add(l);
        }
这一段是怎么保证每一个都不重复的。再山寨一个容易懂的写法：package com.cn;import java.util.ArrayList;
import java.util.List;public class Test {
public static void main(String[] args) {
String[] s = {"1","2","3","4","5"};
List<String> list = combine(s);
System.out.println(list); }
public static List<String> combine(String[] s) {
List<String> list = new ArrayList<String>();
int m = s.length;
int n = (int) Math.pow(2, m);
                //依次增加，然后取出每一位看看是1，还是0。
for(int i = 1; i < n; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < m; j++) {
int l = i & (int)Math.pow(2, j);
if ((l>>>j) == 1) {
sb.append(s[j]);
}
}
list.add(sb.toString());
}
return list;
}
}