Randomizzazione ristretta di un vettore binario

Quello che potresti fare (in prossimità del tempo O (n), se non mi sbaglio) è, parametrizzandolo con "limite", preparare / pre-calcolare una grammatica senza contesto epsilon come (per limit = 3),

Upto3 -> LimitOnes | LimitZeros
LimitOnes -> Zeros Ones LimitOnes | Zeros Ones | Zeros
LimitZeros -> Ones Zeros LimitZeros | Ones Zeros | Ones
Zeros -> Zero | Zero Zero | Zero Zero Zero
Ones -> One | One One | One One One
Zero -> 0
One -> 1

(nota: non pretendo che sia la grammatica corretta o più semplice che vorresti usare, ma puoi sempre giocherellare / sperimentare con la tua usando l'elegante Grammofono strumento, di Michael Daines)

dove "Upto3" è il simbolo assioma / inizio della grammatica.

(Le uniche due regole che dipendono da N che sono Zeros - > ... e Ones - > ...)

Quindi, usando una grammatica pre-calcolata (che userete per scopi di generazione anziché l'analisi), potete scrivere una semplice funzione ricorsiva, che, partendo dal simbolo di inizio, seleziona casualmente una delle alternative del regole e la applica, tramite concatenazione di stringhe, su un accumulatore che passa a se stesso (e che avrai passato come stringa vuota per la chiamata di livello superiore).

Ad ogni chiamata ricorsiva, è banale decidere (a seconda di N e dell'ultima lunghezza conosciuta dell'accumulatore) quale ramo alternativo delle regole (cioè, produzioni) - LimitOnes, LimitZeros, Ones o Zeros - è significativo seguire (non superare N).

Per esempio,

N = 10, limit = 3:

inizia con Upto3: accumulator=""

da "Upto3", scegli in modo casuale "LimitZeros"

da "LimitZeros", applica "Ones", "Zeros" in "Ones Zeros LimitZeros": accumulator="100"

da "LimitZeros", applica "Ones", "Zeros" in "Ones Zeros LimitZeros": accumulator="100110"

ecc., ecc.

Ti lascio capire i dettagli di implementazione.

'Spero che questo aiuti,

L'approccio generale per affrontare un problema di questo tipo è pensare alla combinatoria. Come risponderesti alla domanda " Quante stringhe binarie a 40 bit ci sono senza più di 3 dello stesso bit? "

Risposta: decomposizione strutturale. Una stringa binaria a 40 bit senza esecuzioni di più di 3 dello stesso bit termina in una corsa di 1, 2 o 3 bit; in generale possiamo definire una funzione f(n) conteggio n -bit stringhe binarie che non eseguono più di 3 bit e derivano la ricorrenza f(1) = 1 , f(0) = 1 (molto importante!), f(-1) = 0 , e per più grande n , f(n) = f(n-1) + f(n-2) + f(n-3) .

Ora, estendetelo alla domanda " Quante stringhe binarie a 40 bit ci sono con il peso di Hamming di 20 bit e nessuna esecuzione di più di 3 dello stesso bit? ". Questa volta la scomposizione strutturale deve prendere in considerazione il peso di Hamming in un modo o nell'altro. Un modo sarebbe considerare l'eccesso del bit finale: ad es. in 0010110 il bit finale è 0 e l'eccesso è 1 perché c'è un altro 0 rispetto a 1 . Questa volta chiamiamo la nostra funzione g . Vogliamo sapere g(40, 0) (stringa a 40 bit con eccesso di 0).

Per derivare la ricorrenza per g(n, e) , supponiamo che l'ultima esecuzione sia di lunghezza r . Se il numero totale di bit dello stesso valore dell'ultima esecuzione è b e il numero dell'altro bit è a , quindi per definizione e = b - a . Se rimuoviamo la corsa, rimaniamo con n - r bit e la sottrazione per i salti in eccesso (ricordate che è l'eccesso del ultimo bit, e rimuovendo l'ultimo giro giriamo l'ultimo bit) per diventare a - (b - r) = r - e .

Quindi otteniamo la ricorrenza g(n, e) = g(n - 1, 1 - e) + g(n - 2, 2 - e) + g(n - 3, 3 - e) . Le basi vengono lasciate come un dettaglio che deve essere compilato.

Tieni presente che possiamo utilizzare un approccio tabella di programmazione dinamica standard per calcolare g(n, e) in O(ne) di spazio e tempo.

Dopo aver riempito quella tabella, possiamo rispondere alla domanda originale: come generare una delle stringhe g(40, 0) . Decidiamo semplicemente se la corsa finale sarà di 0 o 1 (con una semplice chiamata a rand() ), e decidere se sarà di lunghezza 1 , 2 o 3 (idealmente ponderazione della scelta casuale in proporzione ai contributi di ciascuno dei tre: g(n - r, r - e) ). Quindi passiamo a quel g(n', e') e applichiamo lo stesso processo con la differenza minore che invece di decidere casualmente il valore dell'ultimo passaggio lo spostiamo dal suffisso.

Il punto chiave che voglio fare è che questo processo di utilizzare per primo una scomposizione strutturale per rispondere alla domanda combinatoria è una tecnica molto generale che si applica a molte molte strutture combinatorie. Puoi usarlo per generare in modo uniforme una partizione casuale di un intero, un albero binario casuale con un dato numero di nodi, ecc.

Considera il seguente approccio:

1. Crea un vettore casuale senza limitazioni
2. Utilizza un codice di linea predefinito in modo simile a 4B5B ( link ) per far sì che quanto sopra soddisfi i tuoi limiti .

C'è un problema generale nell'area della comunicazione, ci sono molte ragioni per cui vogliamo trasformare una stringa di bit in un'altra stringa in modo tale che la quantità di ripetizioni di ogni bit sia limitata (ad esempio evitare la sottostringa lunga che è tutto zeri o tutti). Sono certo che se ripassi l'argomento troverai quello che stai cercando, credo che il metodo 4B5B possa essere generalizzato per ottenere ciò che ti serve, quindi è un buon punto di partenza