How to detect symmetries in 4 integer variables efficiently?

Question

I want to find symmetries in 4 integer variables i,j,k and l . The symmetries are:

1. all four numbers are equal: XXXX,
2. three numbers are equal: XXXY,XXYX,XYXX,YXXX
3. two pairs of equal numbers: XXYY,XYXY,XYYX,...
4. one pair of equal numbers and two different numbers: XXYZ,XYXZ,XYZX,...
5. all numbers are different.

All variables run within a certain non continuous range. I use nested if else statements. The first if checks for inequality of all variables. If not, then I have case 1. The next if checks if there are any equal pairs. If not, then case 5. The next if checks for three equal numbers. If true, then case 2. Otherwise, the last if checks for two pairs of equal numbers. If true, then case 3, otherwise case 4.

  if(!(i==j && j==k && k==l)){
    if(i==j || i==k || i==l || j==k || j==l || k==l){
     if((i==j && j==k) || (i==j && j==l) || (i==k && k==l) || (j==k && k==l)){            ...//do something
     }else{
    if((i==j && k==l) || (i==k && j==l) || (i==l && j==k)){ 
...//do something
    }else{
     ...//do something
    }           
  }
     }else{
     ...//do something  
     } 
 }else{
  ...//do something
 }  

Is there better way do do this? I mean better in the sense of better performance, because I have to do this test millions of times.

Answer 1

Similar idea than samgak, but without the need of external table. Just count the sum of all matches

int count = (i==j) + (i==k) + (i==l) + (j==k) + (j==l) + (k==l);

and do switch with following choices

switch (count){
case 0: //All differenct
case 1: //One same
case 2: //Two different pairs
case 3: //Three same
case 6: //All are same
}

Again, as already mentioned, your current code might be faster in some cases. Especially if the most common case is the one where all the elements are equal.

Answer 2

If you can afford a small (64 byte) lookup table, you can test each pair of values and set a bit for each comparison in a number that you use as an index into your table, e.g:

int classifySymmetries(int i, int j, int k, int l)
{
     return table[(i == j) |
                  ((i == k) << 1) |
                  ((i == l) << 2) |
                  ((j == k) << 3) |
                  ((j == l) << 4) |
                  ((k == l) << 5)];
}

Then do a switch on the return value. You can use your existing code to generate the table, by substituting a bit test for each comparison, or generating dummy i j k l values that satisfy each bit pattern from 0 to 63.

This approach requires a constant 6 comparisons. Bear in mind that sorting 4 values requires between 4 and 5 comparisons (there are 4! = 24 possible orderings, and each comparison yields 1 bit of information). But then you have to do tests based on the sorted values on top of that.

Whether using a lookup table beats your current approach will depend on the distribution of values and other factors like memory access times, you should profile to confirm.

Answer 3

A better way is to use a map:

#include <iostream>
#include <map>
using namespace std;


int main()
{
    int i, j, k, l;
    cin >> i >> j >> k >> l;

    std::map<int, int> count;

    int outcomes[5] = { 0, 0, 0, 0, 0 };

    // Store the values in the map
    count[i]++;
    count[j]++;
    count[k]++;
    count[l]++;

    // tally types of outcome according to the map
    for(typename std::map<int, int>::iterator iter = count.begin(); iter != count.end(); ++iter)
    {
        outcomes[iter->second] ++;
    }

    // print out "1 of a kind" count, up to "4 of a kind"
    // this is just for visualization
    for (int i = 1; i <= 4; ++i)
    {
        cout << i << " of a kind = " << outcomes[i] << endl;
    }

    // your bit here, it checks on just the "outcomes" array
    if(outcomes[4] > 0) // 4 of a kind
    {
    }
    else if(outcomes[3] > 0) // 3 of a kind
    {
    }
    else if(outcomes[2] > 1) // two pair
    {
    }
    else if(outcomes[2] > 0) // one pair
    {
    }
    else // singles only
    {
    }

    cin.ignore();
    cin.get();

    return 0;
}

This approach would be far more extensible too, if you wanted to extend it beyond 4 choices.