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?

Input always contains 2 elements and 1st goes to connection1, 2nd goes to connection2? — CodeFuller, Nov 19 '17 at 10:38
Input can contain n elements (n>=2) and Output can contain m elements (m>=2) but always 2 connections only — ehh, Nov 19 '17 at 10:51
That will be pretty inefficient and convoluted with LINQ. https://stackoverflow.com/questions/1952153/what-is-the-best-way-to-find-all-combinations-of-items-in-an-array — Slai, Nov 19 '17 at 13:35
Hint: you need *three* operators: (1) "choose two, in order", (2) "choose two, either order", and (3) Cartesian product with Select. Your desired output is the composition of these three operators; do you see how? Can you implement each of those three operators and then compose them? — Eric Lippert, Nov 19 '17 at 16:54

Richard · Accepted Answer · 2017-11-19T16:28:07.737

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

The problem with that is that I will get connections of input connected to input, for example {A1, A2} — ehh, Nov 19 '17 at 10:56
@ehh You'll need to better define your problem to be clear what combinations are allowed. As the question stands "A1" is input A to output 1, so input to input would be "AA" or "AB", — Richard, Nov 19 '17 at 10:59
I've better explains the problem and wrote some rules. Please see my edit — ehh, Nov 19 '17 at 11:15

Imre Pühvel · Answer 2 · 2017-11-19T23:36:08.583

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:

get all valid input combinations (of length 2)
get all valid output variations (of length 2)
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.

score 1 · Answer 3 · answered Nov 19 '17 at 11:22

I've written an unit test with the example you provide and a working implementation:

public static class PairsOfConnections
{
    public static IEnumerable<Tuple<string, string>> GetAllPairsOfConnections(string[] input, string[] output)
    {
        var connectionsFromFirstInput = output.Select(o => new { Input = input[0], Output = o });
        var connectionsFromSecondInput = output.Select(o => new { Input = input[1], Output = o }).ToList();

        return from a in connectionsFromFirstInput
               from b in connectionsFromSecondInput
               where a.Output != b.Output
               select new Tuple<string, string>(a.Input + a.Output, b.Input + b.Output);
    }
}

public class PairsOfConnectionsTests
{
    [Test]
    public void TestGetAllPairsOfConnections()
    {
        string[] input = { "A", "B" };
        string[] output = { "1", "2", "3", "4" };

        IEnumerable<Tuple<string, string>> result = PairsOfConnections.GetAllPairsOfConnections(input, output);

        var expected = new List<Tuple<string, string>>
        {
            new Tuple<string, string>("A1","B2"),
            new Tuple<string, string>("A1","B3"),
            new Tuple<string, string>("A1","B4"),
            new Tuple<string, string>("A2","B1"),
            new Tuple<string, string>("A2","B3"),
            new Tuple<string, string>("A2","B4"),
            new Tuple<string, string>("A3","B1"),
            new Tuple<string, string>("A3","B2"),
            new Tuple<string, string>("A3","B4"),
            new Tuple<string, string>("A4","B1"),
            new Tuple<string, string>("A4","B2"),
            new Tuple<string, string>("A4","B3")
        };
        CollectionAssert.AreEquivalent(expected, result);
    }
}

I see you have added the information that we can have more than 2 inputs. In that case, this code is not enough. — Tao Gómez Gil, Nov 19 '17 at 11:23
Works perfectly but you are right, it will not work for more than 2 inputs — ehh, Nov 19 '17 at 11:35

score 0 · Answer 4 · answered Nov 19 '17 at 16:02

Seeing that you have clarified that there can be more than two inputs, I've written a modified algorithm, with the same unit test as before, and a new one:

public static class PairsOfConnections
{
    public static IEnumerable<Tuple<string, string>> GetAllPairsOfConnections(string[] inputs, string[] outputs)
    {
        var connectionsFromFirstInput = outputs.Select(o => new { Input = inputs[0], Output = o }).ToList();

        var result = new List<Tuple<string, string>>();
        foreach (string input in inputs.Skip(1))
        {
            var connectionsFromNextInput = outputs.Select(output => new { Input = input, Output = output }).ToList();
            IEnumerable<Tuple<string, string>> pairs = from a in connectionsFromFirstInput
                        from b in connectionsFromNextInput
                        where a.Output != b.Output
                        select new Tuple<string, string>(a.Input + a.Output, b.Input + b.Output);

            result.AddRange(pairs);
        }

        return result;
    }
}

public class PairsOfConnectionsTests
{
    [Test]
    public void TestGetAllPairsOfConnections_WithTwoInputs()
    {
        string[] input = { "A", "B" };
        string[] output = { "1", "2", "3", "4" };

        IEnumerable<Tuple<string, string>> result = PairsOfConnections.GetAllPairsOfConnections(input, output);

        var expected = new List<Tuple<string, string>>
        {
            new Tuple<string, string>("A1","B2"),
            new Tuple<string, string>("A1","B3"),
            new Tuple<string, string>("A1","B4"),
            new Tuple<string, string>("A2","B1"),
            new Tuple<string, string>("A2","B3"),
            new Tuple<string, string>("A2","B4"),
            new Tuple<string, string>("A3","B1"),
            new Tuple<string, string>("A3","B2"),
            new Tuple<string, string>("A3","B4"),
            new Tuple<string, string>("A4","B1"),
            new Tuple<string, string>("A4","B2"),
            new Tuple<string, string>("A4","B3")
        };
        CollectionAssert.AreEquivalent(expected, result);
    }

    [Test]
    public void TestGetAllPairsOfConnections_WithThreeInputs()
    {
        string[] input = { "A", "B", "C" };
        string[] output = { "1", "2", "3" };

        IEnumerable<Tuple<string, string>> result = PairsOfConnections.GetAllPairsOfConnections(input, output);

        var expected = new List<Tuple<string, string>>
        {
            new Tuple<string, string>("A1","B2"),
            new Tuple<string, string>("A1","B3"),
            new Tuple<string, string>("A1","C2"),
            new Tuple<string, string>("A1","C3"),
            new Tuple<string, string>("A2","B1"),
            new Tuple<string, string>("A2","B3"),
            new Tuple<string, string>("A2","C1"),
            new Tuple<string, string>("A2","C3"),
            new Tuple<string, string>("A3","B1"),
            new Tuple<string, string>("A3","B2"),
            new Tuple<string, string>("A3","C1"),
            new Tuple<string, string>("A3","C2"),
        };
        CollectionAssert.AreEquivalent(expected, result);
    }
}

Using LINQ get all possible pair of connections from two lists

4 Answers4