清洁算法生成 (0) 到 (0,1,2,3,4,5,6,7,8,9) 类型的所有集合

Question

基本上，我想要一组包含 (0..9)、然后 (0, 1..9)、(1, 2..9)..(8,9) 等的集合依此类推，直到 (0,1,2,3,4,5,6,7,8,9)。我知道这可以通过以下方式嵌套 for 循环来完成，但我想知道是否有更简洁的方法？

最好是可以在 C# 中完成的东西，但我对任何算法都感兴趣。

for (int i = 0; i < max; i++) {
    yield {i};
    for (int j = i + 1; j < max; j++) {
        yield {i, j};
        for (int k = j + 1; k < max; k++) {
            yield {i, j, k};
            for (int l = k + 1; l < max; l++) {
                yield {i, j, k, l};
                for (int m = l + 1; m < max; m++) {
                    yield {i, j, k, l, m};
                    // And so on and so forth
                }
            }
        }
    }
}

Answer 1

这是我不久前写的。它使用堆栈。它是通用的，因此也可以用于其他序列。

static IEnumerable<T[]> CombinationsAnyLength<T>(params T[] values)
{
    Stack<int> stack = new Stack<int>(values.Length);
    int i = 0;
    while (stack.Count > 0 || i < values.Length) {
        if (i < values.Length) {
            stack.Push(i++);
            int c = stack.Count;
            T[] result = new T[c];
            foreach (var index in stack) result[--c] = values[index];
            yield return result;
        } else {
            i = stack.Pop() + 1;
            if (stack.Count > 0) i = stack.Pop() + 1;
        }
    }
}

CombinationsAnyLength(1, 2, 3, 4) outputs:

1 12 123 1234 124 13 134 14 2 23 234 24 3 34 4

Answer 2

为什么不将其视为位并从位生成集合？

IEnumerable<List<int>> MakeSets()
{
    // count from 1 to 2^10 - 1 (if you want the empty set, start at 0
    for (uint i=1; i < (1 << 10); i++) 
    {
        // enumerate the bits as elements in a set
        List<int> set = BitsIn(i);
        yield return set;
    }
}

List<int> MakeSet(uint i)
{
    List<int> set = new List<int>();
    // this will give you values from 0..max
    // if you want 1, start with 1
    // if you want non-integers, pass in an array of values and index into that
    int val = 0;
    // for every bit in i
    while (i != 0)
    {
        // add the val if the corresponding bit is set
        if ((i & 1) != 0) set.Add(val);
        i = i >> 1;
        val++;
    }
    return set;
}

由于我喜欢上面的通用版本，所以我们也将其设为通用版本：

IEnumerable<List<T>> MakeSets(params T[] values)
{
    if (values.Length > 63) 
        throw new IllegalArgumentException("63 is the limit");

    for (ulong i = i; i < (1 << (values.Length + 1); i++) 
    {
        List<T> set = new List<T>();
        int val = 0;
        ulong j = i;

        while (j != 0) 
        {
            if ((j & 1) != 0) set.Add(values[val]);
            j = j >> 1;
            val++;
        }

        yield return set;
    }
}

Answer 3

这是生成子集的算法。

让你拥有一套

S = [a,b,c,d,e,f]

。

并且您想要生成所有子集，那么包含所有子集的数组的长度将为

2^n

，其中

n

是

S

中的元素数量。

int A = [] //  array containing all sub-sets
for i = 0 --- 2^n
    x = binary(i) // like for i = 5 -> x = '000101' where x is a string of n digits.
    ns = []            // new array
    for j = 0 --- n
        if x[j] == '1'
            push S[j] into ns array
    push ns into A
return A

A 将拥有您想要的每组，或者您可以修改它以获得新结果。

Answer 4

使用丹尼斯签名：

    public static IEnumerable<T[]> CombinationsAnyLength<T>(params T[] values)
    {
        for(var i = 0; i < (1 << values.Length); i++)
        {
            var result = new List<T>();
            for(var j = 0; j < values.Length; j++)
            {
                if(((1 << j) & i) != 0)
                {
                    result.Add(values[j]);
                }
            }
            yield return result.ToArray();
        }
    }