Permutazioni fisse
Salve,
chiedo un aiuto, a risolvere un problema a cui non trovo una risposta, al momento.
Il problema è calcolare tutte le permutazioni di $|N|+|O|$ oggetti, dove gli oggetti di $N$ sono distinti ed hanno una funzione di ordine. e gli elementi di $O$ sono uguali e indistinti. Dove $|N|=|O|$.
esempio:
$N=[n_1,n_2,n_3,n_4]$
$O={o,o,o,o}$
Se ipotiziammo che la procedura che calcola la permutazione restituisce una lista $[]$ con posizione:
- posizione $1$ deve essere occupata da $n_1$
- posizione $|N|+|O|$ deve essere occupata da ${o}$
l'output di una procedura prossibile perciò diventa:
$[n_1,o,n_2,n_3,n_4,o,o,o]$
$...$
$[n_1,n_2,o,o,o,n_3,n_4,o]$
per semplificare il problema e le condizioni considero:
- $N'=N-{n_1}$
- $O'=O-{o}$
l'output perciò diventa:
$[o',n_2,n_3,n_4,o',o']$
$...$
$[n_2,o',o',o',n_3,n_4]$
questo è un esempio semplice, ma $N$ ed $O$ possono essere molto grandi.
Io ho ben scritto una procedura, ma vi chiedo se avete idee su come poter imporre che l'insieme $N$ mantenga l'ordinamento, cioè non sia perturbato. C'è qualche proprietà combinatoria?
Ringrazio molto
chiedo un aiuto, a risolvere un problema a cui non trovo una risposta, al momento.
Il problema è calcolare tutte le permutazioni di $|N|+|O|$ oggetti, dove gli oggetti di $N$ sono distinti ed hanno una funzione di ordine. e gli elementi di $O$ sono uguali e indistinti. Dove $|N|=|O|$.
esempio:
$N=[n_1,n_2,n_3,n_4]$
$O={o,o,o,o}$
Se ipotiziammo che la procedura che calcola la permutazione restituisce una lista $[]$ con posizione:
- posizione $1$ deve essere occupata da $n_1$
- posizione $|N|+|O|$ deve essere occupata da ${o}$
l'output di una procedura prossibile perciò diventa:
$[n_1,o,n_2,n_3,n_4,o,o,o]$
$...$
$[n_1,n_2,o,o,o,n_3,n_4,o]$
per semplificare il problema e le condizioni considero:
- $N'=N-{n_1}$
- $O'=O-{o}$
l'output perciò diventa:
$[o',n_2,n_3,n_4,o',o']$
$...$
$[n_2,o',o',o',n_3,n_4]$
questo è un esempio semplice, ma $N$ ed $O$ possono essere molto grandi.
Io ho ben scritto una procedura, ma vi chiedo se avete idee su come poter imporre che l'insieme $N$ mantenga l'ordinamento, cioè non sia perturbato. C'è qualche proprietà combinatoria?
Ringrazio molto
Risposte
"ham_burst":
Io ho ben scritto una procedura, ma vi chiedo se avete idee su come poter imporre che l'insieme $N$ mantenga l'ordinamento, cioè non sia perturbato. C'è qualche proprietà combinatoria?
Se ho capito bene gli [tex]n_i[/tex] devono rimanere ordinati, mentre gli o gli "ballano intorno"? Allora puoi considerare gli [tex]n_i[/tex] dei setti che individuano $|N|$ recipienti (visto che [tex]n_1[/tex] deve rimanere al primo posto, ma in coda si possono avere degli o), e in ogni recipiente puoi trovare un numero qualunque di o. Il problema e' lo stesso che nella distribuzione di Bose-Einstein (vedi http://en.wikipedia.org/wiki/Bose_distribution).
Praticamente gli [tex]n_i[/tex] scompaiono dal problema.
Ora, non ho capito se devi solo calcolare il numero di permutazioni possibili, oppure se devi produrle con un algoritmo (si spera il piu' efficiente possibile) una per una. Il primo caso e' noto, nel secondo si tratta praticamente di fare delle partizioni di $|O|$ con numeri non-negativi, per quanto ne capisco io, visto che gli 'o' sono indistinguibili, e le loro permutazioni fattorizzano. Devi tenere solo il conto delle trasposizioni necessarie per portare le 'o' nei rispettivi recipienti, per esempio a partire dall'ordinamento arbitrario
[tex]\{n_1,..,n_{|N|},o,..\}[/tex]
per portare una 'o' tra [tex]n_1[/tex] e [tex]n_2[/tex] devi fare le $|N|-1$ trasposizioni $(n_{|N|},o)$, $(n_{|N|-1},o)$, e cosi' via.
Spero che ti possa servire, mi rendo conto che sono un po' di pensieri in liberta'
bye^2, mr
Assolutamente fantastico!
avevo intuito qualcosa, ma la tua esposizione mi a fatto chiarire la soluzione in modo molto più formale.
Sì l'algoritmo è un passo successivo, l'importante era capire come risolvere questa parte del problema (molto più ampio).
Ho tralasciato per sbaglio una condizione, ma si risolve nello stesso modo. Vediamo se funziona applicata al procedimento scritto fino ad ora.
Intanto grazie mille
avevo intuito qualcosa, ma la tua esposizione mi a fatto chiarire la soluzione in modo molto più formale.
Sì l'algoritmo è un passo successivo, l'importante era capire come risolvere questa parte del problema (molto più ampio).
Ho tralasciato per sbaglio una condizione, ma si risolve nello stesso modo. Vediamo se funziona applicata al procedimento scritto fino ad ora.
Intanto grazie mille
"ham_burst":
Ho tralasciato per sbaglio una condizione, ma si risolve nello stesso modo. Vediamo se funziona applicata al procedimento scritto fino ad ora.
Intanto grazie mille
Di nulla!
Fammi sapere come va a finire
bye^2, mr
Ne approfitto per chiedere un altro parere, sempre legato al problema sopra, ma questa volta è un problema di rappresentazione in stuttura dati.
Cambio la definizione dell'insieme $O$ così da semplificare il discorso.
$O$ rappresenta un insieme di elementi ${s,d}$ con cardinalità $|O|=2*(n-1)$ cioè ci sono $(n-1)\ ,\ s$ e $(n-1)\ ,\ d$.
Il problema perciò diviene, elencare ogni permutazione di $O$ rispetto ad $N$ (permutazione limitata ad un shift sinistro di $O$ su $N$come detto sopra), dove ogni lista risultante dovrà avere $|N|+(|O|-(n-1))$ elementi.
Perciò sarebbe da elencare ogni sottoinsieme di $O$ di dimensione $(n-1)$ cioè $((|O|),((n-1)))$ liste per ogni permutazione di $N$. cioè un bellissimo elenco di circa $(n-2)^2* ((|O|),((n-1)))$ liste
esempio un passo:
$[n_1,n_2,n_3,s,n_4,s,d]$
...
$[n_1,n_2,n_3,d,n_4,d,s]$
Il problema, se lo ho spiegato bene, è come potrei far "convivere" uno schift con ogni sottoinsieme di $O$? Sapendo che i due insiemi hanno due rappresentazioni e significati semantici completamente diversi.
Ringrazio ancora
Cambio la definizione dell'insieme $O$ così da semplificare il discorso.
$O$ rappresenta un insieme di elementi ${s,d}$ con cardinalità $|O|=2*(n-1)$ cioè ci sono $(n-1)\ ,\ s$ e $(n-1)\ ,\ d$.
Il problema perciò diviene, elencare ogni permutazione di $O$ rispetto ad $N$ (permutazione limitata ad un shift sinistro di $O$ su $N$come detto sopra), dove ogni lista risultante dovrà avere $|N|+(|O|-(n-1))$ elementi.
Perciò sarebbe da elencare ogni sottoinsieme di $O$ di dimensione $(n-1)$ cioè $((|O|),((n-1)))$ liste per ogni permutazione di $N$. cioè un bellissimo elenco di circa $(n-2)^2* ((|O|),((n-1)))$ liste
esempio un passo:
$[n_1,n_2,n_3,s,n_4,s,d]$
...
$[n_1,n_2,n_3,d,n_4,d,s]$
Il problema, se lo ho spiegato bene, è come potrei far "convivere" uno schift con ogni sottoinsieme di $O$? Sapendo che i due insiemi hanno due rappresentazioni e significati semantici completamente diversi.
Ringrazio ancora
Non ti bastano due numeri (int)?
/OT
TO/
/OT
"ham_burst":
...uno schift...
TO/
Non ho prima di tutto del tutto chiaro quale sia il significato di $n$, rappresenta la cardinalità di $N$?
Considero prima di tutto le stringhe di lunghezza $m$ di elementi di $O$ (suppongo che $m$ sia minore o uguale al numero di $s$ o $d$). Ogni stringa avrà un certo numero $k$ di $s$ e $(m-k)$ di $d$ e il numero delle stringhe di lunghezza $m$ con $k$ elementi $s$ è dato da $((m),((k, m-k))) = ((m),(k)) = ((m),(m - k)) = (m!)/(k!(m-k)!)$. Il numero di stringhe di lunghezza $m$ sarà allora $\sum_{k=0}^m ((m),(k)) = 2^m$. Si poteva arrivarci anche sfruttando l'isomorfismo tra queste stringhe e le stringhe di 0 e 1 della stessa lunghezza viste come numeri binari.
Possiamo a questo punto vedere la tua stringha come una sequenza di simboli | e * in cui | rappresenta un elemento di $N$ (il primo è inutile considerarlo) e * un elemento di $O$. Per ogni stringa di questo tipo ci saranno $m$ * e $|N|-1$ | e potremo inserire al posto dei * una qualsiasi delle stringhe precedentemente calcolate. Ci sono quindi $((m+1),(|N|-1))$ stringhe di questo tipo ($((m),(|N|-1))$ se non si richiede che la stringa finisca con un elemento di $O$) e quindi un totale di stringhe uguali a $2^m((m+1),(|N|-1))$ (o $2^m((m),(|N|-1))$) stringhe possibili.
In altre parole, gli esempi che hai scritto si ottengono con $m = 3$, $N = \{1, 2, 3, 4 \}$, con stringhe di elementi di $O$ uguali rispettivamente a $ssd$ e $dds$ e stringa di simboli uguale a ||*|**.
Nota che le stringhe di $O$ le puoi ottenere facilmente utilizzando un numero unsigned e continuando a sommare (per poi leggere la sua rappresentazione binaria), mentre credo che il metodo più comodo per ottenere quelle generali sia semplicemente di calcolarti tutte le partizioni della stringa non ordinata (se programmi in C++ esiste next_permutation che può essere usato per ottenere tutte le permutazioni).
Considero prima di tutto le stringhe di lunghezza $m$ di elementi di $O$ (suppongo che $m$ sia minore o uguale al numero di $s$ o $d$). Ogni stringa avrà un certo numero $k$ di $s$ e $(m-k)$ di $d$ e il numero delle stringhe di lunghezza $m$ con $k$ elementi $s$ è dato da $((m),((k, m-k))) = ((m),(k)) = ((m),(m - k)) = (m!)/(k!(m-k)!)$. Il numero di stringhe di lunghezza $m$ sarà allora $\sum_{k=0}^m ((m),(k)) = 2^m$. Si poteva arrivarci anche sfruttando l'isomorfismo tra queste stringhe e le stringhe di 0 e 1 della stessa lunghezza viste come numeri binari.
Possiamo a questo punto vedere la tua stringha come una sequenza di simboli | e * in cui | rappresenta un elemento di $N$ (il primo è inutile considerarlo) e * un elemento di $O$. Per ogni stringa di questo tipo ci saranno $m$ * e $|N|-1$ | e potremo inserire al posto dei * una qualsiasi delle stringhe precedentemente calcolate. Ci sono quindi $((m+1),(|N|-1))$ stringhe di questo tipo ($((m),(|N|-1))$ se non si richiede che la stringa finisca con un elemento di $O$) e quindi un totale di stringhe uguali a $2^m((m+1),(|N|-1))$ (o $2^m((m),(|N|-1))$) stringhe possibili.
In altre parole, gli esempi che hai scritto si ottengono con $m = 3$, $N = \{1, 2, 3, 4 \}$, con stringhe di elementi di $O$ uguali rispettivamente a $ssd$ e $dds$ e stringa di simboli uguale a ||*|**.
Nota che le stringhe di $O$ le puoi ottenere facilmente utilizzando un numero unsigned e continuando a sommare (per poi leggere la sua rappresentazione binaria), mentre credo che il metodo più comodo per ottenere quelle generali sia semplicemente di calcolarti tutte le partizioni della stringa non ordinata (se programmi in C++ esiste next_permutation che può essere usato per ottenere tutte le permutazioni).
"ham_burst":
$O$ rappresenta un insieme di elementi ${s,d}$ con cardinalità $|O|=2*(n-1)$ cioè ci sono $(n-1)\ ,\ s$ e $(n-1)\ ,\ d$.
Il problema perciò diviene, elencare ogni permutazione di $O$ rispetto ad $N$ (permutazione limitata ad un shift sinistro di $O$ su $N$come detto sopra), dove ogni lista risultante dovrà avere $|N|+(|O|-(n-1))$ elementi.
Perciò sarebbe da elencare ogni sottoinsieme di $O$ di dimensione $(n-1)$ cioè $((|O|),((n-1)))$ liste per ogni permutazione di $N$. cioè un bellissimo elenco di circa $(n-2)^2* ((|O|),((n-1)))$ liste
Poiche' i sottoinsiemi di $O$ cercati sono lunghi al piu' $n-1$, si puo' scrivere ogni sottoinsieme come un numero a $n-1$ bit (sarebbe diverso se i sottoinsiemi fossero piu' lunghi, perche' avresti il vincolo che non possono esserci piu' di $n-1$ simboli uguali). Direi che ogni configurazione (del vecchio problema) va arricchita con un intero (mi sembra che il post di Rggb possa essere letto in questo senso) a $n-1$ bit.
Esempio:
$[n_1,n_2,n_3,s,n_4,s,d]$
[tex][n_1,n_2,n_3,o,n_4,o,o] \times (s,s,d)[/tex]
$[n_1,n_2,n_3,d,n_4,d,s]$
[tex][n_1,n_2,n_3,o,n_4,o,o] \times (d,d,s)[/tex]
In termini di permutazioni a partire da $[n_1,..,n_l,s,..,d,..]$ si tratta di coniugare con una permutazione che metta gli elementi di $[s,..,d,..]$ in modo che i primi $n-1$ siano nell'ordine voluto, "dimenticare" gli altri, e fare una delle permutazioni del vecchio problema, per portare i nuovi simboli, che sono gia' nell'ordine giusto, nei recipienti marcati dai "setti" $n_i$.
Il problema, se lo ho spiegato bene, è come potrei far "convivere" uno schift con ogni sottoinsieme di $O$? Sapendo che i due insiemi hanno due rappresentazioni e significati semantici completamente diversi.
Spero di aver capito bene. Il trucco che propongo e' di usare una rappresentazione che riguardi solo gli $O$ e comporla con la vecchia rappresentazione, fingendo che gli 's' e i 'd' siano i vecchi 'o'.
Ringrazio ancora
Figurati! E' un piacere!
bye^2, mr
Edit: Ho letto solo adesso il post di apatriarca. Il che mi conforta, perche' mi sembra che diciamo la stessa cosa
Non ho prima di tutto del tutto chiaro quale sia il significato di n, rappresenta la cardinalità di N?
Sì $n$ è la cardinalità di $|N|$ ho dimenticato di specificarlo.
Gli elementi di $O$ sono $2*(n-1)$ ne più ne meno. L'insieme da permutare con $N$ è un sottoinsieme di $O$ composto da $n-1$ elementi.
Comunque ora con questi dati che mi avete fornito forse riesco a risolvere, vediamo.
Il lavoro adesso sarà fare un po' di pruning....
grazie del'aiuto
Vorrei chiarire un dubbio di definizione.
Quello che alla fine vorrei fare io, è una "permutazione con ripetizione", giusto?
PS: qui ho chiesto un parere su una proprietà dei numeri binari, legato al problema del post. Se interessa e sapete una risposta, ben venga
Quello che alla fine vorrei fare io, è una "permutazione con ripetizione", giusto?
PS: qui ho chiesto un parere su una proprietà dei numeri binari, legato al problema del post. Se interessa e sapete una risposta, ben venga
"ham_burst":
Vorrei chiarire un dubbio di definizione.
Quello che alla fine vorrei fare io, è una "permutazione con ripetizione", giusto?
Una permutazione e' bigettiva tra l'insieme dal quale parti e l'insieme target, forse hai in mente il termine "combinazione con ripetizioni". Neanche quello mi sembra giusto, visto che le tue $\{s,d\}$ sono indistinguibili, mentre le $n_i$ in effetti non permutano nemmeno , fanno da separatori.
Pero' non e' nemmeno importante la terminologia, secondo me. Il problema resta simile a quello della Statistica di Bose-Einstein, laddove hai particelle indistinguibili che possono stare in piu' stati, e piu' particelle possono stare nello stesso stato. Qui hai due specie di particelle, in effetti. Non so se questo parallelo ti e' di aiuto...
PS: qui ho chiesto un parere su una proprietà dei numeri binari, legato al problema del post. Se interessa e sapete una risposta, ben venga
Non ho capito un granche' del post originario, ho capito di piu' l'ultimo post. Pero' ci devo pensare, di botto non mi viene in mente niente.
Vorresti se ho capito bene trovare delle proprieta' dei numeri che in base 2 si scrivono con esattamente tre '1' che ti permettano di enumerarli in maniera piu' efficiente di quella bovina?
bye^2, mr
per la definizione ci siamo, è più chiaro
per il problema, lasciando da parte il discorso del post in questa sezione, perciò lasciando stare l'insieme $N$ $O$ ecc...
non $3$ ma $k$. Io vorrei trovare un modo per elencare (con operazioni primitive non algoritmi, che ho già) tutti i numeri binari con esattamente $k$ bit ad $1$. $k$ lo scelgo da problema a problema.
per il problema, lasciando da parte il discorso del post in questa sezione, perciò lasciando stare l'insieme $N$ $O$ ecc...
esattamente tre '1'
non $3$ ma $k$. Io vorrei trovare un modo per elencare (con operazioni primitive non algoritmi, che ho già) tutti i numeri binari con esattamente $k$ bit ad $1$. $k$ lo scelgo da problema a problema.
È sufficiente elencare tutte le triplette $(a, b, c)$ di numeri da $0$ a $n-1$ e poi calcolare il numero $2^a +2^b + 2^c$. Questo numero avrà esattamente $3$ uno nella rappresentazione binaria.
EDIT: Ho corretto la formula.
EDIT: Ho corretto la formula.
"apatriarca":
È sufficiente elencare tutte le triplette $(a, b, c)$ di numeri da $0$ a $n-1$ e poi calcolare il numero $2^{a + b + c}$. Questo numero avrà esattamente $3$ uno nella rappresentazione binaria.
cosa intendi con "triplette $(a, b, c)$"? Se elevo a potenze, avrò sempre un bit attivo sulla potenza corrispondente...
Se mi fai un esempio esplicito ci capiamo al volo...
Intendo dire generare tutti i sottoinsiemi di tre elementi di $\{0, 1, .. , n-1\}$. Generarli è molto facile supponendo sempre $a < b < c$:
Con questo ciclo genererai tutti e solo i numeri con 3 bit uguali a 1. Ovviamente si può adattare il codice per numeri superiori di bit o inferiori.
for (int a = 0; a < n-2; ++a) {
for (int b = a+1; b < n-1; ++b) {
for (int c = b+1; c < n; ++c) {
// ...
}
}
}
Con questo ciclo genererai tutti e solo i numeri con 3 bit uguali a 1. Ovviamente si può adattare il codice per numeri superiori di bit o inferiori.
davvero molto interessante.
Però questo codice è compile-time dipendente. Cioè devo sapere a-priori il numeri di bit attivi.
Posso supporre un massimo di bit che voglio generare (max. 19), e perciò un massimo di variabili e cicli for, ma è pur sempre un qualcosa che devo scrivere nel codice.
Quello che pensavo si potesse fare, è proprio sommare un numero magico e in iterate differenti ho il numero che mi interessa con $k$ bit attivi.
l'algoritmo che sto implementando è sempre esponenziale, non mi cambia moltissimo inserire questi cicli, ma cerco di fare qualche limitazione e tagli dove posso farli.
Comunque questo pezzo di codice provo a modellarlo con il mio e lo confronto con un'altra implementazione delle permutazioni;
vediamo, intanto grazie mille, no ci sarei arrivato
Però questo codice è compile-time dipendente. Cioè devo sapere a-priori il numeri di bit attivi.
Posso supporre un massimo di bit che voglio generare (max. 19), e perciò un massimo di variabili e cicli for, ma è pur sempre un qualcosa che devo scrivere nel codice.
Quello che pensavo si potesse fare, è proprio sommare un numero magico e in iterate differenti ho il numero che mi interessa con $k$ bit attivi.
l'algoritmo che sto implementando è sempre esponenziale, non mi cambia moltissimo inserire questi cicli, ma cerco di fare qualche limitazione e tagli dove posso farli.
Comunque questo pezzo di codice provo a modellarlo con il mio e lo confronto con un'altra implementazione delle permutazioni;
vediamo, intanto grazie mille, no ci sarei arrivato
@apatriarca: scusa se insisto, ma non comprendo come potrebbe questo codice generare i numeri con 3 bit contemporaneamente attivi.
I numeri con 3 bit attivi fino al decimale 55 sono: ${7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52}$
ma se utilizzo il tuo codice, e se sommo $(a,b,c)$ o elevo a potenza (come hai mostrato sopra), e stampo all'interno dei cicli avrò o le potenze di $2$ o un elenco di numeri consecutivi.....
EDIT: oook, fantastico codice. Ho capito dove sbagliavo
Ti ringrazio moltissimo, mi abbassa il tempo di calcolo di molto (sul mio portatile).
I numeri con 3 bit attivi fino al decimale 55 sono: ${7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52}$
ma se utilizzo il tuo codice, e se sommo $(a,b,c)$ o elevo a potenza (come hai mostrato sopra), e stampo all'interno dei cicli avrò o le potenze di $2$ o un elenco di numeri consecutivi.....
EDIT: oook, fantastico codice. Ho capito dove sbagliavo
Ti ringrazio moltissimo, mi abbassa il tempo di calcolo di molto (sul mio portatile).
"apatriarca":
.... poi calcolare il numero $2^{a + b + c}$.
Mi è chiaro il ragionamento di patriarca, un po meno questo calcolo.
Se le 3 cifre esaminate rappresentato i 3 "1" all'interno del numero binario il calcolo dovrebbe essere diverso .... o mi sfugge qualcosa
Il calcolo delle cifre all'interno del ciclo è così messo:
Alla fine e una somma alternata di potenze, come ci è arrivato non lo so, ma funzione con il mio codice
for (int a = 0; a < n-2; ++a) {
for (int b = a+1; b < n-1; ++b) {
for (int c = b+1; c < n; ++c) {
number = (1<<c)+(1<<b)+(1<<a)
}
}
} Alla fine e una somma alternata di potenze, come ci è arrivato non lo so, ma funzione con il mio codice
Sì certo, credo che l'errore al quale si riferiva anche ham_burst quando ha detto di aver capito dove aveva sbagliato fosse in effetti quello. Ovviamente la formula doveva essere $2^a + 2^b + 2^c$ (per la definizione stessa di rappresentazione binaria di un numero)... Per cui se attivi i bit $(0, 3, 7)$ ottieni il numero $2^0 + 2^3 + 2^7 = 1 + 8 + 128 = 137_10 = 10001001_2$ come è facile osservare. Ho scritto il post velocemente ed è stata una svista.
"ham_burst":
Il calcolo delle cifre all'interno del ciclo è così messo:
for (int a = 0; a < n-2; ++a) { for (int b = a+1; b < n-1; ++b) { for (int c = b+1; c < n; ++c) { number = (1<<c)+(1<<b)+(1<<a) } } }
Alla fine e una somma alternata di potenze, come ci è arrivato non lo so, ma funzione con il mio codice
mbè... cosi' è già diverso.... ORA SI.
non mi sembra complesso il ragionamento, ognuna delle 3 cifre rappresenta un "1" di un numero binario, e quindi vanno sommate tra loro...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo