Situato combinatorio algoritmo in Java

Question

Ho un insieme di dati con gli attributi come questo:

Marital_status = {M,S,W,D}
IsBlind = {Y,N}
IsDisabled = {Y,N}
IsVetaran = {Y,N}

ecc. Ci sono circa 200 tali variabili.

Ho bisogno di un algoritmo per generare combinazioni di attributi, con un valore alla volta.

In altre parole, la mia prima combinazione potrebbe essere:

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = Y

Il set successivo sarebbe:

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = N

Ho provato ad utilizzare un generatore combinazione semplice, trattando ogni valore per ogni attributo come attributo stessa. Non ha funzionato perché le scelte si escludono a vicenda sono compresi nelle combinazioni e il numero di combinazioni possibili è davvero enorme (133873417996074857185490633899939406700260683726864088366400 per essere precisi)

La prego di suggerire un algoritmo (preferibilmente codificato in Java)?

Grazie !!

Answer 1

Come altri hanno fatto notare (e voi stessi anche), non è possibile verificare in modo esaustivo questo.

Vi suggerisco di prendere il metodo di campionamento , e il test con quello. Hai forte background teorico, in modo da essere in grado di trovare la strada in internet per trovare e capire questo.

---

Ma lasciatemi fare un piccolo esempio. Per ora, io ignorare possibili "gruppi" di parametri (che sono fortemente correlati).

• Crea un campione di dati uno , che contiene tutti i valori possibili per tutte le 200 parametri. Questo esaustività assicura che nessun valore di parametro potrebbe essere dimenticato.

    

  Non deve essere creato in anticipo, i valori possono essere creato da un ciclo.

• Per ogni campione di uno dei dati, è necessario aggiungere gli altri valori. Un approccio semplice sarebbe quella di scegliere un certo numero di volte che si desidera testare ogni uno-campione (dire N = 100). Per ogni campione di uno dei dati, si farebbe generare casualmente N volte gli altri valori .

  

Se ci sono 1000 possibili valori utilizzando tutti i 200 parametri, e N = 100, che ci darebbe 100K test.

---

Si potrebbe elaborare su questa idea di base in molti modi:

• Se si desidera che il test sia ripetibile , si potrebbe generare solo una volta, conservarlo, e quindi riutilizzare gli stessi set in tutti i test futuri.
• si poteva controllare la propria distribuzione in modo che ogni valore viene selezionato un discreto numero di volte .
• Nella vita reale, tutti i 200 parametri non sarebbero senza collegamenti. Molti parametri sarebbe in realtà essere collegati ad alcuni altri, nel senso che la probabilità di trovare i valori insieme non sono nemmeno. Invece di fare il set esaustivo iniziale su un solo parametro, come ho fatto in precedenza,
  Avrei eseguire l'insieme esaustivo su un cluster di parametri collegati .

Answer 2

trovare un altro modo. Se si dispone di 200 variabili, e ognuno ha almeno 2 scelte, si sta andando ad avere> = 2 ^ 200 combinazioni. Se si genera una combinazione ogni nanosecondo, ci vorrebbero circa 10 ^ 43 anni per enumerare 2 ^ 200 scelte.

Answer 3

Keith ha sottolineato, il numero delle combinazioni sarà incredibilmente grande se non ci sono combinazioni di esclusi, il che renderebbe il vostro bisogno unmeetable. Tuttavia, dal momento che hai già detto che avete scelte si escludono a vicenda, lo spazio delle soluzioni sarà più piccolo.

Quanto più piccolo? Dipende da quante scelte si escludono a vicenda. Mi consiglia di fare un po 'di matematica su che prima di andare troppo duro.

Supponendo che le scelte abbastanza sono esclusivi, si sta ancora andando ad avere per essenzialmente a forza bruta, ma si è molto improbabile trovare uno esistente, algoritmo di utile.

Il che mi porta alla domanda: qual è il tuo motivo per fare questo - test esaustivo? Suona bene, ma è possibile che questo non è possibile. Ho incontrato questo problema me stesso, e alla fine, si può ben essere costretto a una combinazione di casi "edge" accuratamente selezionati, oltre ad alcuni quasi-selezionati in modo casuale gli altri casi.

Dopo aver letto il tuo commento di cui sopra, sembra si definisce "la mutua esclusione" in modo diverso di me, e temo che si può avere un problema.

Quindi un dato paziente non sia cieco e non vedenti. Grande. Ma non è quello che ho (e ho il sospetto chiunque altro qui) capito quando lei ha citato le esclusioni comuni di investimento.

Per chi, sto parlando per esempio, se cieco, non può essere non disabili, o qualcosa del genere.

Senza un numero significativo di mutuamente esclusive interrelazioni tra i tuoi attributi che limitano le loro combinazioni, si sarà in grado di completare il test esaustivo.