4

可能なすべての組み合わせを含む別のリストからリストを作成する必要があります。可能な解決策を調査す​​る中で、多くの興味深いアプローチを見つけましたが、すべて提供されたレコードの数に基づいて結果を生成するようです。組み合わせを最大しきい値まで増やす必要があります。

つまり、次の配列を検討してください

1,2,3,4,5

次のような結果が必要です (この例ではしきい値は 3 です)

1
1,2
1,2,3
1,2,4
1,2,5
1,3,4
2,3,5... etc

実際には、データは IEnumerable になります。目的の結果を示すために、単純な int[] を使用しました。

4

3 に答える 3

5

私のソリューションでは、単純な再帰アルゴリズムを使用して組み合わせを作成します。

  • シーケンスをウォークスルーすると、現在の値のみを保持するシーケンスをすぐに返すことができます。単一のアイテムの IEnumerable を作成する簡単な拡張メソッドを作成しました。

  • 次に、しきい値を 1 減らして残りの要素のすべての組み合わせを再帰的に生成し、それぞれを現在の値と組み合わせます。

要素が繰り返されるべきではないと仮定します (つまり、{ 1, 1 } または { 1, 2, 1 } は許可されません)。要素の繰り返しを許可したい場合は、変数を削除して、 への再帰呼び出しで にremaining置き換えることができます。valuesGetCombinations

yieldキーワードの使用に注意してください。これは、コードが遅延実行を使用することを意味します。実際に結果を列挙する前に、中間結果を保存する必要はありません。

public static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> values, int threshold)
{
    var remaining = values;

    foreach (T value in values)
    {
        yield return value.Yield();

        if (threshold < 2)
        {
            continue;
        }

        remaining = remaining.Skip(1);

        foreach (var combination in GetCombinations(remaining, threshold - 1))
        {
            yield return value.Yield().Concat(combination);
        }
    }
}

public static IEnumerable<T> Yield<T>(this T item)
{
    yield return item;
}

整数配列 { 1, 2, 3, 4, 5 } の出力は次のとおりです。

1
1, 2
1, 2, 3
1, 2, 4
1, 2, 5
1, 3
1, 3, 4
1, 3, 5
1, 4
1, 4, 5
1, 5
2
2, 3
2, 3, 4
2, 3, 5
2, 4
2, 4, 5
2, 5
3
3, 4
3, 4, 5
3, 5
4
4, 5
5
于 2013-10-04T23:26:27.887 に答える
1

ここに1つの解決策があります：

public static IEnumerable<T[]> Combinations<T>(IEnumerable<T> items, int threshold)
{
    var comboBuilder = new List<T>();
    foreach (var combo in EnumerateCombos(items, comboBuilder, 0, threshold))
    {
        yield return combo;
    }
}
private static IEnumerable<T[]> EnumerateCombos<T>(IEnumerable<T> items, List<T> currentCombo, 
                                                   int startIndex, int threshold)
{
    if (currentCombo.Count >= threshold) { yield break; }

    for (int i = startIndex; i < items.Count(); i++)
    {
        //Skip past the items we've already gone through in the current combo:
        var item = items.Skip(i).First();

        //Create a new combination with the next available item:
        currentCombo.Add(item);
        yield return currentCombo.ToArray();

        //Repeat the process with the rest of the remaining items:
        foreach (var combo in EnumerateCombos(items, currentCombo, i + 1, threshold))
        {
            yield return combo;
        }

        //Recursion cleanup:
        currentCombo.RemoveAt(currentCombo.Count - 1);
    }
}
于 2013-10-04T20:24:01.820 に答える
1

特定の数の組み合わせを見つけるための解決策が既にあると仮定すると（あなたが言った）、署名について考えてみましょう：

public static IEnumerable<IEnumerable<T>> Combinations<T>(
    IList<T> source, int count)

次に、N 回呼び出すことで、すべてのカウントの組み合わせを簡単に取得できます。

public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> source)
{
    return Enumerable.Range(0, source.Count)
            .SelectMany(i => Combinations(source, i));
}
于 2013-10-04T18:51:17.867 に答える