数组中所有数字的（顺序不一样也是一种）任意组合

假设我现在有一个数组int a[3]={1,2,3},那么他的组合就有以下几种，
1:{1,2,3}
2:{1,3,2}
3:{2,1,3}
4:{2,3,1}
5:{3,1,2}
6:{3,2,1}
我想要4个数字，但是4个种类太多，就举个例子，希望大家帮想想

9 个解决方案

#1

想要代码还是？

#2

 

引用 1 楼 shawncpp 的回复:

想要代码还是？

代码。。。  我试过很多次了 都卡住了  求助啊

#3

import java.util.ArrayList;
import java.util.List;

public class Test {

	static List<int[]> allSorts = new ArrayList<int[]>();
    
    public static void permutation(int[] nums, int start, int end) {
        if (start == end) {
            int[] newNums = new int[nums.length]; 
            for (int i=0; i<=end; i++) {
                newNums[i] = nums[i];
            }
            allSorts.add(newNums); 
        } else {
            for (int i=start; i<=end; i++) {
                int temp = nums[start];
                nums[start] = nums[i];
                nums[i] = temp;
                permutation(nums, start + 1, end); 
                nums[i] = nums[start];
                nums[start] = temp;
            }
        }
    }
        
    public static void main(String[] args) {
        int[] numArray = {1, 2, 3, 4};
        permutation(numArray, 0, numArray.length - 1);
        int[][] a = new int[allSorts.size()][]; 
        allSorts.toArray(a);
            

        for (int i=0; i<a.length; i++) {
            int[] nums = a[i];
            for (int j=0; j<nums.length; j++) {
                System.out.print(nums[j]);
            }
            System.out.println();
        }
    }
}

#4

public abstract class Permutation {

