Using LINQ get all possible pair of connections from two lists

Question

Given lists Input = {A, B} and Output = {1, 2, 3, 4 }, I want to get a new list that contains all possible pair of connections {connection1,connection2} :

connections = {A1, B2}, 
         {A1, B3}, 
         {A1, B4}, 
         {A2, B1},
         {A2, B3}, 
         {A2, B4}, 
         {A3, B1},
         {A3, B2},
         {A3, B4}, 
         {A4, B1},
         {A4, B2},
         {A4, B3}

Rules:

• Each combination represents a couple of 2 connections.
• Each connection is represented by 1 input and 1 output. (for example, AB is not possible)
• If an input or output element is already used from the previous connection then it can't be used in the next one. (for example, {A1,B1} is not possible)
• Input can contain n elements (n>=2) and Output can contain m elements (m>=2) but the combination is always represented by only 2 connections.

Illustration of connection {A1, B3}

Suggestions?

Answer 1

Updated Answer

This should do it:

using System.Linq;
using static System.Console;

class Program {
    static void Main(string[] args) {
        var inputs = new[] { "A", "B", "C" };
        var outputs = new[] { "1", "2", "3", "4" };

        var res = from i1 in inputs
                  from i2 in inputs
                  where i1 != i2
                  from o1 in outputs
                  from o2 in outputs
                  where o1 != o2
                  let c1 = i1 + o1
                  let c2 = i2 + o2
                  // Avoid {x,y} and {y,x} in result.
                  where c1.CompareTo(c2) < 0
                  select (first: c1, second: c2);

        foreach (var r in res) {
            WriteLine($"{{{r.first}, {r.second}}}");
        }
    }
}

Original Answer

You need the LINQ to Objects equivalent of a cross join, which is just looping over the contents of both lists without any conditions to limit the set of results.

var allPairs = (from a in ListA
                from b in ListB
                select (a, b)
               ).ToList();

Will give you a list of all pairs as tuples.

In your case you seem to want all pairs of pairs: given all combinations of input and output then get all pairs of combinations on input and output.

Which is just a case of expanding the above with a second combination of the list of all input-output combinations.

// Assume `Input` and `Output` and enumerables of string
var inputOutputPairs = (from ip in Input
                        from op in Output
                        select ip + op
                       ).ToList();

var result = (from left in inputOutputPairs
              from right in inputOutputPairs
              select (left, right)
              // To avoid duplicates like ("A4","A4") include this:
              // where left != right
             ).ToList();

And the result will be a list of ValueTuple<string, string>.

Answer 2

Richard's updated answer is elegant and probably the best fit for your needs, but I suggest an alternative idea using combinatorics. (and also using function-style linq which is imho a lot easier to debug and maintain).

The idea is:

1. get all valid input combinations (of length 2)
2. get all valid output variations (of length 2)
3. combine all valid inputs with all output variations.

Example implementation using a pre-baked combinatorics package from NuGet:

var Input = new[] { "A", "B"};
var Output = new[] { "1", "2", "3", "4" };
int maxConnections = 2;

var validInputs = new Combinations<String>(Input, maxConnections);
var validOutputs = new Variations<String>(Output, maxConnections);
var connectionsets = validInputs
    .SelectMany(ins => validOutputs
        .Select(outs => new { Ins = ins, Outs = outs })
    );

To get the connection from the format of ins/outs to single string, you could use something along the lines of :

String.Join(",", set.Ins.Select((input, i) => input + set.Outs.Skip(i).First()));

NB! Also note that this approach enables you to solve a bit wider question of finding N connections instead of just 2.