Algoritmo per trovare se è possibile ricreare un set

Questo può essere risolto calcolando una corrispondenza tra gli elementi nel tuo set base e gli altri set. Questo essenzialmente controlla la condizioni di Hall .

Cioè, costruisci un grafo bipartito G = (A, B, E), dove A è il set base e B è gli altri set. C'è un vantaggio da x in A a qualche y in B se x è in y. Ora calcola un matching massimo (ci sono diversi algoritmi per questo) e sei a posto. Se non esiste alcuna corrispondenza, non è possibile ricreare il set.

Diciamo che il tuo set "grande" è chiamato bigSet e la tua serie di insiemi è chiamata arrayOfSets.
1. Passa attraverso tutti gli elementi di tutti i set in arrayOfSets e ricorda quante volte hai trovato ogni numero da bigSet in questi set. Supponiamo che tu memorizzi queste informazioni in count (che dovrebbe essere un dizionario se bigSet non è ordinato, che non dovrebbe essere per definizione ... oppure puoi rendere il bigSet ordinato copiandolo in una matrice o qualcosa del genere ).
2. Se hai trovato qualche numero zero volte (ovvero se count(bigSet[i]) è 0 per alcuni i), bigSet non può essere generato da arrayOfSets .
3. Ripassa di nuovo arrayOfSets e ogni volta che trovi un numero da bigSet il cui conteggio in arrayOfSets è min{count(bigSet[1]), count(bigSet[2]),..., count(bigSet[n])} , elimina quel set da arrayOfSets e diminuisci il numero di volte in cui ogni numero da quell'array appare in arrayOfSets . Se il conteggio di alcuni numeri raggiunge 0 dopo averlo fatto, e se non è il numero che hai appena trovato, bigSet non può essere generato. "Elimina" (cancella o in qualche modo "segna" così sai che non dovresti più considerarlo) il numero che hai appena trovato da bigSet e riavvia questo passaggio. Ricorda il set da cui hai preso quel numero (se vuoi ricreare la soluzione in seguito)
4. Se bigSet è vuoto (tutti i numeri da esso sono stati eliminati), puoi generare bigSet da arrayOfSets .
5. Ripeti 3. - 4.

Esempio: (Sto usando l'indicizzazione basata su 1)

bigSet = {10,4,8,1,7}
arrayOfSets = [{10,4}, {10,8,12,7},{1,5},{9,7},{7}]     
Go through arrayOfSets and get:  
count(10) = 2
count(4) = 1
count(8) = 1  
count(1) = 1  
count(7) = 3
min(count()) = 1 so go through arrayOfSets searching for numbers from {4,8,1}.  
arrayOfSets[1] contains 4, so you delete arrayOfSets[1] from arrayOfSets, delete 4 from bigSet and decrease count for 4 and 10.
After this, you have:
bigSet = {10,8,1,7}
arrayOfSets = [{SKIPME},{10,8,12,7},{1,5},{9,7},{7}]     
count(10) = 1
count(8) = 1  
count(1) = 1  
count(7) = 3 
min(count()) = 1 so go through arrayOfSets searchinig for numbers from {10,8,1}.  
arrayOfSets[2] contains 8 so, following the same procedure, you get:
bigSet = {10,1,7}  
arrayOfSets = [{SKIPME},{SKIPME},{1,5},{9,7},{7}]     
count(10) = 0
count(1) = 1  
count(7) = 3  
bigSet can't be generated from arrayOfSets because count(10) = 0.

Ecco un approccio che dovrebbe essere "ok" in termini di complessità temporale (ma forse non ancora ottimale). L'idea è di creare prima un indice di valori nella serie di insiemi, quindi passare attraverso l'insieme di numeri per vedere se possono essere trovati nell'indice.

Definizioni

Usando la descrizione del problema,

• consenti a S di essere il set che stai cercando di ricostruire
• lascia che X sia l'array di insiemi, dove X [i] è l'i'th impostato in X
• lascia v = X [i, j] il valore j'th nel set X [i]

Per risolvere il problema in modo efficiente,

• sia H una mappa con le voci h (v, XI), dove v è un valore in X, e XI è una lista di indici i in X in cui è stato trovato questo valore.
• sia R la mappa dei valori corrispondente a S, con le voci r (i, v) dove v è il valore nell'insieme X [i], e i è l'insieme da cui è stato preso questo valore per ricostruire S

Algoritmo

1. Costruisci la mappa H leggendo tutti i set di X. Per ogni nuovo valore v = X [i, j], inserisci una corrispondente voce h (v, XI) in H per ricordare in quale set (il ho impostato X) questo valore è stato trovato. Per i valori già in H, aggiungi i alle voci corrispondenti 'XI.

2. Iterate su tutti i valori in S. Per ogni valore, cercatelo in H. Se non ne trovate uno, interromperete poiché S non può essere ricostruito.

3. Per ogni valore in S, se il valore esiste in H, itera su XI della voce corrispondente h (v, XI) per recuperare gli indici i.

4. Per ogni i in XI, prova ad aggiungere R una nuova voce r (i, v), se e solo se R non contiene un'altra voce per lo stesso i. Se una voce per i esiste già, significa che un altro valore è già stato letto dall'insieme corrispondente in X, e un altro set deve essere considerato.

5. Ripeti il passaggio 4 finché non sarà possibile aggiungere una nuova voce a R, o finché non ne rimarrà più. In quest'ultimo caso interrompere come il set S non può essere ricostruito. *)

6. I valori v nelle voci di R dovrebbero ora corrispondere a S.

*) in realtà, prima di interrompere il passaggio 5, potrebbe esserci qualche permutazione di insiemi in X che funzionerebbe ancora. Perché ciò funzioni, l'algoritmo dovrebbe riavviare il passaggio 4 provando un'altra combinazione di set in X.

Dichiarazione di non responsabilità: non ho implementato l'algoritmo o lo ho testato.