Best way to enumerate all combinations

Question

Suppose I have the following list in any order:

S1 
R1 
R2 
S2
S3

I need to create a LIST where each "S" contains each "R" combination

Output:

S1 => R1
S1 => R2
S2 => R1
S2 => R2
S3 => R1
S3 => R2

what's the best way to achieve this? thanks

This sounds like 2 lists, not one. You want combinations of all elements in an S list with an R list. Thinking that way makes the job as easy as a nested loop. — Pranav Negandhi, Jul 07 '15 at 16:20
Parse list for R elements to move to another list, O(n). For each S remaining, build a dictionary that each S element points to same list with elements R. — huseyin tugrul buyukisik, Jul 07 '15 at 16:21
Sounds like "Cartesian product" (http://stackoverflow.com/questions/1741364/efficient-cartesian-product-algorithm) - not really sure if it is what you are asking for. — Alexei Levenkov, Jul 07 '15 at 16:27
sounds like MS SQL's "select * from table1, table2" to me, isn't it? or no? — ken lacoste, Jul 07 '15 at 16:32

Jacob · Accepted Answer · 2015-07-07T16:30:26.747

5

Try:

var byPrefix = list.GroupBy(i => i.First()).ToDictionary(g => g.Key, g => g);
var result = 
    from s in byPrefix['S']
    from r in byPrefix['R']
    select new { s, r };

edited Jul 07 '15 at 16:30

answered Jul 07 '15 at 16:28

Jacob

77,566
24
149
228

`SelectMany` to the rescue – leppie Jul 07 '15 at 16:29
1

`ToDictionary` allows the index access and avoids redundant iterations as well. – Jacob Jul 07 '15 at 16:34
Yeah, I realise this is tad harder than I thought without it :) – leppie Jul 07 '15 at 16:43

score 1 · Answer 2 · answered Jul 07 '15 at 16:27

As Pranav and huseyin mentioned, you just need to split into two lists and then use a nested foreach to loop through them.

var startingList = new List<string> { "S1", "R1", "R2", "S2", "S3" };
List<Tuple<string, string>> result = new List<Tuple<string, string>>();

foreach(var s in startingList.Where(x => x.StartsWith("S")).ToList())
{
    foreach(var r in startingList.Where(x => x.StartsWith("R")).ToList())
    {
        result.Add(new Tuple<string, string>(s, r));
    }
}

score 0 · Answer 3 · edited Jan 24 '20 at 17:24

If this is always static, I mean always two lists (or prefixes), you can do nested loops:

List<string> list = new List<string>();
list.Add("S1");
list.Add("R1");
list.Add("R2");
list.Add("S2");
list.Add("S3");

loop

foreach (var s in list.Where(l => l.StartsWith("S")))
{
    foreach (var r in list.Where(l => l.StartsWith("R")))
    {
        Console.WriteLine(string.Format("{0} => {1}", s, r));
    }
}

or:

list.Where(l => l.StartsWith("S"))
    .ToList()
    .ForEach(s => list.Where(l => l.StartsWith("R"))
                      .ToList()
                      .ForEach(r => Console.WriteLine(string.Format("{0} => {1}", s, r)))
            );

Instead of Console.WriteLine, you can add the result to another list.

score 0 · Answer 4 · answered Jul 07 '15 at 16:29

This is what I came up with, a mixture of array and enumerators:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = new string[] {
                "S1", 
                "R1", 
                "R2", 
                "S2",
                "S3"
            };
            foreach (var item in CombinationsOfSAndR(input)) 
            {
                Console.WriteLine("{0} -> {1}", item.Key, item.Value);
            }
            /* OUT:
            S1 -> R1
            S1 -> R2
            S2 -> R1
            S2 -> R2
            S3 -> R1
            S3 -> R2 */
        }
        static IEnumerable<KeyValuePair<string, string>> CombinationsOfSAndR(string[] input)
        {
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i].StartsWith("S"))
                {
                    for (int j = 0; j < input.Length; j++)
                    {
                        if (input[j].StartsWith("R"))
                        {
                            yield return new KeyValuePair<string, string>(input[i], input[j]);
                        }
                    }
                }
            }
        }
    }
}

Best way to enumerate all combinations

4 Answers4