Algoritmo per calcolare la permutazione k senza ripetere e senza duplicati

Question

Algoritmo per calcolare la permutazione k senza ripetere e senza duplicati

#1 da (2 voti)

3

Ho un insieme di numeri interi, ad esempio 1..20, e voglio ottenere tutte le possibili combinazioni di quel set per disegnare 5 numeri.

Quindi ogni combinazione ha 5 numeri da quel set di numeri interi. Ma non voglio che i numeri nella combinazione siano duplicati e voglio che la combinazione non ordinata sia unica.

Suppongo che non sia facile da capire, il mio inglese non è il migliore e non conosco tutti i termini matematici. Quindi ecco un'illustrazione.

Il mio set è 1..20 e ovviamente ha una lunghezza di 20 .

Voglio che ogni combinazione possibile sia come [1, 2, 3, 4, 5] , [1, 2, 3, 4, 6] , ..., [1, 4, 8, 14, 20] , sempre una lunghezza di 5.

E questo dovrebbe essere proibito: [1, 2, 3, 4, 5] , [3, 2, 1, 5, 4] poiché questi due contengono gli stessi numeri esatti.

Anche questo non è permesso: [1, 1, 2, 3, 4] poiché questa combinazione contiene numeri duplicati.

Quindi un approccio ingenuo sarebbe quello di iterare tramite il 5% difor di cicli su 20, salvare tutte le combinazioni precedenti e verificare la presenza di duplicati attraverso le combinazioni e all'interno della combinazione più recente. Ma questo risulterebbe in 3.200.000 cicli, che non è molto efficiente, dal momento che il numero finale di combinazioni è 1.860.480 (se non ho calcolato male, ma dovrebbe essere n! / ((n -k)! * k!) se non sbaglio completamente, dove n = 20 e k = 5 ).

Quindi, come posso eliminare i loop duplicati in primo luogo? Ho bisogno di un algoritmo che sia veloce e che non compia passi inutili poiché calcolerò cose con questi dati che richiedono un po 'di tempo e quindi voglio ridurre il più possibile il numero di cicli.

algorithms combinatorics

posta Johannes Klauß 10.06.2015 - 12:21

fonte

1 risposta

Leggi altre domande sui tag algorithms combinatorics

Utilizzo di JDK nei problemi di licenza di Google Studio Android Perché git ha bisogno di rimuovere oggetti duplicati quando si uniscono i rami?

score 2 · Accepted Answer

A meno che non mi sbagli:

Ci sono% modi per scegliere 5 numeri su 20 (con ripetizioni, con duplicati)
Se non si accettano "duplicati" (selezionando lo stesso numero più di una volta), si rimane con 20^5 = 3,200,000 , in questo caso n! / (n - k)! . Queste sono permutazioni k.
Se, quindi, non autorizzi la "ripetizione" (avendo raccolte con gli stessi elementi solo in un ordine diverso), ti verrà lasciato con 20! / (20 - 5)! = 1,860,480 , in questo caso n! / ((n - k)! * k!) . Questi sono chiamati k-combinazioni. Questi sono ciò che sembri cercare.

Se stai cercando solo combinazioni di dimensione 5 e vuoi accedere immediatamente all'intero insieme di combinazioni, allora direi che l'approccio a 5 cicli nidificati va bene, e non penso che sarai in grado di fare qualsiasi cosa più veloce. Hai solo bisogno di modificare la tua idea un po 'così non avrai bisogno di verificare l'univocità o duplicare i numeri e non fare iterazioni inutili. Puoi produrre (solo) combinazioni ordinate facendo qualcosa come:

public Set<Set<Integer>> all5CombinationsOf20(){
    Set<Set<Integer>> result = new HashSet<Set<Integer>>();
    for(int i = 1; i <= 16; i++){
        for(int j = i+1; j <= 17; j++){
            for(int k = j+1; k <= 18; k++){
                for(int l = k+1; l <= 19; l++){
                    for(int m = l+1; m <= 20; m++){
                        result.add(new HashSet<Integer>(Arrays.asList(i,j,k,l,m)));
                    }
                }
            }
        }
    }
    return result;
}

Dato che questo ti dà le combinazioni in un modo ordinato [1, 2, 3, 4, 5] viene prodotto, ma [3, 2, 1, 5, 4] e [1, 1, 2, 3, 4 ] non lo sono.

Tuttavia questo approccio non è estendibile a combinazioni di dimensioni arbitrarie, quindi avresti bisogno di ricorsione. Una volta ho scritto questo:

public static <T> Set<Set<T>> combinations(Set<T> alphabet, int k) {
    if (alphabet.size() == 0) {
        throw new IllegalArgumentException("alphabet.size must be > 0");
    }
    if (k < 0) {
        throw new IllegalArgumentException("k must be >= 0");
    }
    if (k == 0) {
        Set<Set<T>> result = new HashSet<Set<T>>();
        result.add(new HashSet<T>());
        return result;
    } else {
        Set<Set<T>> result = new HashSet<Set<T>>();
        for (T e : alphabet) {
            Set<T> newAlphabet = new HashSet<T>(alphabet);
            newAlphabet.remove(e);
            Set<Set<T>> smallerCombinations = combinations(newAlphabet, k - 1);
            for (Set<T> smallerCombination : smallerCombinations) {
                Set<T> combination = new HashSet<T>(smallerCombination);
                combination.add(e);
                result.add(combination);
            }
        }

        return result;
    }
}

Questo non è necessariamente veloce visto che si sta facendo molto casino, ma l'idea dovrebbe essere chiara: per fare una combinazione di dimensione n su un certo alfabeto (nel tuo caso 1..20), rimuovi un elemento e dall'alfabeto, crea una combinazione di dimensione n-1 sull'alfabeto meno e restituisci la combinazione con e aggiunto. Riutilizzare lo stesso alfabeto per combinazioni più piccole e lasciare che HashSet si sbarazzi dei duplicati sarebbe più veloce.

Anche questi insiemi di combinazioni diventano grandi abbastanza velocemente, quindi potresti voler essere pigro e non tenerli tutti in memoria (a seconda di come li vuoi usare), in tal caso, controlla link