2

一連の値 ( 1、1、1、12、) があるとします。その合計が事前定義された範囲内にあるすべての可能な組み合わせ (反復なし) をどのように生成します12か。たとえば、 と の間の範囲を持つ (すべての深さの) すべての組み合わせは次のとおりです。16[min,max]1317

1 12

1 1 12

1 1 1 12

16

1 16

これは、同じ値の各項目が区別できないと想定しているため1 12、最終出力に 3 つの結果はありません。総当たりは可能ですが、アイテム数が多い状況では、すべての深さでの組み合わせの数は天文学的です。上記の例では、(3 + 1) * (2 + 1) * (1 + 1) = 24 の組み合わせがすべての深さで存在します。したがって、組み合わせの合計は、任意の値の項目数 + 1 の積になります。もちろん、論理的には、部分和が最大値より大きい膨大な数の組み合わせを除外できます (たとえば、セット16 12がすでに最大値より大きい)。の値な17ので、 と が含まれる組み合わせはスキップ16し12てください)。

私は当初、入力配列を 2 つの配列に変換し、それらを走行距離計のようにインクリメントできると考えていました。しかし、私はこの再帰的アルゴリズムが早期に壊れてしまうことに完全に行き詰まっています。助言がありますか？

{
    int uniqueValues = 3;
    int[] maxCounts = new int[uniqueValues];
    int[] values = new int[uniqueValues];

    // easy code to bin the data, just hardcoding for example
    maxCounts[0] = 3;
    values[0] = 1;
    maxCounts[1] = 2;
    values[1] = 12;
    maxCounts[2] = 1;
    values[2] = 16;

    GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}

private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    if (index >= maxValues.Length)
    {
        return;
    }

    while (currentCombo[index] < maxValues[index])
    {
        currentValue += values[index];

        if (currentValue> max)
        {                   
            return;
        }

        currentCombo[index]++;

        if (currentValue< min)
        {                    
            GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            results.Add((int[])currentCombo.Clone());
        }
    }
}

編集

整数値はデモ用です。ある種の数値 ( int、double、floatなど...)を持つ任意のオブジェクトにすることができます。

通常、一意の値はほんの一握り (約 10 程度) ですが、合計で数千のアイテムが存在する場合があります。

4

5 に答える 5

0

別の実装のアイデア:

番号のリストからスタックのリストを作成します。各スタックはリストに表示される番号を表し、この番号は番号リストに表示された回数だけスタックにプッシュされます。さらに、このリストはソートされています。

アイデアは、スタック リストを反復処理し、最大値を超えていない場合は各スタックで一度に 1 つの数値をポップして関数を呼び出し、現在のスタックをスキップする追加の呼び出しを実行するというものです。

このアルゴリズムは、この値を追加すると最大値を超えたときに同じ値を持つ異なる要素を追加しようとするなど、多くの冗長な計算を減らします。

このアルゴリズムでかなり大きな問題 (50 個以上) を解決することができました。最小値と最大値によっては、明らかに間隔が非常に大きい場合、組み合わせの数が膨大になる可能性があります。

コードは次のとおりです。

static void GenerateLimitedCombinations(List<int> intList, int minValue, int maxValue)
{
    intList.Sort();
    List<Stack<int>> StackList = new List<Stack<int>>();
    Stack<int> NewStack = new Stack<int>();
    NewStack.Push(intList[0]);
    StackList.Add(NewStack);

    for (int i = 1; i < intList.count; i++)
    {
        if (intList[i - 1] == intList[i])
            StackList[StackList.count - 1].Push(intList[i]);
        else
        {
            NewStack = new Stack<int>();
            NewStack.Push(intList[i]);
            StackList.Add(NewStack);
        }
    }

    GenerateLimitedCombinations(StackList, minValue, maxValue, 0, new List<int>(), 0);
}

static void GenerateLimitedCombinations(List<Stack<int>> stackList, int minValue, int maxValue, int currentStack, List<int> currentCombination, int currentSum)
{
    if (currentStack == stackList.count)
    {
        if (currentSum >= minValue)
        {
            foreach (int tempInt in CurrentCombination)
            {
                Console.Write(tempInt + " ");
            }
            Console.WriteLine(;
        }
    }

    else
    {
        int TempSum = currentSum;
        List<int> NewCombination = new List<int>(currentCombination);
        Stack<int> UndoStack = new Stack<int>();

        while (stackList[currentStack].Count != 0 && stackList[currentStack].Peek() + TempSum <= maxValue)
        {
            int AddedValue = stackList[currentStack].Pop();
            UndoStack.Push(AddedValue);
            NewCombination.Add(AddedValue);
            TempSum += AddedValue;
            GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, new List<int>(NewCombination), TempSum);
        }

        while (UndoStack.Count != 0)
        {
            stackList[currentStack].Push(UndoStack.Pop());
        }

        GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, currentCombination, currentSum);
    }
}

テストプログラムは次のとおりです。

static void Main(string[] args)
{
    Random Rnd = new Random();
    List<int> IntList = new List<int>();
    int NumberOfInts = 10, MinValue = 19, MaxValue 21;

    for (int i = 0; i < NumberOfInts; i++) { IntList.Add(Rnd.Next(1, 10));
    for (int i = 0; i < NumberOfInts; i++) { Console.Write(IntList[i] + " "); } Console.WriteLine(); Console.WriteLine();

    GenerateLimitedCombinations(IntList, MinValue, MaxValue);
    Console.ReadKey();
}
于 2013-10-13T14:47:14.097 に答える