	private Permutation(){}
	static int n=0;
	static void swap(int[] array,int i,int j){
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
	public static void permAll(int[] list){
		n=0;
		perm(list, 0, list.length-1);
	}
	public static void perm(int[] list, int k, int m){
		int i;
		if(k>m){
			for(i=0;i<=m;i++){
				System.out.print(list[i]+" ");
			}
			System.out.println();
			n++;
		}else{
			for(i=k;i<=m;i++){
				swap(list, k, i);
				perm(list,k+1,m);
				swap(list, k, i);
			}
		}
	}

	public static void main(String[] args){
		int list[] = {1, 2, 3, 4};     
		permAll(list);     
	    System.out.println("total:"+ n);   
	}
}

#5

用递归，3楼正解。

#6

看看这个http://bbs.csdn.net/topics/390483203

#7

这题属于月经题了，以前就有过类似的题；4、5楼答案很好，均是邻位对换的递归算法，下面提供两种常用的全排列非递归算法，基本思路：
1、自底向下---根据n!=n*(n-1)!构造哈夫曼树
2、自顶向下---对解空间进行广度遍历

package sort;

import java.util.LinkedList;
import java.util.Queue;

import org.junit.Test;


/**
 * 全排列的一个辅助节点
 *
 */
 class AllSortNode {

/**
 * 左子串
 */
private String leftStr;

/**
 * 右子串
 */
private String rightStr;


public String getLeftStr() {
	return leftStr;
}

public String getRightStr() {
	return rightStr;
}

public void setLeftStr(String leftStr) {
	this.leftStr = leftStr;
}

public void setRightStr(String rightStr) {
	this.rightStr = rightStr;
}

public AllSortNode() {
	super();
}

public AllSortNode(String leftStr, String rightStr) {
	super();
	this.leftStr = leftStr;
	this.rightStr = rightStr;
}

@Override
public String toString() {
	return "AllSortNode [leftStr=" + leftStr + ", rightStr=" + rightStr + "]";
}

}
public class PaiLie {

/**
 从底部向上 利用最优二叉树的构造过程和全排列的定义: n!=n*(n-1)!
 */
public LinkedList<String> fromButtomToTop(String str){
	LinkedList<String> sort=new LinkedList<String>();
	String end=str.charAt(str.length()-1)+"";
	sort.add(end);
	//把字符从后往前扫描
	for(int i=str.length()-2;i>=0;i--){
		String zhongString=str.charAt(i)+"";
		int size=sort.size();
		//从集合中依次取出字符串 依次遍历
		for(int m=0;m<size;m++){
			String after=sort.get(m);
			StringBuffer sb=new StringBuffer();
			//j从0到len，依次确定 前、中、后的字符串 然后合并  
			for(int j=0;j<=after.length();j++){
				String touString=after.substring(0, j);
				String weiString=after.substring(j, after.length());
				sb.append(touString);
				sb.append(zhongString);
				sb.append(weiString);
				String resuString=sb.toString();
				//把新字符串 添加到集合 sb制空
				sort.add(resuString);
				sb=new StringBuffer();
			}
		}
		//移除上次生成的短的字符串 为(str.length()-1-i)!
		int removeSize=this.jiecheng(str.length()-1-i);
		this.removeFirst(removeSize, sort);
	}
	return sort;
}

/**
 *阶乘 非递归
 */
public int jiecheng(int n){
	int sum=1;
	for(int i=1;i<=n;i++){
		sum*=i;
	}
	return sum;
}

/**
从集合头部移除一定数量的元素 
 */
public void removeFirst(int k,LinkedList<String> list){
	for(int i=1;i<=k;i++){
		list.remove(0);
	}
}
/**
层次遍历算法求全排列
 */
public String[] allSortWithQueue(String s){
	Queue<AllSortNode> que=new LinkedList<AllSortNode>();
	String leftRoot="";
	String rightRoot=s;
	AllSortNode root=new AllSortNode(leftRoot, rightRoot);
	//放入根节点
	que.offer(root);
	while(true){
		//直到某一个节点的右串为空
		if(que.peek().getRightStr().length()==0){
			break;
		}else{
			//弹出一个节点
			AllSortNode currentRoot=que.poll();
			//获得左右子串
			String rightStr=currentRoot.getRightStr();
			String leftStr=currentRoot.getLeftStr();
			int len=rightStr.length();
			for(int i=0;i<len;i++){
				//遍历右子串 依次取出一个字符，加到左子串之后
				//从而生成新的左子串和右子串，生成新的节点，压入队列
				StringBuffer sb=new StringBuffer(rightStr);
	        	sb.deleteCharAt(i);
	        	String leftChStr=leftStr+rightStr.charAt(i);
	        	String rightChStr=sb.toString();
                AllSortNode node=new AllSortNode(leftChStr+" ", rightChStr);
                que.offer(node);
			}
		}
	}
	int size=this.jiecheng(s.length());
	String[] resultArray=new String[size];
	int i=0;
	while(!que.isEmpty()){
		resultArray[i]=que.poll().getLeftStr();
		i++;
	}
	return resultArray;
}
@Test
public void testAllSort(){
	System.out.println("HFM法：");
	System.out.println("------");
	char[] charArray={'A','B','C'};
	String string=new String(charArray);
	LinkedList<String> list=fromButtomToTop(string);
	for(String str:list){
		for(int i=0;i<str.length();i++){
			System.out.print(str.charAt(i)+" ");
		}
		System.out.println("");
	}
	System.out.println("BFS法：");
	System.out.println("------");
	String[] array=allSortWithQueue(string);
	for(String str:array){
		System.out.println(str);
	}
}

}

结果：

HFM法：
------
A B C 
B A C 
B C A 
A C B 
C A B 
C B A 
BFS法：
------
A B C 
A C B 
B A C 
B C A 
C A B 
C B A 

可以看到，算法的不同会影响输出顺序。

#8

第一个笔误了，是“自底向上”。

#9

该回复于2013-06-08 09:10:51被管理员删除