如何有效地检测 4 个整数变量的对称性？

Question

我想在 4 个整数变量 i,j,k 和 l 中找到对称性。对称性是：

所有四个数字都相等：XXXX，
三个数字相等：XXXY,XXYX,XYXX,YXXX
两对相等的数字：XXYY,XYXY,XYYX,...
一对相等的数字和两个不同的数字：XXYZ,XYXZ,XYZX,...
所有数字都不同。

某个非连续范围内的所有变量运行。我使用嵌套的 if else 语句。第一个 if 检查所有变量的不平等。如果不是，那么我有情况 1。下一个 if 检查是否有任何相等的对。如果不是，则情况 5。下一个 if 检查三个相等的数字。如果为真，则情况 2。否则，最后一个 if 检查两对相等的数字。如果为真，则为情况 3，否则为情况 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
 }

有更好的方法吗？我的意思是更好的性能，因为我必须进行数百万次此测试。

Answer 1

如果您能负担得起小型（64 字节）查找 table，您可以测试每对值并在用作索引的数字中为每个比较设置一个位 table，例如：

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

然后切换 return 值。您可以使用现有代码生成 table，方法是为每个比较替换一个位测试，或生成满足从 0 到 63 的每个位模式的虚拟 i j k l 值。

这种方法需要不断进行 6 次比较。请记住，对 4 个值进行排序需要 4 到 5 次比较（有 4！= 24 种可能的排序，每次比较产生 1 位信息）。但是你必须根据排序后的值进行测试。

使用查找 table 是否优于您当前的方法将取决于值的分布和内存访问时间等其他因素，您应该分析以确认。

Answer 2

更好的方法是使用地图：

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

如果您想将其扩展到超过 4 个选择，这种方法的可扩展性也会大大提高。

Answer 3

与 samgak 类似的想法，但不需要外部 table。只需计算所有匹配项的总和

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

并switch选择以下选项

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

同样，如前所述，您当前的代码在某些情况下可能更快。特别是如果最常见的情况是所有元素都相等的情况。

如何有效地检测 4 个整数变量的对称性？

How to detect symmetries in 4 integer variables efficiently?

c

c++

performance

integer

symmetry