排列组合算法实现【学习】

一个从M个数字里面取N个数字的组合
没用到递归的实现，将选取的位置标记为1没选取的标记为0
返回的是数组的形式。

版本1

public class CombineUtil {
	
	private static int[] copy(int[] bs){
		int[] result = new int[bs.length];
		for(int i=0;i<bs.length;i++){
			result[i] = bs[i];
		}
		return result ;
	}


	public static void print(List<int[]> l){
		for(int i=0;i<l.size();i++){
			int[] a = (int[])l.get(i);
			for(int j=0;j<a.length;j++){
				System.out.print(a[j]+"\t");
			}
			System.out.println();
		}
	}

	public static void print(int[] a){
		for(int j=0;j<a.length;j++){
			System.out.print(a[j]+"\t");
		}
		System.out.println();
	}
	
	/**
	 * 从m里选n个数字
	 * @param m
	 * @param n
	 * @return
	 */
	public static List<int[]> combineEx(int m, int n) {
		if (m < n) {
			return null;
		}
		
		List<int[]> list = new ArrayList<int[]>();
		int[] cn = new int[m];
		for (int i = 0; i < cn.length; i++) {
			if (i < n) {
				cn[i] = 1;
			} else {
				cn[i] = 0;
			}
		}
		
		boolean flag = true;
		
		do {
			int pos = 0;
			int sum = 0;
			boolean tempFlag = true;
			
			list.add(copy(cn));
			if (m == n || m == 0) {
				return list;
			}
			
			for (int i = 0; i < m - 1; i++) {
				if (cn[i]==1 && cn[i+1]==0) {
					cn[i]=0;
					cn[i+1]=1;
					pos = i;
					break;
				}
			}
			
			for (int i = 0; i < pos; i++) {
				if (cn[i] == 1) {
					sum ++;
				}
			}
			
			for (int i = 0; i < pos; i++) {
				if (i < sum) {
					cn[i] = 1;
				} else {
					cn[i] = 0;
				}
			}
			
			for (int i = m-n; i < cn.length; i++) {
				if (cn[i] == 0) {
					tempFlag = false;
					break;
				}
			}
			
			flag = !tempFlag;
		} while (flag);
		list.add(copy(cn));
		
		return list;
	}
	
	public static void main(String[] args) {

		try {
			CombineUtil.print(combineEx(3, 3));

		} catch (Exception e) {
			e.printStackTrace();
		}  
		
	}

版本二

public class CombinationEx {
	
	private List<String> list = new ArrayList<String>();
	
	private void mn(int m, int n) {
		if ( m < n) {
			throw new IllegalArgumentException("参数异常"); 
		}
		
		BitSet bs = new BitSet(m);
		for (int i = 0; i < n; i++) {
			bs.set(i, true);
		}
		
		do {
			printAll(m, bs);
		} while(moveNext(bs, m)); 
	}
	
	private void printAll(int m, BitSet bs) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < m; i++) {
			if (bs.get(i)) {
				sb.append("1").append(",");
			} else {
				sb.append("0").append(",");
			}
		}
		sb.setLength(sb.length() - 1);
		list.add(sb.toString());
	}
	
	private boolean moveNext(BitSet bs, int m) {
		int start = -1;
		while (start < m) {
			if (bs.get(++start)) {
				break;
			}
		}
		
		if (start >= m) {
			return false;
		}
		
		int end = start;
		while (end < m) {
			if (!bs.get(++end)) {
				break;
			}
		}
		
		if (end >= m) {
			return false;
		}
		
		for (int i = 0; i < end; i++) {
			bs.set(i, false);
		}
		
		for (int i = 0; i < end - start - 1; i++) {
			bs.set(i);
		}
		
		bs.set(end);
		return true;
	}
	
	private List<String> getList() {
		return list;
	}
	
	public static void main(String[] args) {
		CombinationEx co = new CombinationEx();
		co.mn(5, 3);
		for (int i = 0; i < co.getList().size(); i++) {
			System.out.println(co.getList().get(i));
		}
	}
}

下面介绍全排列的算法

public class Arrange {
	private int total = 0;
	private ArrayList<String> arrangeList = new ArrayList<String>();

	public Arrange() {
	}

	private void swap(String list[], int k, int i) {
		String c3 = list[k];
		list[k] = list[i];
		list[i] = c3;
	}

	public void perm(String list[], int k, int m) {
		if (k > m) {
			StringBuffer sb = new StringBuffer();
			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);
			}
		}
	}

	public int getTotal() {
		return total;
	}

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

	public static void main(String args[]) {
		// String list[] = { "1", "2", "3", "4", "5" };
		String list[] = { "1", "2", "3" };
		Arrange ts = new Arrange();
		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);
	}
}

评论

2 楼 night_stalker 2010-08-16  

lz 注定要杯具的，下面跑跑题：


A

话说，Ruby 1.9.2 的数组有各种排列组合方法，使用超简单的 ……

irb(main):001:0> [1,2,3,4].combination(3).to_a # 组合
=> [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
irb(main):002:0> [1,2,3].permutation(3).to_a # 排列
=> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

如果直接给个闭包作参数，就可以不生成中间结果，以单个排列/组合结果为元素跑循环。


B

看 Array#combination 的实现(C)，用了一个栈：

static VALUE
rb_ary_combination(VALUE ary, VALUE num)
{
    long n, i, len;

    n = NUM2LONG(num);
    RETURN_ENUMERATOR(ary, 1, &num);
    len = RARRAY_LEN(ary);
    if (n < 0 || len < n) {
	/* yield nothing */
    }
    else if (n == 0) {
	rb_yield(rb_ary_new2(0));
    }
    else if (n == 1) {
	for (i = 0; i < len; i++) {
	    rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
	}
    }
    else {
	volatile VALUE t0 = tmpbuf(n+1, sizeof(long));
	long *stack = (long*)RSTRING_PTR(t0);
	volatile VALUE cc = tmpary(n);
	VALUE *chosen = RARRAY_PTR(cc);
	long lev = 0;

	MEMZERO(stack, long, n);
	stack[0] = -1;
	for (;;) {
	    chosen[lev] = RARRAY_PTR(ary)[stack[lev+1]];
	    for (lev++; lev < n; lev++) {
		chosen[lev] = RARRAY_PTR(ary)[stack[lev+1] = stack[lev]+1];
	    }
	    rb_yield(rb_ary_new4(n, chosen));
	    if (RBASIC(t0)->klass) {
		rb_raise(rb_eRuntimeError, "combination reentered");
	    }
	    do {
		if (lev == 0) goto done;
		stack[lev--]++;
	    } while (stack[lev+1]+n == len+lev+1);
	}
    done:
	tmpbuf_discard(t0);
	tmpary_discard(cc);
    }
    return ary;
}

上面代码前面一大段是各种边界检查什么的，下面那几行 for(;;) 便是核心逻辑。
返回数组 chosen = 栈(index) map 到数组元素，每轮更新一下栈。实现也超简单 ……

1 楼 yangtao309 2010-08-16  

请看懂算法了的 给个留言好伐
不要看到标题 就投新手贴
只是希望多交流而已