Dato un array di n bit, come generare ogni permutazione con i 1 e gli n-0?

Question

Dato un array di n bit, come generare ogni permutazione con i 1 e gli n-0?

#1 da (2 voti)
#2 da (0 voti)

1

È abbastanza semplice forzare brutalmente una raccolta di stringhe e quindi filtrare per ogni occorrenza con il conteggio richiesto di 1.

Man mano che n aumenta il numero di possibili permutazioni diventa molto grande, molto rapidamente, tuttavia, e a causa di considerazioni sulla velocità e lo spazio, sto cercando di trovare un metodo più sofisticato - idealmente, uno che non implichi una stringa eccessiva elaborazione.

algorithms combinatorics

posta lcdr_data 10.06.2015 - 06:26

fonte

2 risposte

Leggi altre domande sui tag algorithms combinatorics

Una fabbrica può essere sostituita da una chiave sul web.config? Come sarebbero i trade-off di ciascun approccio? Devo usare i farmaci generici quando possibile o in alcuni casi è ok?

score 2 · Answer 1

È possibile suddividere il problema nel sottoprocesso (pseudocodice):

array[] GetArrays(j, n)
    if(n = 0)
        return one empty array
    if(j = 0)
        return one array of n zeroes
    array[] zero = map(prepend 0,  GetArrays(j, n-1)) 
    array[] one = map(prepend 1,  GetArrays(j - 1, n - 1))
    return concat(zero, one)

score 0 · Answer 2

Scegli un algoritmo arbitrario per generare tutte le combinazioni di elementi da n. Vedi questo post SO precedente , ad esempio oppure i 75 esempi in diversi linguaggi di programmazione su Codice Rosetta . Quindi usalo per generare tutte le combinazioni di elementi i dal set {0,1,2,...,n-1} e assegna ogni risultato R = (r1,r2,...,r_i) una stringa di lunghezza n di zeri e uno dove le posizioni di quelle sono i valori in R.