How can I get all subsets of a set that respect the order

Question

I'm looking for a C# example that will give me all subsets of a set while respecting the order.

For example I have A,B and would like:

A
B
AB
BA

Please note that for my purpose AB != BA.

The solution should be generic for any input type:

List<List<T>> GetSubsets<T>(List<T> originalSet)

I've come across some great solutions using bitwise manipulation for AB == BA (e.g Generate all combinations for a list of strings) but so far I have failed to find anything to solve what I described above.

Any tips/pointers would be much appreciated!

I think your problem statement is backwards. You want to respect order, not ignore it. — Raymond Chen, Mar 17 '15 at 02:08

score 1 · Answer 1 · answered Mar 17 '15 at 02:02

You can do it recursively.

Put the items in a set, and make an empty list containing the items in a subset. Then call your recursive method that populates the list of lists.

On each recursive invocation start by adding the items that you have collected so far to the list of result lists. Then for each item remaining in the set of items do the following:

Remove the item from the remaining set
Add the item to the list containing the partial subset
Make a recursive invocation
Remove the item from the partial subset
Add the item back to the remaining set.

Here is a simple implementation in C#:

static void CollectAll(ISet<String> remaining, IList<string> soFar, List<List<string>> all) {
    if (soFar.Count != 0) {
        all.Add(soFar.ToList());
    }
    foreach (var item in remaining.ToList()) {
        remaining.Remove(item);
        soFar.Add(item);
        CollectAll(remaining, soFar, all);
        soFar.Remove(item);
        remaining.Add(item);
    }
}

Demo.

score 1 · Accepted Answer · edited May 23 '17 at 11:56

GetPermutations() is ref. from https://stackoverflow.com/a/10630026/1287352

public static List<List<T>> PermutationOf<T>(HashSet<T> set)
{
    var result = new List<List<T>>();
    for (var length = 1; length <= set.Count; length++)
    {
        result.AddRange(GetPermutations<T>(set, length).Select(i => i.ToList()));
    }
    return result;
}

private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
        (t1, t2) => t1.Concat(new T[] { t2 }));
}

Usage:

PermutationOf(new HashSet<Guid>() { Guid.NewGuid(), Guid.NewGuid(), Guid.NewGuid() })
PermutationOf(new HashSet<String>() { "A", "B", "C" })

Result:

A
B
C
A, B
A, C
B, A
B, C
C, A
C, B
A, B, C
A, C, B
B, A, C
B, C, A
C, A, B
C, B, A

How can I get all subsets of a set that respect the order

2 Answers2

Linked