2

リストがあり、2の組み合わせから始めてリストの要素に対していくつかの操作を実行したいと思います。

以下が私のリストだとしましょう：

List<string> strArr = new List<string> { "A", "B", "C", "D", "E", "F", "G", "H" };

一度に2つの要素を選択すると、以下の組み合わせが生成されます:-( A、B）（A、C）（A、D）（A、E）（A、F）（A、G）（A、H） （B、C）（B、D）など

一度に3つの要素を選択すると、以下の組み合わせが生成されます:-( A、B、C）（A、B、D）（A、B、E）（A、B、F）（A、B、G） （A、B、H）（A、C、D）（A、C、E）（A、C、F）（A、C、G）（A、C、H）（A、D、E）（ A、D、F）（A、D、G）（A、D、H）（A、E、F）（A、E、G）（A、E、H）（A、F、G）（A 、F、H）（A、G、H）（B、C、D）（B、C、E）（B、C、F）など

これらの組み合わせを取得するのは非常に簡単です。アルゴリズムに従って、nからk個の要素のすべての組み合わせを返し ましたが、正確な出力が得られます。

ただし、特定の条件を満たす場合に要素をリストから削除し続けるという別の要件があるため、このコードを使用できません。したがって、組み合わせの数は減少し続けます。したがって、私の場合はパフォーマンスが低下するため、LINQを使用してすべての組み合わせを取得する必要はありません。

私はそれを以下の方法で行うことを考えました：

List<string> strArr = new List<string> { "A", "B", "C", "D", "E", "F", "G", "H" };
// Loop for selecting combination of two elements at time
for (int i = 0; i < strArr.Count; i++)
{
    for (int j = i + 1; j < strArr.Count; j++)
    {
        // Writing on Console
        // Actually do some operation to check whether these two elements in list needs to be removed or not
        Console.Write(strArr[i] + strArr[j]);
        Console.WriteLine();

        // Check whether current combination of 2 elements need to be removed or not
        if (<< condition >>)
        {
            // Remove both the current elements

            // Remove current element of outer loop
            strArr.RemoveAt(i);
            // Remove current element of inner loop
            // Subtracting one as list size is reduced by 1
            strArr.RemoveAt(j - 1);

            //
            i--;
            break;
        }
    }
}

bool isRemoved = false;
// Loop for selecting combination of three elements at time
for (int i = 0; i < strArr.Count; i++)
{
    for (int j = i + 1; j < strArr.Count; j++)
    {
        for (int k = j + 1; k < s.Count; k++)
        {
            // Writing on Console
            // Actually do some operation to check whether these three elements in list needs to be removed or not
            Console.Write(strArr[i] + strArr[j] + strArr[k]);
            Console.WriteLine();

            // Check whether current combination of 3 elements need to be removed or not
            if (<< condition >>)
            {
                // Remove all the three elements

                // Remove current element of outer loop
                strArr.RemoveAt(i);
                // Remove current element of inner loop
                // Subtracting 1 as list size is reduced by 1
                strArr.RemoveAt(j - 1);
                // Subtracting 2 as list size is reduced by 2
                strArr.RemoveAt(k - 2);
                isRemoved = true;
                i--;
                break;
            }

            // If elements are removed then exit from loop with variable j
            if (isRemoved)
            {
                break;
            }
        }
    }
}

// Now make loop for selecting combination of four elements at time
// and keep removing the elements depending upon condition

要素を削除すると、パフォーマンスが向上するので、最後までこの操作を実行したいと思います。再帰的にループのこれらの深いレベルを維持する方法を考えることができません。再帰でこれらの無限のforループを追加するのを手伝ってくれる人はいますか？

ソリューションの作成に時間を割いていただきありがとうございますが、これは私が望んでいることではありません...コードなしで要件を簡単に説明します。

  1. 10個の要素のリストがあるとしましょう。
  2. 2から9までのすべての組み合わせを選択したい。要素の総数が10の場合、可能な組み合わせの総数は1012になります。
  3. 次に、2つのグループのすべての組み合わせの評価を開始します。最初のグループ（A、B）としましょう。特定の条件に基づいてこのグループを評価し、その組み合わせが条件をサスティファイする場合は、10個の要素のリストから要素（A、B）を削除します。したがって、リストに8つの要素を残します。
  4. 残りの8つの要素との組み合わせの総数は246になります。（A、C）（A、D）などの組み合わせは試していません。
  5. しかし、私はまだ2つのグループの組み合わせを評価しています。次に、2つのグループの残りの組み合わせを選択します...次の組み合わせは（C、D）（C、E）になります。残りのすべての組み合わせがそうではないとしましょう。リストからそれらを削除する条件を満たします。次に、3つのグループの組み合わせの評価を開始します。
  6. 3つの最初のグループは（C、D、E）になります...特定の条件に合格した場合、リストから3つの要素すべてを削除し、5つの要素のみを残します。次に、これら5つの要素で3の組み合わせのテストを実行します。
  7. その後、4人のグループなど

ユースケースを今すぐ理解していただければ幸いです。

上記のユースケースの実装を手伝ってくれる人はいますか？

4

3 に答える 3

1

次のソリューションは、2 つの要素の組み合わせから始まり、そこから上に向かって、入力リストから要素のすべての可能な組み合わせを反復処理します。提供されたフィルター関数が true を返す場合、選択された要素は考慮から除外されます。したがって、より多くの要素が削除されるにつれて、反復の総数が減少します。結果は自動的に追跡されません。必要に応じて結果を追跡するのは発信者次第です。従う私の使用例は、結果を追跡する方法を示しています。

public static void PermutateElements<T>(
    IEnumerable<T> elements,
    Predicate<IEnumerable<T>> filterGroup)
{
    var chooseFrom = new LinkedList<T>(elements);
    var chosen = new List<T>(chooseFrom.Count);
    for (int chooseCount = 2; chooseCount < chooseFrom.Count - 1; chooseCount++)
    {
        Permutate(chooseFrom, chooseCount, filterGroup, chosen, 0);
    }
}

static bool Permutate<T>(LinkedList<T> chooseFrom, int chooseCount,
    Predicate<IEnumerable<T>> filterPermutation, IList<T> chosen, int skipLast)
{
    int loopCount = chooseFrom.Count;
    for (int i = 0; i < loopCount; i++)
    {
        var choosingNode = chooseFrom.First;
        chooseFrom.RemoveFirst();

        bool removeChosen = false;
        if (i < loopCount - skipLast)
        {
            chosen.Add(choosingNode.Value);
            if (chooseCount == 1)
                removeChosen = filterPermutation(chosen);
            else
                removeChosen = Permutate(chooseFrom, chooseCount - 1, filterPermutation, chosen, skipLast + i);
            chosen.RemoveAt(chosen.Count - 1);
        }
        if (!removeChosen)
            chooseFrom.AddLast(choosingNode);
        else if (chosen.Count > 0)
            return true;
    }
    return false;
}

以下の例では、文字をグループ化するためにこれらの関数を使用しています。A から Z までの文字を任意のグループに分けて、各グループに母音よりも多くの子音が含まれ、少なくとも 1 つの母音が含まれるようにします。

HashSet<char> vowels = new HashSet<char>(new char[] { 'A', 'E', 'I', 'O', 'U', 'Y' });
var results = new List<IEnumerable<char>>();
Predicate<IEnumerable<char>> processGroup = delegate(IEnumerable<char> groupElements)
{
    int vowelCount = groupElements.Count(x => vowels.Contains(x));
    int consonantCount = groupElements.Count(x => !vowels.Contains(x));
    if (vowelCount < consonantCount && vowelCount > 0)
    {
        results.Add(new List<char>(groupElements));
        return true;
    }
    else
        return false;
};

var elements = new char[26];
for (int i = 0; i < elements.Length; i++)
    elements[i] = (char)('A' + i);
PermutateElements(elements, processGroup);

実行に 3131 回の反復を要した結果 (削除せずにすべての可能な組み合わせを反復するよりもはるかに少ない) は、次のとおりです。

ABC DEF GHI JKO PQU VWY

この時点ですべての母音が使い果たされたため、これ以上正しい組み合わせはできませんでした。

于 2013-01-31T15:19:26.247 に答える
0

これがまさに必要なものかどうかはわかりませんが、アプローチと見なされる場合があります。

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Tuple<Expression, Expression>>  conditions = new List<Tuple<Expression, Expression>>();

            // a complex condition, that the current item contains both "B" and "H"
            Expression<Func<IEnumerable<string>, bool>> expression1 = item => item.Contains("B") && item.Contains("H");

            // an expression which is used to exclude the elements from the list
            Expression<Func<string, bool>> expression2 = j => j != "B" && j != "H";

            // associate the condition with the exclusion filter
            var condition = new Tuple<Expression, Expression>(expression1, expression2);

            conditions.Add(condition);

            List<string> strArr = new List<string> { "A", "B", "C", "D", "E", "F", "G", "H" };

            IEnumerable<IEnumerable<string>> result = Process(strArr, conditions);
        }

        private static IEnumerable<IEnumerable<string>> Process(IEnumerable<string> strArr, List<Tuple<Expression, Expression>> conditions)
        {
            List<IEnumerable<string>> response = new List<IEnumerable<string>>();
            int k = 0;
            for (int i = 1; i <= strArr.Count(); i++)
            {
                k++;
                var r = strArr.Combinations(Math.Min(strArr.Count(), k));
                bool stop=false;
                foreach (IEnumerable<string> item in r)
                {
                    if (stop)
                    {
                        break;
                    }
                    foreach (Tuple<Expression, Expression> condition in conditions)
                    {
                        if (Enumerable.Repeat<IEnumerable<string>>(item, 1).Any(Evaluate(condition.Item1) as Func<IEnumerable<string>, bool>))
                        {
                            var initialCount = strArr.Count();
                            strArr = strArr.Where(Evaluate(condition.Item2) as Func<string, bool>);
                            i -= initialCount - strArr.Count();
                            stop = true;
                            break;
                        }
                        else
                        {
                            foreach (var item1 in r)
                            {
                                response.Add(item1);
                            }
                        }
                    }

                }
            }
            return response;
        }

        public static object Evaluate(Expression e)
        {
            if (e.NodeType == ExpressionType.Constant)
                return ((ConstantExpression)e).Value;
            return Expression.Lambda(e).Compile().DynamicInvoke();
        }
    }

    public static class Helper
    {
        public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
        {
            return k == 0 ? new[] { new T[0] } :
              elements.SelectMany((e, i) =>
                elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c))
                );
        }
    }
}

この回答をヘルパーとして使用しました。Processメソッドが一連の条件 (この例では 1 つだけ) と疎結合されていることもわかります。

于 2013-01-31T14:37:06.197 に答える
0

これは、同様の問題を解決するために c++ で作成したアルゴリズムです。C# で動作するように少し変更すれば、目的に合わせて使用​​できるはずです。

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

仕組みの説明はこちらでご覧いただけます。

于 2015-02-03T19:58:53.290 に答える