CODEWITHSUNDEEP
c#algorithmlanguage-agnosticpermutation
j.i.h.
j.i.h.

Reputation: 827

Clean algorithm to generate all sets of the kind (0) to (0,1,2,3,4,5,6,7,8,9)

Basically, I'd like a set of sets that contains from (0..9), then (0, 1..9), (1, 2..9)..(8,9), and so on and so forth up until (0,1,2,3,4,5,6,7,8,9). I know this can be accomplished by nesting for loops in the manner below, but I'm wondering if there's a neater way of doing it?

Preferably something that could be accomplished within C#, but I'm interested in any algorithm.

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
                }
            }
        }
    }
}

Upvotes: 0

Views: 326

Answers (4)

plinth
plinth

Reputation: 49189

Why not treat this as bits and generate the set from the bits?

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;
}

and since I like the generic version above, let's make this generic too:

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;
    }
}

Upvotes: 2

konrad.kruczynski
konrad.kruczynski

Reputation: 47561

Using Dennis signature:

    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();
        }
    }

Upvotes: 0

singhiskng
singhiskng

Reputation: 511

here is a algorithm for generating sub-sets.

let you have a set S = [a,b,c,d,e,f].

and you want to generate all the subsets then length of the array containing all the sub-sets will be
2^n where n is number of elements in 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 will have every set you wanted or you can modify it to get new result.

Upvotes: 1

Dennis_E
Dennis_E

Reputation: 8894

I wrote this a while ago. It uses a Stack. It's generic, so it can be used for other sequences as well.

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

Upvotes: 3

Related Questions