循环遍历数组的每个可能组合

Question

我试图循环遍历C#中依赖于大小的数组的每个组合,但不是顺序.例如:var states = ["NJ", "AK", "NY"];

一些组合可能是:

states = [];
states = ["NJ"];
states = ["NJ","NY"];
states = ["NY"];
states = ["NJ", "NY", "AK"];

......在我的情况下也是如此,states = ["NJ","NY"]并且states = ["NY","NJ"]是相同的,因为顺序并不重要.

有没有人对最有效的方法有任何想法？

Answer 1

以下两种方法的组合应该做你想要的.想法是如果项目的数量是n,那么子集的数量是2 ^ n.如果你从0迭代到2 ^ n - 1并查看二进制数字,你会得到每个项目的一个数字,如果数字是1那么你包括项目,如果它是0你没有.我在BigInteger这里使用的int只能用于少于32个项目的集合,并且long只能用于少于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;
    }
}

用以下代码

var states = new[] { "NJ", "AK", "NY" };

foreach (var subset in states.PowerSets())
{
    Console.WriteLine("[" + string.Join(",", subset.Select(s => "'" + s + "'")) + "]");
}

会给你这个输出.

[]
['NJ']
['AK']
['NJ','AK']
['NY']
['NJ','NY']
['AK','NY']
['NJ','AK','NY']