我怎样才能得到一组遵守顺序的所有子集

Question

我正在寻找一个 C# 示例，它会在遵守顺序的同时为我提供集合的所有子集。

例如我有 A,B 并且想要：

A
B
AB
BA

请注意，为了我的目的 AB != BA。

该解决方案应该对任何输入类型都是通用的：

List<List<T>> GetSubsets<T>(List<T> originalSet)

我遇到了一些使用 AB == BA 的按位操作的很好的解决方案（例如 Generate all combinations for a list of strings），但到目前为止我还没有找到任何解决我上面描述的问题的方法。

任何 tips/pointers 将不胜感激！

Answer 1

你可以递归地做。

将项目放在一个集合中，并制作一个包含子集中项目的空列表。然后调用填充列表列表的递归方法。

在每次递归调用时，首先将您到目前为止收集的项目添加到结果列表列表中。然后对项目集中剩余的每个项目执行以下操作：

从剩余的集合中删除项目
将项目添加到包含部分子集的列表中
进行递归调用
从部分子集中删除项目
将项目添加回剩余集合。

这是一个简单的 C# 实现：

static void CollectAll(ISet<String> remaining, IList<string> soFar, List<List<string>> all) {
    if (soFar.Count != 0) {
        all.Add(soFar.ToList());
    }
    foreach (var item in remaining.ToList()) {
        remaining.Remove(item);
        soFar.Add(item);
        CollectAll(remaining, soFar, all);
        soFar.Remove(item);
        remaining.Add(item);
    }
}

Demo.

Answer 2

GetPermutations() 是参考。来自

public static List<List<T>> PermutationOf<T>(HashSet<T> set)
{
    var result = new List<List<T>>();
    for (var length = 1; length <= set.Count; length++)
    {
        result.AddRange(GetPermutations<T>(set, length).Select(i => i.ToList()));
    }
    return result;
}

private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
        (t1, t2) => t1.Concat(new T[] { t2 }));
}

用法：

PermutationOf(new HashSet<Guid>() { Guid.NewGuid(), Guid.NewGuid(), Guid.NewGuid() })
PermutationOf(new HashSet<String>() { "A", "B", "C" })

结果：

A
B
C
A, B
A, C
B, A
B, C
C, A
C, B
A, B, C
A, C, B
B, A, C
B, C, A
C, A, B
C, B, A

我怎样才能得到一组遵守顺序的所有子集

How can I get all subsets of a set that respect the order

c#

algorithm

subset