使用LINQ从两个列表中获取所有可能的连接对

Question

给定列表Input = {A，B}和Output = {1，2，3，4}，我想要得到一个包含所有可能连接对{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}

规则:

• 每个组合代表2个连接。
• 每个连接由1个输入和1个输出表示。（例如，AB不可能）
• 如果一个输入或输出元素已经在前一个连接中使用，则不能在下一个连接中使用。（例如，{A1，B1}不可能）
• 输入可以包含n个元素（n>=2），输出可以包含m个元素（m>=2），但是组合总是由只有2个连接表示。

连接 {A1, B3} 的示例：

建议？

- ehh

---

输入始终包含2个元素，第一个元素连接到connection1，第二个元素连接到connection2？ - CodeFuller

输入可以包含n个元素（n≥2），输出可以包含m个元素（m≥2），但始终仅有两个连接。 - ehh

使用LINQ来做这件事会非常低效和复杂。 - Slai

提示：您需要三个运算符：（1）“选择两个，有序”，（2）“选择两个，无序”，以及（3）使用Select的笛卡尔积。 您想要的输出是这三个运算符的组合； 您看到了吗？ 您能实现这三个运算符然后将它们组合起来吗？ - Eric Lippert

Answer 1

更新的回答

这应该可以解决问题：

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}}}");
        }
    }
}

您需要LINQ to Objects中类似于交叉连接的方法，它只是循环遍历两个列表的内容而没有任何条件去限制结果集。

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

将为您列出所有成对元组。

在您的情况下，您似乎想要所有成对的成对：给定输入和输出的所有组合，然后获取输入和输出的所有组合的成对。

这只是通过使用第二个输入输出组合列表扩展上述内容的一个例子。

// 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();

结果将是一个 ValueTuple<string, string> 列表。

- Richard

---

问题在于我会得到输入连接到输入的连接，例如{A1，A2}。 - ehh

@ehh 你需要更好地定义你的问题，以清楚表明哪些组合是允许的。目前问题所表示的意思是"A1"作为输入A转换成输出1，那么输入到输入的组合应该是"AA"或"AB"。 - Richard

我更好地解释了问题并写了一些规则。请查看我的编辑。 - ehh

Answer 2

Richard的更新答案很优雅，可能是最适合您需求的，但我建议使用组合数学的另一种想法。（并且还使用函数式linq，这在我看来更容易调试和维护）。

思路如下：

1. 获取所有有效的输入组合（长度为2）
2. 获取所有有效的输出变化（长度为2）
3. 将所有有效的输入与所有输出变化组合。

使用预先制作的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 })
    );

要将输入/输出格式转换为单个字符串，您可以使用类似以下代码：

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

注意！还请注意，这种方法使您能够解决寻找N个连接而不仅仅是2个的更广泛问题。

- Imre Pühvel

Answer 3

我已经根据您提供的示例编写了一个单元测试和一个可工作的实现：

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);
    }
}

- Tao Gómez Gil

---

我看到你添加了我们可以拥有两个以上输入的信息。在这种情况下，这段代码是不够的。 - Tao Gómez Gil

运行完美，但你是对的，它不能处理超过2个输入。 - ehh

Answer 4

看到您已经澄清了可能会有两个以上的输入，我编写了一个修改后的算法，与之前相同的单元测试和一个新的测试：

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);
    }
}

- Tao Gómez Gil