Wie kann man bei zwei Mengen, die jeweils ganzzahlige Werte enthalten, eine Menge finden, die alle möglichen paarweisen Werte enthält?ORs der Werte dieser beiden Mengen? Z.B. (Alle Zahlen sind binär)

{1, 10} x {100, 1000} = {101, 1001, 110, 1010}
{1, 10} x {11, 101} = {11, 101, 111}

Das erste Beispiel ergibt volle vier Kombinationen, während das zweite nur drei ergibt, da beide Mengen einige Bits gemeinsam haben. Offensichtlich kann das Ergebnis in berechnet werdenO(m*n), aber gibt es einen schnelleren Weg, dies zu lösen, wenn man bedenkt, dass die Größe des Ergebnisses in vielen Fällen geringer wäre alsm*n?

In einigen Fällen ist die resultierende Menge signifikant kleiner alsm*n (z.B.{1, 11, 111} x {10, 110} = {11, 111}) - aber ich kann die genaue Art all dieser Fälle nicht genau genug bestimmen, um einen Algorithmus zu erhalten. Im Idealfall sollte es laufenO(r), wor ist die Größe der Ergebnismenge. Es kann eine Möglichkeit geben, Quellensets zu partitionieren, das Ergebnis mithilfe eines dynamischen Programmieransatzes aufzubauen oder etwas anderes in diesem Sinne zu tun, aber im Moment kann ich es nicht finden.