Pregunta Cómo comprobar si un vector es un subconjunto de otro en c ++


Estoy tratando de encontrar una forma simple de verificar si un vector es un subconjunto de otro sin ordenar el orden de los elementos en el vector. Ambos vectores contienen elementos de números aleatorios en ellos.

std::includes parece funcionar solo para rangos ordenados ¿Cómo puedo lograr esto?


10
2017-08-02 01:54


origen


Respuestas:


Copia los vectores. Ordena las copias. Entonces usa std::includes en las copias.

template <typename T>
bool IsSubset(std::vector<T> A, std::vector<T> B)
{
    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());
    return std::includes(A.begin(), A.end(), B.begin(), B.end());
}

17
2017-08-02 02:03



Mi respuesta asume que cuando dices "subconjunto", realmente estás buscando más el equivalente de una "subcadena"; es decir, mantener el orden de los elementos durante la búsqueda.


En última instancia, no puedo ver cómo podrías hacer esto en nada menos que O(n*m). Teniendo eso en cuenta, puedes simplemente lanzar tu propia manera simple:

template <typename T1, typename T2>
bool contains(std::vector<T1> const& a, std::vector<T2> const& b) {
   for (typename std::vector<T1>::const_iterator i = a.begin(), y = a.end(); i != y; ++i) {
      bool match = true;

      typename std::vector<T1>::const_iterator ii = i;
      for (typename std::vector<T2>::const_iterator j = b.begin(), z = b.end(); j != z; ++j) {
          if (ii == a.end() || *j != *ii) {
              match = false;
              break;
          }
          ii++;
      }

      if (match)
         return true;
   }

   return false;
}

Demo en vivo.

(Probablemente podría ser más creativo con los parámetros de la plantilla).


7
2017-08-02 02:02



Esto supone que los duplicados NO importan. Entonces, si tiene dos instancias del número 99 en el vector a, entonces, siempre que el vector b tenga al menos una instancia del número 99, entonces se declarará como un subconjunto.

bool isSubset(const std::vector<int>& a, const std::vector<int>& b)
{
    for (std::vector<int>::const_iterator i = a.begin(); i != a.end(); i++)
    {
        bool found = false;

        for (std::vector<int>::const_iterator j = b.begin(); j != b.end(); j++)
        {
            if (*i == *j)
            {
                found = true;
                break;
            }
        }

        if (!found)
        {
            return false;
        }
    }

    return true;
}

3
2017-08-02 01:59



Sin clasificación ...

template <typename T>
bool isSubsetOrEqual(std::vector<T> const& a, std::vector<T> const& b) {
   for(auto const& av:a){
      if(std::find(b.begin(),b.end(),av)==b.end())
          return false;
   }
   return true;
}

0
2017-12-20 22:48