集合组合算法

//设计算法以求解从集合{1..n}中选取k(k<=n)个元素的所有组合。
// 例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 .
 //集合allLst{a1,a2,....an}
 //组合个数(维度):k(k<=n)
 //思路：
 //首先按照顺序排列第一个组合:{a1,a2....ak}
 //第一步：k项递增index，然后一直到an，到达第k项的极值.
 //第二步：向前递增k-1项递增index = index++，k项index按照k-1项顺序排列，再次递归k项到极值。
 //     如果k-1项到达极值index=n -(k - dimensi[维度，k-1项维度k-1]),以此类推，向前递增k-2项index,递归第二步。
 //第三步：当递归到第一项的最大极值，组合结束。

 

<!--<br/ /> <br/ /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br/ /> http://www.CodeHighlighter.com/<br/ /> <br/ /> -->package com.base.test1;

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

public class Test {

    ///结束标记
    public static boolean flag = false;
    class Element
    {
        public Object data;
        public int index;
    }
    public static void main(String[] args)
    {

        Test combine = new Test();
        int n = 10;
        int k = 9;
        ArrayList lst = new ArrayList();
        for( int i =0;i < n;i++)
        {
            lst.add(new Integer(i+1));
        }
        combine.computeColleCombine(lst, k);
    }
    public void computeColleCombine(List allLst,int k)
    {
        Element[] objs = new Element[k];
        //首先按照顺序组合第一个排列
        //{a1,a1,....ak}
        for(int i = 0;i < k;i++)
        {
            Element elment = new Element();
            elment.data = allLst.get(i);
            elment.index = i;
            objs[i] = elment;
        }
        printObjs(objs);
        int n = allLst.size();
        if( n > k )
        {
            //从后向前控制组合
            cycDimensionality(allLst,objs,k - 1);
        }
    }
    
    private void cycDimensionality(List allLst,Element[] elments,int dimensi)
    {
        int k = elments.length;
        int n = allLst.size();
        if(flag)
        {
            return ;
        }
        //控制最后一个元素开始打印
        if(dimensi==(k-1))
        {
            //第k项
            Element lastEl = elments[k - 1];
            //一直递增k项到极值
            while(lastEl.index < (n - 1))
            {
                lastEl.index = lastEl.index + 1;
                lastEl.data = allLst.get(lastEl.index);
                printObjs(elments);
            }
            //向前一项递增index
            cycDimensionality(allLst,elments,dimensi - 1);

        }else{
            //前一项=如index = k - 2
            Element preEl = elments[dimensi];
            //当前维度项索引最大极值
            int currDimensiMaxIndex = n - 1 - (k - 1 - dimensi);
            if(preEl.index < currDimensiMaxIndex)
            {
                preEl.index = preEl.index + 1;
                preEl.data = allLst.get(preEl.index);
                //preEl后面元素个数
                int nextCount = k - 1 - dimensi;
                //排序后面的元素
                for(int i = 0;i < nextCount;i++)
                {
                    int nextIndex= preEl.index + i + 1;
                    int nextDimensi = dimensi + i + 1;
                    elments[nextDimensi].index = nextIndex;
                    elments[nextDimensi].data = allLst.get(nextIndex);
                }
                printObjs(elments);
                //结束点：当第一维度达到极值，结束
                if(preEl.index == currDimensiMaxIndex &&
                        dimensi == 0)
                {
                    flag = true;
                    return;
                }
                //递归k项元素到极值
                cycDimensionality(allLst,elments,k - 1);
            }
            else{
                cycDimensionality(allLst,elments,dimensi - 1);
            }
        }
        
    }
    
    private  void printObjs(Element[] objs)
    {
        for(int i = 0;i < objs.length;i++)
            System.out.print(objs[i].data);
        System.out.println();
    }
}