遍历HashSet中每个元素的两两组合

Question

如何遍历 HashSet 中每两个元素的组合一次？

foreach (var elt1 in hashSet) {
  foreach (var elt2 in hashSet) {
    ...
  }
}

以下代码可以遍历两个组合，但会重复遍历每个组合。我希望只遍历一次。

我认为在Python中很容易实现。在C＃中有没有办法实现？

示例：

输入hashSet：{1, 2, 3, 4}

遍历结果：(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

- Rok Povsic

---

将 HashSet 转换为数组并在数组上使用嵌套循环？ - Medinoc

可以做到，是的。有没有更简洁的方法？ - Rok Povsic

请您能否详细说明一下...也就是说，您的输入是什么样子的，输出会是什么，中间需要进行哪些操作，这样我们才能更好地了解整个事情的全貌。 - user240141

在我脑海中，我不认为如此。只有 ToArray()，For i 0 → size，For j i → size。 - Medinoc

@Eldritch Conundrum：我认为可读性不是最好的。我喜欢dasblinkenlight的MakeAllPairs()函数。 - Rok Povsic

Answer 1

C# 中没有内建的方法可以实现这个功能。由于 HashSet<T> 没有索引 ^*，你也不能通过两个循环实现。

如果这只是一次性的需求，最简单的解决方案是在 ToList() 或者 ToArray() 的结果上使用两个嵌套的循环，像这样：

var items = hashSet.ToList();
for (var i = 0 ; i != items.Count ; i++) {
    var a = items[i];
    for (var j = i+1 ; j != items.Count ; j++) {
        var b = items[i];
    }
}

如果你正在寻找可重用的内容，可以在 IEnumerable<T> 上创建一个扩展方法来生成所有配对：

static IEnumerable<Tuple<T,T>> MakeAllPairs<T>(this IEnumerable<T> data) {
    var items = data.ToList();
    for (var i = 0 ; i != items.Count ; i++) {
        var a = items[i];
        for (var j = i+1 ; j != items.Count ; j++) {
            var b = items[i];
            yield return Tuple.Create(a, b);
        }
    }
}

现在您可以在单个循环中迭代您的键值对：

foreach (var pair in hashSet.MakeAllPairs()) {
    Console.WriteLine("{0} {1}", pair.Item1, pair.Item2);
}

^* 在技术层面上，你可以使用来自Enumerable的ElementAt<T>(int)扩展，但在大数据集上执行会非常缓慢。

- Sergey Kalinichenko

Answer 2

我最初误读了问题。这是一个新的答案。

这是您想要的（如果基于索引工作是一种选择）。下面是解释：

string[] myArray = GetArray();

for (int i = 0; i < myArray.Length - 1; i++)
{
    var element1 = myArray[i];

    for(int j = i + 1; j < myArray.Length; j++)
    {
        var element2 = myArray[j];
        Console.WriteLine("{0} {1}", element1, element2);
    }
}

解释：假设有以下数组：

Apple, Banana, Coconut, Zucchini

当 i = 0 (苹果) 时，j 将会是 1 (香蕉)，然后是 2 (椰子)，接着是 3 (西葫芦)。

当 i = 1 (香蕉) 时，j 将会是 2 (椰子)，接着是 3 (西葫芦)。

以此类推...

基本上，你要确保 元素 j 总是在元素 i 前面。这意味着你已经有效地去掉了一半的可能性（j 在 i 的前面），这正是你想要的。

注意：如果你想使用相等的元素组（比如 苹果 + 苹果），第二个 for 循环需要改为：

    for(int j = i; j < myArray.Length; j++) //notice j = i instead of i + 1

- Flater

---

每个组合不仅意味着相邻的元素。 - Rok Povsic

我改变了我的答案。我完全误读了它。这个是正确的 :) - Flater

Answer 3

要返回所有排列组合（例如(1,2)和(2,1)），您可以使用SelectMany将集合与自身进行交叉连接：

 var hashSet = new HashSet<int>{1,2,3,4,5,6,7,8};
 foreach (var elt in hashSet.SelectMany(
                     x => hashSet.Select(y => new Tuple<int, int>(x, y))))
 {
    Debug.WriteLine("{0}-{1}", elt.Item1, elt.Item2);
 }

编辑: 如果您只想要唯一的组合（例如 (1,2) 而不是 (2,1)），那么在交叉连接期间只需添加一个过滤器即可只保留更大的值:

 var hashSet = new HashSet<int> { 1, 2, 3, 4, 5, 6, 7, 8 };
 foreach (var elt in hashSet.SelectMany(
                     x => hashSet.Where(y => y >= x)
                                 .Select(y => new Tuple<int, int>(x, y))))
 {
    Debug.WriteLine("{0}-{1}", elt.Item1, elt.Item2);
 }

- StuartLC

---

这并不能防止相同的组合发生两次，例如1+4和4+1。如果我理解正确，这正是OP想要的。 - Flater

OP的原始问题循环两次，从元素0开始，因此给出了所有排列组合。 - StuartLC

原帖引用：“...但是会迭代每个组合两次。我想只迭代一次。”这意味着元素的顺序不重要，1+4等于4+1，不应该为每个排列运行，而只应该为组合运行。 - Flater

我认为原帖作者正在寻找C(n, 2)的组合。 - Fung

@Fung：我也这么认为。不太确定那些符号了 :) - Flater

更新 - 也适用于组合。 - StuartLC

Answer 4

你可以直接在 HashSet 上使用索引。尝试这样做：

int int1, int2;
HashSet<int> hs = new HashSet<int>();
hs.Add(1);
hs.Add(2);
hs.Add(3);
for (int i = 0; i < hs.Count-1; i++) {
    int1 = hs.ElementAt<int>(i);
    for (int j = i + 1; j < hs.Count; j++)
    {
        int2 = hs.ElementAt<int>(j);
    }
}

- Zohar Peled