How to Permute Pairs Across a Set in C#

algorithmsc

I am writing a bet settling app in C# and WinForms. I have 6 selections, 4 of them have won. I know that using the following formula from Excel:

=FACT(selections)/(FACT(selections-doubles))/FACT(doubles)

This is coded into my app and working well: I can work out how many possible doubles (e.g., AB, AC, AD, AE, BC, BD, BE, etc.) need to be resolved.

But what I can't figure out is how to do the actual calculation. How can I efficiently code it so that every combination of A, B, C, and D has been calculated?

All my efforts thus far on paper have proved to be ugly and verbose: is there an elegant solution to this problem?

Best Answer

I don't speak C#, but here's the general idea in C-like pseudocode:

items = {A, B, C, D, E}
for (i = 0; i < items.count-1; i++)
    for (j = i+1; j < items.count; j++) {
        doSomethingWithPair(items[i], items[j])
    }
}

In English, pick the first item and combine it with all the subsequent items. Then pick the next item and combine it with all subsequent items, and so on until you've combined the penultimate item with the ultimate item.

If order were important, i.e. you wanted permutations instead of combinations, pick both members of each pair from the full range of items. Change the outer loop so that it goes all the way to the end and the inner loop so that it starts from the beginning. Remember to check that i != j if you don't want permutations with replacement:

for (i = 0; i < items.count; i++) {
    for (j = 0; j < items.count; j++) {
        if (i == j) continue;        // avoid AA, BB, etc.
        doSomethingWithPair(items[i], items[j]);
    }
}
Related Topic