Algoritmo di conteggio dei sottoinsiemi

1

Ho un problema seguente che voglio risolvere in modo efficiente:

Input: imposta s di {Pass, Fail} ^ k vettori, m - percentuale minima di vettori

Output: set di insiemi di indici: dove ogni set contiene gli indici di Pass word in determinati vettori e il numero di vettori che contiene Pass in quegli indici supera il m percento dai vettori totali.

Esempio: {(Pass, Fail, Pass, Fail), (Pass, Fail, Pass, Pass)} dove k è 4 e il numero di elementi set è 2 e m 60%, l'uscita sarà {{0,2 }, {0}, {2}}

L'output è un gruppo di set in cui ogni set contiene indici vettoriali che per almeno il 60% del valore dei vettori era Pass

    
posta Sergey Kucher 14.08.2011 - 13:46
fonte

1 risposta

2

Questo dovrebbe darti gli indici. Il prossimo passo è costruire la potenza impostata da questi.

link

Puoi controllare quali sono le enumerazioni e le list comprehensions e le tuple. Fammi sapere se sei bloccato a tradurre questo in C #.

s = ((True,False,True,False),(True,False,True,True))
indecies = [0] + [i+1 for i, vctr in enumerate(s) if sum(vctr) >= 0.6 * len(el)]
indecies
[0, 2]

Note: A) Devi sempre anteporre l'indice 0, che rappresenta il set vuoto. B) Il modo in cui l'ho inserito qui è inefficiente, ma puoi trovare un modo migliore. C) La complessità finora è proporzionale al numero totale di voti. D) Puoi rendere il 60% un parametro piuttosto che una costante hardcoded. E) È stato difficile analizzare le tue esigenze, quindi ho pensato che volevi filtrare i vettori perdenti e poi calcolare un power set degli indici rimanenti.

    
risposta data 14.08.2011 - 18:31
fonte

Leggi altre domande sui tag