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

假设我们得到了一个整数数组。例如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(boolean) 数组，如果它已经属于某个等效类，则返回false；如果还不属于一个等效类，则返回true。
这将计算被B [k]中的元素整除的等价集的数量，但是现在，我不确定如何处理单例集，因为循环后将检查数组成员都重置为true。

(我试过了

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

在上述循环之后，但仅将n加到计数中)

有人可以帮我吗？有更有效的方法吗？另外，我应该如何处理单例集？

谢谢。

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

最佳答案

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

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

关于c++ - 查找C++中等效类数量的有效方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25235615/