c++ - 在 C++ 中查找等价类数量的有效方法

Question

假设我们有一个整数数组。 A[n]，例如

 A[11]={10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

和一个素数列表，例如 B[k]

 B[2]={3, 5}

对于B[k]中的每一个元素b_i，我们找出A[n]中能被它整除的元素并组合成一个等价类，如果A[n]中的某个元素不能被任何整除B[k]中的元素，那么它就是一个由单个元素组成的等价类。例如，在上面的例子中，等价类是

 {12, 15, 18}
 {10, 15, 20}
 {11}
 {13}
 {14}
 {16}
 {17}
 {19}

(重复 15，因为它可以同时被 3 和 5 整除)，其中第一个等价类由 A[n] 中可被 3 整除的数字组成，第二个是可被 5 整除的数字，其余是共同的元素-素数为 3 和 5。基本上，给定 A[n] 和 B[k]，我想计算可以创建多少个等价集，在上面的例子中，它是 8。

我想出的是:

   for(j=0; j<n; j++){
       check[j]=true;
   }

   for(i=0; i<k; i++){
       helper=0;
       for(j=0; j<n; j++){
           if(check[j]==true){
               if(A[j]%B[i]==0){
                   check[j]==false;
                   helper++;
               }
           }
       }

       if(helper>0){
           count++;
       }
   }

   for(j=0; j<n; j++){
       if(check[j]==true){
           count++;
       }
   }

check 是 bool 数组，如果它已经属于某个等价类则返回 false，如果它还不属于某个等价类则返回 true。这计算了可被 B[k] 中的元素整除的等价集的数量，但是现在，我不确定如何处理单例集，因为检查数组成员在循环后都被重新设置为 true。

(我试过了

   for(j=0; j<n; j++){
      if(check[j]==true){
          count++;
      }
   }

在上面的循环之后，但它只将 n 添加到计数中)

有人可以帮我解决这个问题吗？有没有更有效的方法呢？另外，我应该如何处理单例集？

谢谢。

附言。由于 15 在 2 组中重复，因此从技术上讲它不是等价类。对不起。

Answer 1

使用标准容器重写的相同代码示例:

#include <iostream>
#include <map>
#include <set>

using namespace std;

int A[]= { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
int B[]= { 3, 5 };

typedef set<int> row;

int
main()
{
  map<int, row> results;

  // Fill
  for (auto i = begin(A); i != end(A); ++i)
    for (auto j = begin(B); j != end(B); j++)
    {
      if (*i % *j)
        results[*i] = row();
      else
      {
        if (results.find(*j) == results.end())
          results[*j] = row();

        results[*j].insert(*i);
      }
    }

  // Cleanup
  for (auto j = begin(B); j != end(B); j++)
    for (auto i : results[*j])
      results.erase(i);

  // Dump
  for (auto i : results)
  {
    cout << "{ ";
    if (i.second.size())
      for (auto j = i.second.begin(), nocomma = --i.second.end(); j != i.second.end(); ++j)
        cout << *j  << (j == nocomma ? " " : ", ");
    else
      cout << i.first << " ";
    cout << "}" << endl;
  }

  return 0;
}

输出:

{ 12, 15, 18 }
{ 10, 15, 20 }
{ 11 }
{ 13 }
{ 14 }
{ 16 }
{ 17 }
{ 19 }