005-03 集合を指定した分割数に分割

集合を指定した分割数に分割するメソッドを実装します。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        // セパレータとInt型の列挙を引数として、結合したstringを返す
        Func<string, IEnumerable<int>, string> IntEnumJoin = (pSeparater, pEnum) =>
        {
            string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
            return string.Join(pSeparater, StrArr);
        };

        var ValList = new List<int>();
        for (int I = 1; I <= 3; I++) {
            ValList.Add(I * 10);
        }

        List<List<int[]>> BunkatuArrListList =
            BunkatuArrListListClass<int>.DeriveBunkatuArrListList(ValList, 2);

        foreach (List<int[]> EachBunkatuArrList in BunkatuArrListList) {
            Console.WriteLine("■■■分割結果■■■");
            foreach (int[] EachBunkatuArr in EachBunkatuArrList) {
                Console.WriteLine(IntEnumJoin(" ", EachBunkatuArr));
            }
        }
    }
}

#region BunkatuArrListListClass
// 集合を指定した分割数に分割
internal static class BunkatuArrListListClass<Type>
{
    // 列挙と分割数を引数として、配列のListのListを返す
    internal static List<List<Type[]>> DeriveBunkatuArrListList(IEnumerable<Type> pBaseEnum, int pDivCnt)
    {
        Type[] BaseArr = pBaseEnum.ToArray();

        var WillReturn = new List<List<Type[]>>();

        var DESResultList = new List<JyoutaiDef>();
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BitSetList = new List<int>();
        WillPush.BitSetList.Add(0);
        WillPush.UseBitSet = 0;
        Stk.Push(WillPush);

        int AllBitOn = (1 << BaseArr.Length) - 1;

        int UB = BaseArr.GetUpperBound(0);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.UseBitSet == AllBitOn) {
                if (Popped.BitSetList.Count == pDivCnt) {
                    DESResultList.Add(Popped);
                }
                continue;
            }

            if (Popped.BitSetList.Last() == 0) {
                // 最小添字が未使用なら、必ず使用する
                for (int I = 0; I <= UB; I++) {
                    int CurrBit = 1 << I;
                    if ((Popped.UseBitSet & CurrBit) > 0) continue;

                    WillPush.BitSetList = new List<int>(Popped.BitSetList);
                    int LastInd = WillPush.BitSetList.Count - 1;
                    WillPush.BitSetList[LastInd] |= CurrBit;
                    WillPush.UseBitSet = Popped.UseBitSet | CurrBit;
                    Stk.Push(WillPush);
                    break;
                }
            }
            else {
                // 分割を増やす場合
                if (Popped.BitSetList.Count < pDivCnt) {
                    WillPush.BitSetList = new List<int>(Popped.BitSetList);
                    WillPush.BitSetList.Add(0);
                    WillPush.UseBitSet = Popped.UseBitSet;
                    Stk.Push(WillPush);
                }

                // 分割せずに追加する場合
                int LastVal = Popped.BitSetList.Last();

                int CurrInd = -1;
                for (int I = UB; 0 <= I; I--) {
                    int CurrBit = 1 << I;
                    if ((LastVal & CurrBit) == 0) continue;
                    CurrInd = I;
                    break;
                }
                for (int I = CurrInd + 1; I <= UB; I++) {
                    int CurrBit = 1 << I;
                    if ((Popped.UseBitSet & CurrBit) > 0) continue;

                    WillPush.BitSetList = new List<int>(Popped.BitSetList);
                    int LastInd = WillPush.BitSetList.Count - 1;
                    WillPush.BitSetList[LastInd] |= CurrBit;
                    WillPush.UseBitSet = Popped.UseBitSet | CurrBit;
                    Stk.Push(WillPush);
                }
            }
        }

        foreach (JyoutaiDef EachDESResult in DESResultList) {
            var ResultArrList = new List<Type[]>();
            foreach (int EachBitSet in EachDESResult.BitSetList) {
                var CurrList = new List<Type>();
                for (int I = 0; I <= UB; I++) {
                    int CurrBit = 1 << I;
                    if ((EachBitSet & CurrBit) == 0) continue;
                    CurrList.Add(BaseArr[I]);
                }
                ResultArrList.Add(CurrList.ToArray());
            }
            WillReturn.Add(ResultArrList);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal List<int> BitSetList;
        internal int UseBitSet;
    }
}
#endregion

実行結果

■■■分割結果■■■
10 30
20
■■■分割結果■■■
10 20
30
■■■分割結果■■■
10
20 30

解説

深さ優先探索を使ってます。