5

相互に排他的で、スーパーセットのできるだけ多くの要素を含む、特定のセットのすべてのサブセットを見つけたいと考えています。ユーザーが排他性の意味を定義する場所:

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

少なくともexclusion(a, b) == exclusion(b, a)保持する場所。

そしてexclusion(a, b) == true保証されますa.Equals(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());
    }
}

このコードを、受け入れられた値を 1 つずつ移動するイテレータに変換する方法はありますか?

編集：

質問が少し不正確だったようです、申し訳ありません。私は実際に遅延実行用のジェネレーターを探していました。あなたがそれを呼び出すたびに、次の受け入れられたセットだけが計算されるように

4

2 に答える 2

2

基本的に、あなたがしたいことは、あなたが呼ぶたびに新しいセットを生み出すことで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;
        }
}

それはおそらく最も効率的な解決策ではありませんが、それは仕事を成し遂げます。

また、すべてのサブセットを1回だけ実行することを検討することもできます。そうすれば、finishedセットは必要なく、見つけたすべての結果を直接得ることができます。

于 2013-03-09T15:47:13.563 に答える