如何获得数组的所有子集？
给出一个数组： [dog, cat, mouse]
什么是最优雅的方式来创build：
[,,] [,,mouse] [,cat,] [,cat,mouse] [dog,,] [dog,,mouse] [dog,cat,] [dog,cat,mouse]
我需要这个适用于任何大小的数组。
这本质上是一个二进制计数器，其中数组索引表示位。 这大概让我使用一些按位操作来计算，但我看不到一个很好的方式将其转换为数组索引。
string[] source = new string[] { "dog", "cat", "mouse" }; for (int i = 0; i < Math.Pow(2, source.Length); i++) { string[] combination = new string[source.Length]; for (int j = 0; j < source.Length; j++) { if ((i & (1 << (source.Length - j - 1))) != 0) { combination[j] = source[j]; } } Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]); }
优雅？ 为什么不Linq呢。
public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source) { if (!source.Any()) return Enumerable.Repeat(Enumerable.Empty<T>(), 1); var element = source.Take(1); var haveNots = SubSetsOf(source.Skip(1)); var haves = haveNots.Select(set => element.Concat(set)); return haves.Concat(haveNots); }
您可以使用BitArray类轻松访问数字中的位：
string[] animals = { "Dog", "Cat", "Mouse" }; List<string[]> result = new List<string[]>(); int cnt = 1 << animals.Length; for (int i = 0; i < cnt; i++) { string[] item = new string[animals.Length]; BitArray b = new BitArray(i); for (int j = 0; j < item.Length; j++) { item[j] = b[j] ? animals[j] : null; } result.Add(item); }
static IEnumerable<IEnumerable<T>> GetSubsets<T>(IList<T> set) { var state = new BitArray(set.Count); do yield return Enumerable.Range(0, state.Count) .Select(i => state[i] ? set[i] : default(T)); while (Increment(state)); } static bool Increment(BitArray flags) { int x = flags.Count - 1; while (x >= 0 && flags[x]) flags[x--] = false ; if (x >= 0) flags[x] = true; return x >= 0; }
用法：
foreach(var strings in GetSubsets(new[] { "dog", "cat", "mouse" })) Console.WriteLine(string.Join(", ", strings.ToArray()));
这里有一个和David B的方法类似的解决scheme，但是如果真的需要用原始数量的元素（即使是空的）取回集合，也许更合适。
static public List<List<T>> GetSubsets<T>(IEnumerable<T> originalList) { if (originalList.Count() == 0) return new List<List<T>>() { new List<T>() }; var setsFound = new List<List<T>>(); foreach (var list in GetSubsets(originalList.Skip(1))) { setsFound.Add(originalList.Take(1).Concat(list).ToList()); setsFound.Add(new List<T>() { default(T) }.Concat(list).ToList()); } return setsFound; }
如果传递三个string的列表，您将返回八个列表，每个列表包含三个元素（但某些元素将为空）。
这是一个易于遵循的解决scheme：
private static void Test() { string[] test = new string[3] { "dog", "cat", "mouse" }; foreach (var x in Subsets(test)) Console.WriteLine("[{0}]", string.Join(",", x)); } public static IEnumerable<T[]> Subsets<T>(T[] source) { int max = 1 << source.Length; for (int i = 0; i < max; i++) { T[] combination = new T[source.Length]; for (int j = 0; j < source.Length; j++) { int tailIndex = source.Length - j - 1; combination[tailIndex] = ((i & (1 << j)) != 0) ? source[tailIndex] : default(T); } yield return combination; } }
古法的答案有我正在寻找的基本function，但是与之相符
BitArray b = new BitArray(i);
没有为我工作，它给了一个ArgumentOutOfRangeException。 这是我稍微调整和工作的代码：
string[] array = { "A", "B", "C","D" }; int count = 1 << array.Length; // 2^n for (int i = 0; i < count; i++) { string[] items = new string[array.Length]; BitArray b = new BitArray(BitConverter.GetBytes(i)); for (int bit = 0; bit < array.Length; bit++) { items[bit] = b[bit] ? array[bit] : ""; } Console.WriteLine(String.Join("",items)); }
我对C＃不是很熟悉，但我确定有这样的事情：
// input: Array A foreach S in AllSubsetsOf1ToN(A.Length): print (S.toArray().map(lambda x |> A[x]));
好的，我已经被告知上面的答案是行不通的。 如果你重视优雅而不是效率 ，我会尝试recursion，用我蹩脚的伪代码：
Array_Of_Sets subsets(Array a) { if (a.length == 0) return [new Set();] // emptyset return subsets(a[1:]) + subsets(a[1:]) . map(lambda x |> x.add a[0]) }
这是对Mehrdad解决scheme的一个小改变：
static IEnumerable<T[]> GetSubsets<T>(T[] set) { bool[] state = new bool[set.Length+1]; for (int x; !state[set.Length]; state[x] = true ) { yield return Enumerable.Range(0, state.Length) .Where(i => state[i]) .Select(i => set[i]) .ToArray(); for (x = 0; state[x]; state[x++] = false); } }
或与指针
static IEnumerable<T[]> GetSubsets<T>(T[] set) { bool[] state = new bool[set.Length+1]; for (bool *x; !state[set.Length]; *x = true ) { yield return Enumerable.Range(0, state.Length) .Where(i => state[i]) .Select(i => set[i]) .ToArray(); for (x = state; *x; *x++ = false); } }
