転載:3種類の実装集合求子集合アルゴリズム

以下の内容は:ITeye narutolbyのログは少し調整されており、主体の内容に影響を与えず、参考学習に供する.
テーマ:集合を与えて、その集合のすべてのサブ集合を求めて、例えば集合{1,2}のサブ集合は{}(空集はすべての集合のサブセットである),{1},{2},{1,2},共に2^2のサブ集合で、以下は2つの解法を与えて、その中の第1の解法は再帰と非再帰で実現して、すべてjavaで実現します.【第1の解法】アルゴリズム思想:1つの集合を与えて、サブ集合を求める過程は以下の2つのステップに分けることができる:(1)集合を2つの部分に分けて、第1の要素と残りの要素、例えば{1,2,3}を1と{2,3}(2)の元の集合のすべてのサブ集合を残りの要素のサブセットに分けて、最初の要素をすべてのサブ集合に加えて、例えば{2,3}のサブ集合を{2},{3},{2,3}に分けて、{},では,最初の要素1をこれらのサブ集合に加えると,{1,2},{1,3},{1,2,3},{1,2,3},{1}を構成し,これらの集合を統合すると,元の集合のすべてのサブ集合が{2},{3},{2,3},{1,2},{1,2,3},{1,2,3},{1}となり,コードは以下の通りである.

//      
    static ArrayListString>> getSub(String args[])
    {
        ArrayListString>> result = new ArrayListString>>();
        ArrayListString>> temp = null;
        ArrayList<String> element = null;
        //       
        result.add(new ArrayList<String>());

        for (int i = 0; i < args.length; i++)
        {
            temp = new ArrayListString>>();
            for (int j = 0; j < result.size(); j++)
            {
                element = new ArrayList<String>();
                element.add(args[i]);
                element.addAll(result.get(j));
                temp.add(element);
            }
            result.addAll(temp);
        }
        return result;
    }

//       
    static ArrayListString>> getSub2(String args[], int index)
    {

        ArrayListString>> result = null;
        ArrayListString>> temp = null;
        ArrayList<String> element = null;
        String item = null;
        if (args.length == index)
        {
            result = new ArrayListString>>();
            result.add(new ArrayList<String>());
        }
        else
        {
            result = getSub2(args, index + 1);
            item = args[index];
            temp = new ArrayListString>>();
            for (ArrayList<String> sub2 : result)
            {
                element = new ArrayList<String>();
                element.addAll(sub2);
                element.add(item);
                temp.add(element);
            }
            result.addAll(temp);
        }
        return result;
    }

【第2の解法】アルゴリズム思想:n個の要素の集合は、サブ集合を構築する過程において、各要素には2つのケースがあり、サブ集合には「存在」と「存在しない」、「存在」は「1」、「存在しない」は「0」で表される.このように2^nのケース、すなわち2^n個のサブ集合がある.このとき、長さnの2進数「1111….000…」,1はその位置がサブセットに存在することを示し,0はその位置がサブセットに存在しないことを示し,このバイナリ数を0から2^nまで加算すると,すべての状況が現れる,コードは以下の通りである.

//         
    static ArrayList> getSub3(String args[])
    {
        ArrayList> result = new ArrayList>();
        ArrayList subList = null;
        int max = 1 << args.length;

        for (int i = 0; i < max; i++)
        {
            subList = new ArrayList();

            int k = i;
            int index = 0;
            while (k > 0)
            {
                if ((k & 1) > 0)
                {
                    subList.add(args[index]);
                }
                k >>= 1;
                index++;
            }
            result.add(subList);
        }
        return result;
    }

テストメソッド

public static void main(String[] args)
    {
        String array[] =
        {
                "a", "b", "c", "d"
        };
        ArrayList> list = null;
        //list = getSub(array);
        // list = getSub2(array, 0);
         list = getSub3(array);
        for (int i = 0; i < list.size(); i++)
        {
            ArrayList subList = list.get(i);
            System.out.println(subList.toString());
        }
    }