Angenommen, Sie haben eine Reihe von Mengen von ganzen Zahlen. Es ist möglich, dass sich einige der Sets überschneiden (dh Elemente gemeinsam nutzen). Sie könnten die Überlappungen beseitigen, indem Sie Elemente aus den Sets löschen. Einige davon könnten jedoch leer sein. dass wäre eine Schande. Können wir alle Sätze disjunkt machen, ohne sie zu leeren?

Beachten Sie, dass es in dieser Situation keinen Grund gibt, mehrere Elemente in einem Satz zu belassen. Daher kann dieses Problem immer gelöst werden, indem jeder Satz auf nur ein Element reduziert wird. Das ist die Version des Problems, das wir hier lösen.

Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion wie folgt:

Eingabe : Eine Liste von Ganzzahlensätzen.

Ausgabe : Eine Liste von Ganzzahlen mit der gleichen Länge wie die Eingabe, für die:

• Alle Ganzzahlen in der Ausgabe sind unterschiedlich. und
• Jede Ganzzahl in der Ausgabe ist ein Element der entsprechenden Menge der Eingabe.

Klarstellungen

• Sie können eine Menge als Liste darstellen, wenn Sie dies wünschen (oder was auch immer für Ihre Sprache geeignet ist), ohne die Reihenfolge der Elemente zu berücksichtigen.
• Sie müssen den Fall nicht behandeln, in dem keine Lösung vorhanden ist (dh es wird immer mindestens eine Lösung geben).
• Möglicherweise gibt es mehr als eine Lösung. Ihr Algorithmus muss immer eine gültige Lösung erstellen, darf jedoch nicht deterministisch sein (dh es ist in Ordnung, wenn er bei jeder Ausführung eine andere gültige Lösung auswählt).
• Die Anzahl der verschiedenen Ganzzahlen, die in der Eingabe n erscheinen, entspricht der Anzahl der Mengen in der Eingabe und der Einfachheit halber sind die Ganzzahlen von 1 bis einschließlich n (da ihre tatsächlichen Werte keine Rolle spielen). Es liegt an Ihnen, ob Sie diese Tatsache ausnutzen möchten oder nicht.

Testfälle

[{1,2},{1,3},{1,4},{3,4}] -> [2,3,1,4] or [2,1,4,3]
[{1,3},{1,2,4},{2,3},{3},{2,3,4,5}] -> [1,4,2,3,5]
[{1,3,4},{2,3,5},{1,2},{4,5},{4,5}] -> [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4]

Siegbedingung

Ein Programm benötigt eine optimale Zeitkomplexität , um zu gewinnen. Wenn also ein Algorithmus mit einer besseren Zeitkomplexität gefunden wird, werden alle langsameren Einträge disqualifiziert. (Sie können davon ausgehen, dass die integrierten Funktionen Ihrer Sprache so schnell wie möglich ausgeführt werden, z. B. können Sie davon ausgehen, dass eine integrierte Sortierung in der Zeit O (n log n) ausgeführt wird. Ebenso können Sie davon ausgehen, dass alle Ganzzahlen mit einer vergleichbaren Größe wie n addiert, multipliziert usw. in konstanter Zeit.)

Da es in den meisten Sprachen wahrscheinlich ziemlich einfach ist, eine optimale Zeitkomplexität zu erhalten, ist der Gewinner das kürzeste Programm unter denjenigen mit der in Bytes gemessenen Zeitkomplexität.

Gelee , 8 Bytes

Œp⁼Q$ÐfḢ

Probieren Sie es online aus!

Erläuterung

Œp⁼Q$ÐfḢ  Main Link
Œp        Cartesian Product of the elements; all possible lists
     Ðf   Filter; keep elements that are
  ⁼Q$     Equal to themselves uniquified
      Ḣ   Take the first one

Extrem ineffizient. Asymptotisch ϴ(n^(n+1))nach Mischa Lawrow; Ich denke es ist richtig.

Wolfram Language (Mathematica) , 87 Bytes und ϴ (n ³ )

