Algorithm to get all combinations of k elements from n

Question

I have a list and I want to do some operation on elements of list starting from combination of 2.

Let's say below is my list:

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

It will generate below combination if we select 2 elements at a time:- (A,B) (A,C) (A,D) (A,E) (A,F) (A,G) (A,H) (B,C) (B,D) and so on

It will generate below combination if we select 3 elements at a time:- (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) and so on

Getting these combinations is very easy. I followed Algorithm to return all combinations of k elements from n and it is giving me exact output.

But I cannot use this code as I have another requirement where I will keep deleting the elements from the list in case they satisfy certain condition and hence number of combinations will keep on reducing. So I don't want to get all the combinations using LINQ as it will be hampering performance in my case.

I thought of doing it below way:

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

Removing elements will ensure that I get faster performance and I want to do this operation till the end reaches. I'm unable to think how to keep these deep level for loops in recursion. Can anyone help me in adding these endless for loops in recursion?

Thanks for spending your time in writing solution for me but this is not what I want... I will brief the requirement without code.

1. Let's say I have list of 10 elements.
2. I want to select all the combinations starting from group of 2 to 9. Total number of possible combinations will be 1012 if total elements are 10.
3. Now I want to start evaluating all the combinations in group of 2. Let's say first group (A,B). I will evaluate this group based upon certain conditions, and if that combination sastify the condition then I will remove the elements (A,B) from the list of 10 elements. So I will left with 8 elements in list.
4. Total number of combinations with remaining 8 elements will be 246 now. I didn't try the combinations (A,C) (A,D) and so on.
5. But I'm still evaluating the combinations in group of 2. Now I will pick remaining combinations in group of 2... Next combination will be (C,D) (C,E)..Let's say all remaining combinations doesn't satisfy condition of removing them from the list. Then I want to start evaluating combinations in group of 3.
6. First group of 3 will be (C,D,E)... If it will pass the certain condition then I will remove all the 3 elements from the list and I will be left with only 5 elements. Now I want to run my test of combination of 3 on these 5 elements.
7. after that group of 4 and so on

I hope you understand the use case now.

Can anyone help me out in implementing above use case?

Answer 1

Here is an algorithm i wrote in c++ for solving a similar problem. You should be able to use it for your purposes if you modify it a bit to work in 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);
}

You can see an explanation of how it works here.

Answer 2

The following solution will iterate over all possible combinations of elements from the input list, starting with combinations of 2 elements and moving upward from there. If the supplied filter function returns true then the elements chosen are removed from consideration; thus the total number of iterations is reduced as more elements are removed. Results are not tracked automatically; it's up to the caller to track results as required. My example usage to follow will demonstrate how to track results.

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;
}

The example below uses these functions in order to group letters; we want to take the letters A thru Z and put them into arbitrary groups such that each group contains more consonants than vowels, and contains at least one vowel:

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);

The results, which took 3131 iterations to perform (much fewer than iterating over all possible combinations without removal), are as follows:

ABC DEF GHI JKO PQU VWY

At this point all vowels were used up, so no more legal combinations were possible.

Answer 3

Not sure if this is exactly what you need, but it may be considered an approach.

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))
                );
        }
    }
}

I've used this answer as a helper. You can also see that Process method is loosely coupled with the set of conditions (just one in this example).