I am attempting to loop through every combination of an array in C# dependent on size, but not order. For example: var states = ["NJ", "AK", "NY"];
Some Combinations might be:
states = []; states = ["NJ"]; states = ["NJ","NY"]; states = ["NY"]; states = ["NJ", "NY", "AK"]; and so on... It is also true in my case that states = ["NJ","NY"] and states = ["NY","NJ"] are the same thing, as order does not matter.
Does anyone have any idea on the most efficient way to do this?
The combination of the following two methods should do what you want. The idea is that if the number of items is n then the number of subsets is 2^n. And if you iterate from 0 to 2^n - 1 and look at the numbers in binary you'll have one digit for each item and if the digit is 1 then you include the item, and if it is 0 you don't. I'm using BigInteger here as int would only work for a collection of less than 32 items and long would only work for less than 64.
public static IEnumerable<IEnumerable<T>> PowerSets<T>(this IList<T> set) { var totalSets = BigInteger.Pow(2, set.Count); for (BigInteger i = 0; i < totalSets; i++) { yield return set.SubSet(i); } } public static IEnumerable<T> SubSet<T>(this IList<T> set, BigInteger n) { for (int i = 0; i < set.Count && n > 0; i++) { if ((n & 1) == 1) { yield return set[i]; } n = n >> 1; } } With that the following code
var states = new[] { "NJ", "AK", "NY" }; foreach (var subset in states.PowerSets()) { Console.WriteLine("[" + string.Join(",", subset.Select(s => "'" + s + "'")) + "]"); } Will give you this output.
[] ['NJ'] ['AK'] ['NJ','AK'] ['NY'] ['NJ','NY'] ['AK','NY'] ['NJ','AK','NY'] 
You can use back-tracking where in each iteration you'll either (1) take the item in index i or (2) do not take the item in index i.
Pseudo code for this problem:
Main code:
picked) of the length of statesBacktracking function:
states array, its length, the current index and the bool arraystatespicked[i] to true and call the backtracking function with the next indexpicked[i] to false and call the backtracking function with the next index