Skip to content

Instantly share code, notes, and snippets.

@rockwotj
Last active August 29, 2015 14:10
Show Gist options
  • Save rockwotj/9d2338f51b10cbb96f36 to your computer and use it in GitHub Desktop.
Save rockwotj/9d2338f51b10cbb96f36 to your computer and use it in GitHub Desktop.
A couple of common combinatorics question solutions in C#
public static List<List<T>> GeneratePowerSet<T>(List<T> list)
{
var result = new List<List<T>>();
if (list.Count > 0)
{
foreach (var t in GeneratePowerSet(list.GetRange(1, list.Count - 1)))
{
result.Add(t);
var temp = DeepCopy(t);
temp.Add(list[0]);
result.Add(temp);
}
}
else
{
result.Add(new List<T>());
}
return result;
}
public static List<List<T>> GenerateAllKCombinations<T>(List<T> list, int k)
{
var result = new List<List<T>>();
if (k > 0)
{
for (int i = 0; i < list.Count - k + 1; i++)
{
var t = list[i];
var temp = DeepCopy(list);
temp.RemoveRange(0, i + 1);
var tempResult = GenerateAllKCombinations(temp, k - 1);
foreach (var tempItem in tempResult)
{
tempItem.Add(t);
result.Add(tempItem);
}
}
}
else
{
result.Add(new List<T>());
}
return result;
}
private static List<T> DeepCopy<T>(List<T> t)
{
var temp = new T[t.Count];
t.CopyTo(temp);
return temp.ToList<T>();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment