Algoritmo per ottimizzare il raggruppamento

Question

Algoritmo per ottimizzare il raggruppamento

#1 da (2 voti)

3

Vorrei sapere se esiste un algoritmo noto o un modo migliore per fare quanto segue:

Ho una collezione con una sottoraccolta, ad esempio:

R1 R2 R3
-- -- --
M  M  M
N  N
L  L
   A

Quello di cui ho bisogno è un algoritmo per ottenere il seguente risultato:

R1, R2: M N L
R2: A
R3: M

Questo è -non- ciò che voglio, ha più valori ripetuti per R rispetto a quanto sopra:

R1, R2, R3: M
R1, R2: N L
R2: A

Ho bisogno di raggruppare in modo da ottenere i gruppi più ottimizzati di R. La minor quantità di gruppi di R, meglio è che ottengo le raccolte secondarie più grandi.

Un altro esempio (con il risultato più ovvio):

R1 R2 R3
-- -- --
M  M  A
V  V  B
L  L  C

Deve risultare in:

R1, R2: M V L
R3: A B C

Ho bisogno di farlo in LINQ / C #.

Qualche soluzione? Suggerimenti? Link?

c# algorithms linq

posta Jeroen 28.11.2012 - 17:42

fonte

1 risposta

Leggi altre domande sui tag c# algorithms linq

Esiste un modello di fabbrica per prevenire istanze multiple per lo stesso oggetto (istanza uguale a Equal)? Se implemento un servizio web, come posso rispondere alle richieste POST con JSON?

score 2 · Answer 1

Penso che dal momento che desideri la minima totale R, vuoi invertire il tuo K / V e utilizzare i valori come chiavi in modo che la lista iniziale diventi:

M: R1, R2, R3
N: R1, R2
L: R1, R2
A: R2

Quindi puoi pronunciare il conteggio dei membri che si intersecano ( link ) di M e N è 2, il che significa che ottieni n- (2 set * 2 membri) numero di R, e se intersechi L ottieni n- (3 * 2) numero di R. e se intersechi anche A e ottieni n- (4 * 1) numero di R, ovviamente la tua scelta migliore è il secondo set di intersezioni. Sfortunatamente questa è un'implementazione ingenua con O (n!) Tempo perché devi intersetare tutti i possibili set per trovare il più grande set di intersezioni che produrrà la più grande minimizzazione di R per ritrarre tutti i set.

Dopo aver trovato la migliore ottimizzazione in questa tecnica in cui il conteggio dell'intersezione più grande * ha superato, rimuovi tutte le R nella serie di intersezioni dai set che hai intersecato, quindi ripeti i confronti dell'intersezione combinatoria terribilmente inefficienti contro i set man mano che vengono lasciati . Risciacqua e ripeti i confronti per trovare le intersezioni più grandi e rimuoverle dai set fino a quando non ci sono R in nessun set.

Esiste sicuramente una tecnica di confronto più efficiente che intersecare ogni combinazione di set come suggerisco. Sto solo suggerendo un algoritmo che dovrebbe funzionare (credo), che è probabilmente l'approccio ingenuo.