Wie prüft man in C++, ob ein Vektor eine Teilmenge eines anderen Vektors ist?

Question

Ich versuche, einen einfachen Weg zu finden, um zu prüfen, ob ein Vektor eine Teilmenge eines anderen ist, ohne die Reihenfolge der Elemente im Vektor zu sortieren. Beide Vektoren enthalten Elemente mit Zufallszahlen.

std::includes scheint nur für sortierte Bereiche zu funktionieren. Wie kann ich dies bewerkstelligen?

Answer 1

Kopieren Sie die Vektoren. Sortiere die Kopien. Verwende dann std::includes auf den Kopien.

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

Answer 2

Meine Antwort geht davon aus, dass Sie, wenn Sie "Teilmenge" sagen, eigentlich eher nach dem Äquivalent einer "Teilzeichenkette" suchen, d. h. die Reihenfolge der Elemente während der Suche beibehalten.

---

Letztendlich kann ich mir nicht vorstellen, wie man das in weniger als O(n*m) . Da kann man ganz einfach seine eigene Rolle spielen:

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

Live-Demo.

(Sie könnten wahrscheinlich kreativer mit den Parametern der Vorlage umgehen).

Answer 3

Dabei wird davon ausgegangen, dass Duplikate KEINE Rolle spielen. Wenn Sie also zwei Instanzen der Zahl 99 in Vektor a haben, dann wird Vektor b als Teilmenge deklariert, solange er mindestens eine Instanz der Zahl 99 enthält.

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

Answer 4

Ohne Sortierung...

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