在列表中将每个元素与其他每个元素进行比较

Question

什么是编写控制结构的最佳方式，该控制结构将在列表中迭代每个2元组合？

例如：

{0,1,2}

我希望一块代码能够运行三次，分别在以下三个时间点：

{0,1}
{1,2}
{0,2}

我尝试了以下

foreach (int i in input)
{
    foreach (int j in input.Where(o => o != i))
    {
        //Execute code
    }
}

然而，当列表中有两个相同元素时，这种方法将不起作用。使用

{0,2,0}

我仍然想要比较元素 0 和 0。值是无关紧要的。

- Wilson

---

你对这些配对中的每一个都在做什么？你和Jon的解决方案都是O(n平方) 的。根据你所做的事情，可能会有O(n) 的解决方案。（例如，在C#编译器中，您需要比较重载解析问题中的每一对方法，以确定最佳唯一方法；即使更好方法的关系是不传递的，也有O(n)算法可用。） - Eric Lippert

Answer 1

听起来您可能需要类似这样的东西：

for (int i = 0; i < list.Count - 1; i++)
{
    for (int j = i + 1; j < list.Count; j++)
    {
        // Use list[i] and list[j]
    }
}

使用LINQ绝对可以做到这一点：

var pairs = from i in Enumerable.Range(0, list.Count - 1)
            from j in Enumerable.Range(i + 1, list.Count - i - 1)
            select Tuple.Create(list[i], list[j]);

我不确定它是否更清晰了...

编辑：另一种较低效但可能更清晰的选择：

var pairs = from i in Enumerable.Range(0, list.Count - 1)
            let x = list[i]
            from y in list.Skip(i + 1)
            select Tuple.Create(x, y);

- Jon Skeet

---

完美，比我想象的简单得多。我会尽快接受。谢谢你，但你是对的，LINQ解决方案要不易读得多，而且很可能更慢。 - Wilson

谢谢，第一个版本（for循环）非常好用！ 然而，我认为第二个版本（LINQ）有些问题，因为它抛出了一个IndexOutOfRange异常（两个版本之间的索引处理略有不同，但我没有时间去弄清楚如何修复它）。 - Ishikawa

@Ishikawa：我认为这是一个偏移量错误，我已经修复了。 - Jon Skeet

Answer 2

如果您使用的是 C# 7 或更高版本，您可以利用 ValueTuple 类型。它提供了更好的可用性和性能。

public static IEnumerable<(T, T)> GetAllPairs<T>(IList<T> source)
{
    return source.SelectMany((_, i) => source.Where((_, j) => i < j),
        (x, y) => (x, y));
}

使用示例：

foreach ((int x, int y) in GetAllPairs(new[] { 0, 1, 2 }))
{
    // Execute code
    Console.WriteLine($"Pair: {x}, {y}");
}

输出：

Pair: 0, 1
Pair: 0, 2
Pair: 1, 2

- Theodor Zoulias