How to find subsets with exact length using linq lambda syntax

Question

Possible Duplicate:
Lists permutations (unknown number)

Lets say I have input of Range[1, 8]

{1,2,3,4,5,6,7,8}

and i want to find Subsets[%, {2}] (all subsets with exact length of 2)

{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {2, 3}, {2, 4}, 
 {2, 5}, {2, 6}, {2, 7}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, 
 {4, 5}, {4, 6}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {5, 8}, {6, 7}, {6, 8}, {7, 8}}

Tried:

var values = Enumerable.Range(1, 8);
var result = from v in values
             from v2 in values.Skip(v)
             select new[] { v, v2 };

LINQ and Lambda aren't necessarily the same thing. You can build an extension method pretty easily that takes a lambda expression (though in this case, what would the expression look like? Need more info) and then does the subset computations with a recursive function body. — Eli Gassert, Nov 09 '12 at 15:51
Joel Etherton > Well i can call Mathematica with `"Subsets["+list+", {2}]"`. http://reference.wolfram.com/mathematica/ref/Subsets.html — Margus, Nov 09 '12 at 15:54
What you've tried gives me the exact results you're looking for. What's the issue? — D Stanley, Nov 09 '12 at 16:18
@user1793607 The OP has shown the *combinations* as his desired output, not *permutations*. See wikipedia for the difference. — Servy, Nov 09 '12 at 16:39
@Margus can you explain what's wrong with code you tried? It brings exactly what you expect — Sergey Berezovskiy, Nov 09 '12 at 16:48

score 2 · Answer 1 · edited Nov 09 '12 at 16:41

2

var query = from a in Enumerable.Range(1, 8)
            from b in Enumerable.Range(a + 1, 8 - a)
            select String.Format("{{{0}, {1}}}", a, b);

foreach (string s in query)
{
    Console.Out.WriteLine(s);
}

edited Nov 09 '12 at 16:41

Sergey Berezovskiy

232,247
41
429
459

answered Nov 09 '12 at 16:08

Tyler Lee

2,736
13
24

This is a bit hacky though, as it doesn't work with any other input sizes or set sizes. – Servy Nov 09 '12 at 16:34
Can definitely be extended if needed. This answers the specific question asked. – Tyler Lee Nov 09 '12 at 16:46
It's actually non-trivial to extend it from a fixed number of items in the result set to a dynamic result set size. – Servy Nov 09 '12 at 16:52

score 2 · Accepted Answer · answered Nov 09 '12 at 16:33

2

Here is a function to find all combinations of an input sequence of a specified size:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> source, int n)
{
    if (n == 0)
        yield return Enumerable.Empty<T>();


    int count = 1;
    foreach (T item in source)
    {
        foreach (var innerSequence in source.Skip(count).Combinations(n - 1))
        {
            yield return new T[] { item }.Concat(innerSequence);
        }
        count++;
    }
}

So in your case you'd use it as:

var result = Enumerable.Range(1, 8).Combinations(2);

answered Nov 09 '12 at 16:33

Servy

202,030
26
332
449

What a great snippet. However it took me a moment to get that it is missing a `public static class ExtensionMethods` wrapper. – Margus Nov 09 '12 at 16:48
@Servy did you any performance testing? Your method is about 30 times slower than other two methods! I get no clue why it is so. – nawfal Nov 09 '12 at 17:15
@nawfal That wouldn't surprise me. This method covers the general case, the other methods hard coded in many of the details, in particular the size of the result set. Making that not fixed adds a lot of complexity to both the code, and inhibits many optimizations. Now, that said, there are implementations of the general case that are more efficient, but they're also much harder to understand conceptually. Finally, note that combinations scale horribly, even in the best case, so you won't be able to use this for large data sets regardless of the quality of your implementation. – Servy Nov 09 '12 at 17:18

nawfal · Answer 3 · 2012-11-09T17:07:59.700

1

var lst = Enumerable.Range(1, 8);
var result = lst.Join(lst, c => 1, c => 1, (i, j) => new[] { i, j })
        .Where(c => c[0] < c[1]);

Here I used the condition 1 == 1 to get the cross join of values in Enumerable.Range(1, 8) to get all possible combinations.

As noted in comments probably an easier way to generate a cross join is by:

var result = lst.SelectMany(_ => lst, (i, j) => new[] { i, j })
        .Where(c => c[0] < c[1]);

but is less readable to my eyes.

Please note that this is little less efficient compared to other methods as this first gets all the possible combinations and then trim down the unwanted. Nevertheless a simple one-liner.

edited Nov 09 '12 at 17:07

answered Nov 09 '12 at 16:28

nawfal

70,104
56
326
368

You can get a cross join through a simple `SelectMany` call with much less hassle. – Servy Nov 09 '12 at 16:43
@Servy I can not understand if that's what a SelectMany does from the documentation. Can you edit my answer and post it as an answer? – nawfal Nov 09 '12 at 16:47
Edited as requested. Also note that from an efficiency point of view it's probably better to just generate what you need, as the other posts do, rather than generating all permutations and trimming it down. – Servy Nov 09 '12 at 16:52
@Servy Yes I had noticed that. – nawfal Nov 09 '12 at 17:00

How to find subsets with exact length using linq lambda syntax

3 Answers3