通过c生成器的最大独立子集集

本文关键字：独立 子集 通过 | 更新日期: 2023-09-27 18:03:08

我想找到给定集合的所有互斥子集，这些子集包含尽可能多的超集元素。用户定义排他性的含义：

bool exclusion<T>(T a, T b)

其中至少CCD_ 1成立。

如果a.Equals(b) == true ，则保证exclusion(a, b) == true

我的代码如下：

public static HashSet<HashSet<T>> MutuallyExclusive<T>(this IEnumerable<T> available, Func<T, T, bool> exclusion) {
    HashSet<HashSet<T>> finished = new HashSet<HashSet<T>>(new HashSetEquality<T>());
    Recursion<T>(available, new HashSet<T>(), finished, exclusion);
    return finished;
}
private static void Recursion<T>(IEnumerable<T> available, HashSet<T> accepted, HashSet<HashSet<T>> finished, Func<T, T, bool> exclusion) {
    if (!available.Any())
        finished.Add(accepted);
    else
        foreach (T a in available)
            Recursion<T>(available.Where(b => !exclusion(a, b)), new HashSet<T>(accepted) { a }, finished, exclusion);
}
private class HashSetEquality<T> : IEqualityComparer<HashSet<T>> {
    public bool Equals(HashSet<T> x, HashSet<T> y) {
        if (x.Count != y.Count)
            return false;
        return x.All(t => y.Contains(t));
    }
    public int GetHashCode(HashSet<T> obj) {
        return obj.Aggregate(0, (i, t) => i ^ t.GetHashCode());
    }
}

有没有办法把这个代码变成一个迭代器，一个接一个地遍历接受的值？

编辑：

对不起，我的问题似乎有点不准确。事实上，我正在寻找一个发电机，以解除强制执行。因此，每次调用它时，只计算下一个接受的集合

通过c生成器的最大独立子集集

基本上，您想要做的是每次调用finished.Add()并返回true时生成一个新集。

但由于递归，您还需要生成递归调用返回的所有值。你可以通过在一个循环中产生所有这些值来做到这一点：

public static IEnumerable<HashSet<T>> MutuallyExclusive<T>(
    this IEnumerable<T> available, Func<T, T, bool> exclusion)
{
    var finished = new HashSet<HashSet<T>>(new HashSetEquality<T>());
    return Recursion<T>(available, new HashSet<T>(), finished, exclusion);
}
private static IEnumerable<HashSet<T>> Recursion<T>(
    IEnumerable<T> available, HashSet<T> accepted, HashSet<HashSet<T>> finished,
    Func<T, T, bool> exclusion)
{
    if (!available.Any())
    {
        if (finished.Add(accepted))
            yield return finished;
    }
    else
        foreach (T a in available)
        {
            var results = Recursion<T>(
                available.Where(b => !exclusion(a, b)),
                new HashSet<T>(accepted) { a }, finished, exclusion);
            foreach (var set in results)
                yield return set;
        }
}

这可能不是最有效的解决方案，但它可以完成任务。

此外，您可能需要考虑只遍历每个子集一次。这样，您就不需要finished集合，并且可以直接生成您找到的所有结果。

您可以使用而不是return finished;

foreach (HashSet<T> set in finished)
    yield return set;

由于您正在制作生成器(我想这就是它们的名称？(，因此需要将MutuallyExclusive的签名从HashSet<HashSet<T>>更改为exclusion(a, b) == exclusion(b, a)0。所以基本上MutuallyExclusive看起来像：

public static IEnumerable<HashSet<T>> MutuallyExclusive<T>(this IEnumerable<T> available, Func<T, T, bool> exclusion)
{
    HashSet<HashSet<T>> finished = new HashSet<HashSet<T>>(new HashSetEquality<T>());
    Recursion<T>(available, new HashSet<T>(), finished, exclusion);
    foreach (HashSet<T> set in finished)
        yield return set;
}
相关文章：