java实现排列组合算法

1、组合

package com.ubs.is;

import java.util.ArrayList;
import java.util.BitSet;

public class Combination {
    private ArrayList<String> combList = new ArrayList<String>();

    public void mn(String[] array, int n) {
        int m = array.length;
        if (m < n)
            throw new IllegalArgumentException("Error   m   <   n");
        BitSet bs = new BitSet(m);
        for (int i = 0; i < n; i++) {
            bs.set(i, true);
        }
        do {
            printAll(array, bs);
        } while (moveNext(bs, m));

    }

    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 = start; 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 void printAll(String[] array, BitSet bs) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < array.length; i++)
            if (bs.get(i)) {
                sb.append(array[i]).append(',');
            }
        sb.setLength(sb.length() - 1);
        combList.add(sb.toString());
    }

    public ArrayList<String> getCombList() {
        return combList;
    }
   
    private void pp(int count,int selected){
        String[] source = new String[count];
        for(int i=0;i<count;i++){
            source[i]=""+i;
        }
        Combination comb = new Combination();
        comb.mn(source, selected);
        for (int i = 0; i < comb.getCombList().size(); i++) {
            //System.out.println(comb.getCombList().get(i));
        }
        System.out.println("total:"+comb.getCombList().size()+":"+count+","+selected);

    }

    public static void main(String[] args) throws Exception {
        int count=10;
        int selected=5;
        String[] source = new String[count];
        for(int i=0;i<count;i++){
            source[i]=""+i;
        }   
        Combination comb = new Combination();
        comb.mn(source, selected);
        for (int i = 0; i < comb.getCombList().size(); i++) {
            System.out.println(comb.getCombList().get(i));
            //String[] list = comb.getCombList().get(i).split(",");
            //Arrange ts = new Arrange();
            //ts.perm(list, 0, list.length - 1);
            //for (int j = 0; j < ts.getArrangeList().size(); j++) {
                //System.out.println("/u0009" + ts.getArrangeList().get(j));
            //}
        }
        System.out.println("total:"+comb.getCombList().size());
       
        comb.pp(10,1);
        comb.pp(10,2);
        comb.pp(10,3);
        comb.pp(10,4);
        comb.pp(10,5);
        comb.pp(10,6);
        comb.pp(10,7);
        comb.pp(10,8);
        comb.pp(10,9);       
    }

}

 

2、排列

package com.ubs.is;

import java.util.ArrayList;

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" };
        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);
    }
}

3、调用

package com.ubs.is;

import java.util.ArrayList;

public class ArrangeCombine {
    public static ArrayList<String> getArrangeOrCombine(String[] args, int n,
            boolean isArrange) throws Exception {
        if (args.length <= 0) {
            throw new Exception("array.length<=0");
        }
        if (n > args.length) {
            throw new Exception(" n>array.length");
        }
        Combination comb = new Combination();
        comb.mn(args, n);
        if (!isArrange) {
            return comb.getCombList();
        }
        ArrayList<String> arrangeList = new ArrayList<String>();
        for (int i = 0; i < comb.getCombList().size(); i++) {
            String[] list = comb.getCombList().get(i).split(",");
            Arrange ts = new Arrange();
            ts.perm(list, 0, list.length - 1);
            for (int j = 0; j < ts.getArrangeList().size(); j++) {
                arrangeList.add(ts.getArrangeList().get(j));
            }
        }
        return arrangeList;
    }   
}