-Range[n=Length@#]/.Rule@@@FindIndependentEdgeSet[Join@@Table[-i->j,{i,n},{j,#[[i]]}]]&

Probieren Sie es online aus!

Erstellt ein zweigeteiltes Diagramm, dessen Scheitelpunkte auf der einen Seite die Mengen sind (indiziert durch -1,-2,...,-n) und dessen Scheitelpunkte auf der anderen Seite die Elemente sind 1,2,...,n, wobei eine Kante von -ibis jwann jin der i-ten Menge enthalten ist. Findet mithilfe eines integrierten Geräts eine perfekte Übereinstimmung in diesem Diagramm. Listet dann die Elemente auf, die -1,-2,...,-nin dieser Reihenfolge in perfekter Übereinstimmung entsprechen.

Mathematica FindIndependentEdgeSetist hier der Engpass; Alles andere erfordert O (n ² ) -Operationen. Mathematica verwendet wahrscheinlich den ungarischen Algorithmus , und daher gehe ich davon aus, dass er in ϴ (n ³ ) ausgeführt wird, obwohl es möglich ist, dass Mathematica eine naive Implementierung mit O (n ⁴ ) -Komplexität hat.

Haskell , 48 Bytes

-1 Byte dank Nimi.

import Data.List
head.filter((==)<*>nub).mapM id

Probieren Sie es online aus!

Mathematica 39 Bytes

Last@Union[DeleteDuplicates/@Tuples@#]&

In Bezug auf die Komplexität denke ich, dass dies sehr stark von der Länge jeder Unterliste sowie von einem Maß dafür abhängt, wie unzusammenhängend die Unterlisten sind.

Ich denke also, dieser Algorithmus ist O (n Log n + n ^ 2 Log m), wobei m ungefähr die durchschnittliche Länge jeder Unterliste ist.

So etwas hätte die Komplexität O (a ^ n), wobei a> 1 ein Maß für die Überlappung in Unterlisten ist:

(For[x={1,1},!DuplicateFreeQ@x,x=RandomChoice/@#];x)&

Schwer zu sagen, was wirklich schneller ist, ohne die Eigenschaften möglicher Eingaben zu kennen.

05AB1E , 13 Bytes, O (n! * N)

āœʒ‚øε`QO}P}н

Probieren Sie es online aus! Erläuterung:

ā               Make a range 1..n
 œ              Generate all permutations
  ʒ        }    Filter
   ‚ø           Zip with input
     ε   }      Loop over sets
      `QO       Check each element for membership
          P     All sets must match
            н   Take the first result

Schale , 5 Bytes

►oLuΠ

Probieren Sie es online aus!

Erläuterung

Ich habe gerade die Sache mit der Komplexität gesehen: Wie so oft bei der Lösung von Golfsprachen sind sie nicht sehr effizient - diese hat die Komplexität O (n · nⁿ).

►(Lu)Π  -- input as a list of lists, for example: [[1,2],[1,3],[1,4],[3,4]]
     Π  -- cartesian product: [[1,1,1,3],...,[2,3,4,4]]
►(  )   -- maximum by the following function (eg. on [1,1,1,3]):
   u    --   deduplicate: [1,3]
  L     --   length: 2

Pyth , 9 Bytes (ϴ (n ^{n + 1} ))

Da dies genau wie die Jelly-Lösung funktioniert, hat sie höchstwahrscheinlich die gleiche Komplexität.

h{I#.nM*F

Probieren Sie es hier aus!

Wie?

h {I # .nM * F | Volles Programm.

       * F | Kartesisches Produkt falten.
    .nM | Jeweils abflachen.
   # | Behalten Sie diese:
 {I Das ist unveränderlich über das Entfernen doppelter Elemente.
h | Nimm das erste Element.

JavaScript (ES6), 74 73 Byte

1 Byte gespeichert, dank @Neil.

f=([a,...A],s=[],S)=>a?a.map(c=>s.includes(c)||(S=S||f(A,[...s,c])))&&S:s

Durchläuft das Array rekursiv und sucht nach einer Lösung.

Ungolfed:

f=(
   [a, ...A],                        //a is the first array, A is the rest
   s = [],                           //s is the current trial solution
   S                                 //S holds the solution (if one exists) at this branch
  )=>
     a ? a.map(                      //if we're not done, iterate through a
           c => s.includes(c) ||     //  if this element already exists, short-circuit
                (S = S ||            //  else if S has a solution, keep it
                 f(A, [...s, c])     //  else look for a solution down this branch
                )
         ) && S                      //return S

Testfälle:

f=([a,...A],s=[],S)=>a?a.map(c=>s.includes(c)||(S=S||f(A,[...s,c])))&&S:s

console.log(f([[1,2],[1,3],[1,4],[3,4]])) // [2,3,1,4] or [2,1,4,3]
console.log(f([[1,3],[1,2,4],[2,3],[3],[2,3,4,5]])) // [1,4,2,3,5]
console.log(f([[1,3,4],[2,3,5],[1,2],[4,5],[4,5]])) // [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4],4]

Python3, 93 84 Bytes

-9 Bytes dank Caird Coinheringaahing

lambda I:next(filter(lambda x:len(x)==len({*x}),product(*I)))
from itertools import*

Probieren Sie es online aus!