Iterate every combination of two elements in HashSet

Question

How could I iterate through each combination of two elements in a HashSet once?

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

This would iterate the combinations of two but would iterate each combination TWICE. I'd like to do it once.

I think it's easy to do in Python. Is there any way to do it in C#?

Sample:

input hashSet: { 1, 2, 3, 4 }

iterate through: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

Answer 1

There is no built-in method to do this in C#. Since HashSet<T> is not indexed ^*, you cannot do it with two loops either.

If this is a one-time deal, the simplest solution is to make two nested loops on the results of ToList() or ToArray(), like this:

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

If you are looking for something reusable, make an extension method on IEnumerable<T> that produces all pairs:

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

Now you can iterate your pairs in a single loop:

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

^* Technically, you could use ElementAt<T>(int) extension from Enumerable, but that would be very slow on large sets.

Answer 2

I misread the question originally. This is a new answer

This is what you want (if working index-based is an option). Explanation is below

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

Explanation: Assume the following array:

Apple, Banana, Coconut, Zucchini

When i = 0 (Apple), j will be 1 (Banana), then 2 (Coconut), then 3 (Zucchini)

When i = 1 (Banana), j will be 2 (Coconut), then 3 (Zucchini).

And so on...

Basically, you are making sure element j is always ahead of element i. This means you've effectively removed half of the possibilities (where j would be before i), which is what you wanted.

Note: if you want to use sets of equal elements (Apple + Apple), the second for loop needs to change to:

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

Answer 3

You can work with indexes directly on the HashSet. Try this:

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

Answer 4

To return all permutations (viz (1,2) and (2,1)), you can cross join the set with itself using 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);
 }

Edit: If you just want the unique combinations (viz (1,2) but not (2,1)) then just add a filter only larger values during the cross join:

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