Algorithm for obtaining all combinations of k elements from n
I have a list and I want to perform some operation on the elements of the list, starting with a combination of 2.
Let's put my list below:
List<string> strArr = new List<string> { "A", "B", "C", "D", "E", "F", "G", "H" };
It will generate the bottom combination if we select two elements at a time: (A, B) (A, C) (A, D) (A, E) (A, F) (A, G) (A, H) (B, C) (B, D) etc.
It will generate the bottom combination if we select three 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) etc.
Getting these combinations is easy. I have followed the Algorithm to return all combinations of k elements from n and it gives me the exact result.
But I cannot use this code as I have another requirement in which I will continue to remove items from the list if they meet a certain condition, and therefore the number of combinations will continue to decrease. So I don't want to get all the combinations using LINQ as it would hinder performance in my case.
I thought to do it below:
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 the items ensures that I get better performance and I want to make this operation through to the end. I can't think of how to keep this deep level for loops in recursion. Can anyone help me on adding these infinite loops to recursion?
Thanks for taking your time to write a solution for me, but that's not what I want ... I'll cover it without code.
- Let's say I have a list of 10 items.
- I want to select all combinations starting with a group from 2 to 9. The total number of possible combinations will be 1012 if the total number of elements is 10.
- Now I want to start evaluating all combinations in group 2. Let the first group (A, B) speak. I will evaluate this group based on certain conditions, and if this combination flattens out the condition, I will remove items (A, B) from the list of 10 items. Therefore, I will be left with 8 items in the list.
- The total number of combinations with the remaining 8 elements will now be 246. I have not tried combinations (A, C) (A, D), etc.
- But I am still evaluating the combinations in group 2. Now I will select the remaining combinations in the group of 2 ... The next combination will be (C, D) (C, E). Let's say that all other combinations do not satisfy the condition of their removal from the list. Then I want to start evaluating combinations in a group of 3.
- The first group of 3 will be (C, D, E) ... If it passes a certain condition, I will remove all 3 elements from the list and I will leave only 5 elements. Now I want to run my test for a combination of 3 on these 5 elements.
- after this group of 4, etc.
Hopefully now you understand the use case.
Can anyone help me with the implementation of the above use case?
source to share
Not sure if this is exactly what you need, but this can be seen as 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 used this answer as a helper. You can also see that the method is Process
loosely coupled to a set of conditions (only one in this example).
source to share
The next solution will iterate over all possible combinations of elements from the input list, starting with combinations of two elements and moving up from there. If the provided filter function returns true, then the selected items are removed from consideration; thus, the total number of iterations decreases as more items are removed. Results are not automatically tracked; it's up to the caller to track the results as needed. My use case will show you how to track the 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;
}
In the example below, these functions are used to group letters; we want to take the letters A through Z and put them in arbitrary groups, so 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 ran 3131 iterations (much less than repeating all possible combinations without deleting), are as follows:
ABC DEF GHI JKO PQU VWY
At this point, all the vowels were consumed, so there were no more possible combinations.
source to share
Here is an algorithm I wrote in C ++ to solve a similar problem. You should use it for your own purposes if you modify it slightly 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 how it works here .
source to share