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
Sembra che ham_burst l'abbia risolto da solo.. Abbiamo risposto tutti insieme.. 
"apatriarca":
Ho scritto il post velocemente ed è stata una svista.
OK. Intanto avevo scritto il precedente post.
ringrazio tutti per l'interessamento al mio problema, adesso vediamo se l'algoritmo, implementato in codice, risolve il problema
Non vorrei chiedere troppo, ma ci sarebbe un modo per elencarli in ordine numerico (decimale) crescente, utilizzando qui cicli...
Se vuoi un ordinamento, devi necessariamente dare un "peso maggiore" alle cifre più esterne al ciclo.
Se, ad esempio, vuoi un ordinamento decrescente, potresti fare un ciclo che parte da n per scendere a 1, quindi con decrementi delle cifre.
Ottieni qualcosa di simile:
La prima tabella è quella già fatta (non ordinata, vedi valori in rosso).
La seconda tabella è la nuova che risulta ordinata
Se, ad esempio, vuoi un ordinamento decrescente, potresti fare un ciclo che parte da n per scendere a 1, quindi con decrementi delle cifre.
Ottieni qualcosa di simile:
La prima tabella è quella già fatta (non ordinata, vedi valori in rosso).
La seconda tabella è la nuova che risulta ordinata
Per un ordinamento crescente devi scegliere le cifre dalla più significativa alla meno significativa:
for (int a = 2; a < n; ++a) {
for (int b = 1; b < a; ++b) {
for (int c = 0; c < b; ++c) {
number = (1<<c)+(1<<b)+(1<<a)
}
}
}
Great, grazie ad entrambi.
la visuale in tabella è stata stra-utile
la visuale in tabella è stata stra-utile
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo