浏览 4348 次
|
锁定老帖子 主题：排列组合算法实现【学习】
精华帖 (0) :: 良好帖 (0) :: 新手帖 (2) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-08-16
最后修改：2011-03-06
一个从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);
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2010-08-16
请看懂算法了的 给个留言好伐
不要看到标题 就投新手贴 只是希望多交流而已 |
| 返回顶楼 | |
|
发表时间：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 到数组元素，每轮更新一下栈。实现也超简单 …… |
| 返回顶楼 | |
