0
\$\begingroup\$

It's hard to choose the correct title for this question, so let's see if I am able to better convey here what I am in search for. If the title is too far away, suggestions are welcome and I can edit it or put a new question.

So, what I am trying to do is the following. I have the following set of values: A=[a1,a2....a100]. Now, suppose I want to loop trough them to check something for each possible pair of these values but without repetition and avoiding to check a value against itself.

It means that we start with a1 and check it against a2, then a3, then a4, until checking it against a100. Next, we start with a2, but we do not check it against a1 because that was already checked. We go directly to check a2 against a3, then a4, until a100. Next, we start with a3 and check it directly agains a4, then a5, and so on. The idea is that there will be 100+99+98+97...+1 checks, instead of 100^2 checks.

A naïve way of doing that would be to use two loops, one nested in the other, both going trough all the values of A. However, after the main parent loop completes each iteration, it stores the current iterated value in a list. So, when the child nested loop starts it checks if its currently iterated value is already on that list - if it is, the nested loop breaks.

However, it is very likely that this is not a very efficient way of doing that, since one would have to create a list, add to the list every iteration of the first loop and search the list every iteration of the second loop. Considering that I will be dealing with enormous amount of values in A, not only 100, that is real concern.

So, what are the most efficient ways one can do that kind of pair-wise comparison without repetition? I can handle both C# and Javascript. Many thanks.

\$\endgroup\$

closed as off-topic by Seth Battin, Tom 'Blue' Piddock, congusbongus, Josh Oct 26 '15 at 15:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions that aren't specific to game development are off-topic here, but can be asked on Stack Overflow. A good rule of thumb is to ask yourself "would a professional game developer give me a better/different/more specific answer to this question than other programmers?"" – Seth Battin, Tom 'Blue' Piddock, congusbongus, Josh
If this question can be reworded to fit the rules in the help center, please edit the question.

1
\$\begingroup\$

Something like this, perhaps?

private void CompareList(List<foo> listToCompare)
{
     for(int i = 0; i < listToCompare.Length - 1; i++)
     {
          var item1 = listToCompare[i];
          for(int j =i+1; j < listToCompare.Length; j++)
          {       
              var item2 = listToCompare[j];

              DoWhateverComparison(item1, item2);
          }
     }
}

Might need to add some index/null checks, I haven't run the code.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's worth pointing out that in your i for loop's comparison, you'd only need to go until listToCompare.length - 1 that way there's room for j's i+1 without overflowing. \$\endgroup\$ – Corey Ogburn Oct 1 '15 at 21:20
  • \$\begingroup\$ Ha, that's pretty much what I have been sort of doing, but indeed in a more elegant and efficient form. It's very concise and quite a bit faster than mine. Thanks! \$\endgroup\$ – MAnd Oct 1 '15 at 22:22
  • \$\begingroup\$ @MAnd if you want something fancy, convert it to extension method on Enumerable<T>: public static void ForEachPair<T>(this IEnumerable<T> list, Action<T,T> action) and use it like myList.ForEachPair((i1, i2) => {/*do whatever you want here with i1 a i2*/});. \$\endgroup\$ – wondra Oct 2 '15 at 15:26
  • \$\begingroup\$ @wondra, although there is no reason to expect that fancier approach to be better performance-wise, it certainly is even more elegant. Thanks. \$\endgroup\$ – MAnd Oct 6 '15 at 9:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.