Problema con scambio complicato (LA VENDETTA =)
Grazie a Vict ho capito dove sbagliavo nel cercare di ordinare elementi nel modo più veloce e con il minimo di cicli.
http://www.matematicamente.it/forum/viewtopic.php?f=15&t=130524
Ora vorrei ordinare un array di N interi tutti diversi, anzi sono sempre tutti gli interi fra 1 e N.
Ad ogni turno posso scambiare due elementi a scelta dell’array ma, per fare cio, pago un prezzo
pari alla somma dei due elementi. (Ad es: per scambiare di posto l’elemento 3 e l’elemento 4 pago 7)
Vorrei trovare il metodo più economico che ottimizza il prezzo!
(Prima vict85 ha risolto in modo efficente ordinando nel modo più veloce con i passi più brevi)
http://www.matematicamente.it/forum/viewtopic.php?f=15&t=130524
Ora vorrei ordinare un array di N interi tutti diversi, anzi sono sempre tutti gli interi fra 1 e N.
Ad ogni turno posso scambiare due elementi a scelta dell’array ma, per fare cio, pago un prezzo
pari alla somma dei due elementi. (Ad es: per scambiare di posto l’elemento 3 e l’elemento 4 pago 7)
Vorrei trovare il metodo più economico che ottimizza il prezzo!
(Prima vict85 ha risolto in modo efficente ordinando nel modo più veloce con i passi più brevi)
Risposte
Idee?? Non so farlo ma penso si possa ragionare sempre sul fatto che ogni numero ha una certo ordine particolare.
Pensando poi al fatto di "pagare" sarebbe conveniente prendere i numeri piccoli per spostare qualcosa: privilegiare ad esempio il numero uno rispetto ad altri e così via.
Ma forse serve conoscere bene pure la teoria dei grafi... (che devo ancora studiare...)
Pensando poi al fatto di "pagare" sarebbe conveniente prendere i numeri piccoli per spostare qualcosa: privilegiare ad esempio il numero uno rispetto ad altri e così via.
Ma forse serve conoscere bene pure la teoria dei grafi... (che devo ancora studiare...)
Senza dubbio \(\displaystyle (1,\,2,\,3,\,4,\,5,\,6) = (1,\,6)(1,\,5)(1,\,4)(1,\,3)(1,\,2) \) che ha somma minore di quella usata precedentemente \(\displaystyle (1,\,2,\,3,\,4,\,5,\,6) = (1,\,2)(2,\,3)(3,\,4)(4,\,5)(5,\,6) \) nel secondo codice (il primo usava il primo). Ma che il tutto rimanga minimale andrebbe dimostrato.
Ah tu dici l'ultimo codice che hai proposto già risolve? Basta sommare poi i valori per vedere il prezzo minimo risultante?
Se ho un array dato, da ordinare, del tipo 3 2 4 1:
per una sequenza di lunghezza minima (problema precedente) si scambia di posizione 1 e 3 e dopo scambio 3 e 4.
Ora la sequenza di costo minimo è solo quella data dallo scambio tra 1 e 4 e poi 1 e 3.
Certo non posso calcolare un prezzo senza ordinare prima...
Se ho un array dato, da ordinare, del tipo 3 2 4 1:
per una sequenza di lunghezza minima (problema precedente) si scambia di posizione 1 e 3 e dopo scambio 3 e 4.
Ora la sequenza di costo minimo è solo quella data dallo scambio tra 1 e 4 e poi 1 e 3.
Certo non posso calcolare un prezzo senza ordinare prima...
No, nessuno dei due è adatto senza qualche modifica. E comunque il tutto andrebbe dimostrato. Non è detto che convenga usare un numero minimale di scambi.
\(\displaystyle (5,\,6,\,7,\,8,\,9)\cdot (5,\,6)(5,\,7)(5,\,8)(5,\,9) = (5,\,9)(5,\,8)(5,\,7)(5,\,6)\cdot (5,\,6)(5,\,7)(5,\,8)(5,\,9) = e \)
Perciò \(\displaystyle (5,\,6)(5,\,7)(5,\,8)(5,\,9) \) ha somma minimale tra quelli con numero di scambi minimo. La sua somma è \(\displaystyle 5\times 4 + 6+ 7+ 8+ 9 = 50 \). È evidente che ogni somma deve essere superiore a \(\displaystyle 5+6+7+8+9 \).
Vediamo ora come si può cercare di ridurre questa somma sfruttando l'elemento \(\displaystyle 1 \).
\(\displaystyle (5,\,6,\,7,\,8,\,9)(1,\,9,\,8,\,7,\,6,\,5)(1,\,5) = e \)
inoltre \(\displaystyle (1,\,9,\,8,\,7,\,6,\,5) = (1,\,5)(1,\,6)(1,\,7)(1,\,8)(1,\,9) \) perciò si ha che \(\displaystyle (1,\,5)(1,\,6)(1,\,7)(1,\,8)(1,\,9)(1,\,5) \) è una serie di scambi non minimali che inverte \(\displaystyle (5,\,6,\,7,\,8,\,9) \). La somma degli scambi è \(\displaystyle 1\times 6 + 5\times 2 + 6 + 7+ 8+ 9 = 5\times 2 + 6\times 2 + 7+ 8+ 9 = 46 \) che è minore del risultato trovato prima. Ma non lo è sempre, quindi sarebbe necessario misurare i due costi e poi applicare quello minore. Per lo meno quando vi è un solo ciclo disgiunto che non sia né uno scambio (se stesso è minimale in tutti i sensi) ne contenga 1. Se ce né più di uno potrebbe essere possibile trovare un metodo migliore.
Perciò \(\displaystyle (5,\,6)(5,\,7)(5,\,8)(5,\,9) \) ha somma minimale tra quelli con numero di scambi minimo. La sua somma è \(\displaystyle 5\times 4 + 6+ 7+ 8+ 9 = 50 \). È evidente che ogni somma deve essere superiore a \(\displaystyle 5+6+7+8+9 \).
Vediamo ora come si può cercare di ridurre questa somma sfruttando l'elemento \(\displaystyle 1 \).
\(\displaystyle (5,\,6,\,7,\,8,\,9)(1,\,9,\,8,\,7,\,6,\,5)(1,\,5) = e \)
inoltre \(\displaystyle (1,\,9,\,8,\,7,\,6,\,5) = (1,\,5)(1,\,6)(1,\,7)(1,\,8)(1,\,9) \) perciò si ha che \(\displaystyle (1,\,5)(1,\,6)(1,\,7)(1,\,8)(1,\,9)(1,\,5) \) è una serie di scambi non minimali che inverte \(\displaystyle (5,\,6,\,7,\,8,\,9) \). La somma degli scambi è \(\displaystyle 1\times 6 + 5\times 2 + 6 + 7+ 8+ 9 = 5\times 2 + 6\times 2 + 7+ 8+ 9 = 46 \) che è minore del risultato trovato prima. Ma non lo è sempre, quindi sarebbe necessario misurare i due costi e poi applicare quello minore. Per lo meno quando vi è un solo ciclo disgiunto che non sia né uno scambio (se stesso è minimale in tutti i sensi) ne contenga 1. Se ce né più di uno potrebbe essere possibile trovare un metodo migliore.
Costruiamo un grafo pesato in cui ogni nodo è una permutazione e gli archi sono gli scambi con peso dato dalla somma dei valori dello scambio. La soluzione al tuo problema è allora semplicemente il cammino di lunghezza minimo in questo grafo tra la permutazione di partenza e l'identità. Peccato che il metodo sia poco pratico per ragioni sia di spazio che di tempo.. ;D
Grazie ragazzi!
Provo ad aiutarmi con un vettore di booleani
Provo ad aiutarmi con un vettore di booleani
#include <fstream>
#include <vector>
#include <climits>
using namespace std;
vector<int> vec;
//Contiene quali posizioni sono state processate
vector<bool> vis;
int main(void)
{
ifstream in("input.txt");
int N;
in >> N;
vec.resize(N+1);
vis.resize(N+1,false);
for(int i=1;i<=N;i++)
in>>vec[i];
int mosse=0;
int prezzo=0;
for(int i=1;i<=N;i++){
//Se non abbiamo ancora lavorato con questa posizione
if(!vis[i]){
if(vec[i]!=i){
//Mantengo la somma del ciclo di posizioni
int sum=0;
//Il piú piccolo degli interi di questo ciclo
int mn=INT_MAX;
int cur=i;
int num=0;
while(!vis[vec[cur]]){
mn=min(mn,vec[cur]);
sum+=vec[cur];
vis[vec[cur]]=true;
cur=vec[cur];
num++;
}
//Prezzo senza "prendere in prestito"
int cp=(num-1)*mn + sum -mn;
//Prezzo prendendo in prestito
if(mn!=1)
cp=min(cp, 2*(1+mn) + num-1 + sum -mn);
prezzo+=cp;
//Un ciclo di num interi ha bisogno di num-1 mosse
mosse+=num-1;
}
vis[i]=true;
}
}
ofstream out("output.txt");
out<<mosse<<" "<<prezzo<<endl;
return 0;
}
Non l'ho fatto io ma mi sembrava giusto postare il codice per chiudere il post.
PS: Sinceramente non l'ho manco capito benissimo ancora
Da un'occhiata veloce trova il minimo tra le due formule che avevo usato nel mio ultimo post. Insomma calcola il minimo tra il costo del ciclo e quello del passare da 1. Comunque spreca calcolo cercando sempre l'elemento minimo anche se lo possiede già. Quindi ha margini di miglioramento.
Beato te Vict che vedi un ulteriore miglioramento 
Per me, se non avessi avuto la soluzione, risultava un problema quasi irrisolvibile...
Vorrà dire che la strada è lunga: dovrò impegnarmi di più!
Credo pure che Apatriarca avesse dato una linea da seguire visualizzando tutto coi grafi.
Sbaglio?
Per me, se non avessi avuto la soluzione, risultava un problema quasi irrisolvibile...
Vorrà dire che la strada è lunga: dovrò impegnarmi di più!
Credo pure che Apatriarca avesse dato una linea da seguire visualizzando tutto coi grafi.
Sbaglio?
I principi su cui si basa questo metodo sono i seguenti:
1) Per i singoli cicli c'è un modo per determinare il minimo numero di scambi
2) Dati due cicli disgiunti il minimo è fare lo scambio ad uno e all'altro separatamente e indipendentemente.
Dati questi due ipotesi (io non le ho ancora dimostrate) si ha il metodo usato sopra.
Il punto qui è che però lui/lei ignora una cosa.
Se il ciclo esterno è arrivato a \(\displaystyle i \) allora ogni indice inferiore è già comparso in qualche ciclo. Quindi \(\displaystyle i+1 \) è l'elemento minimo.
Inoltre veniamo alle formule.
Se si ha il ciclo \(\displaystyle (a_0\, a_1,\dotsc, a_n) \) allora la trasformazione \(\displaystyle (a_0\, a_1)\dotsb (a_0\,a_n) \) ha ‘peso’ \begin{align}w_1 &= n a_0 + \sum_{i = 1}^n a_i \\
&= (n-1)a_0 + \sum_{i = 0}^n a_i \\
&= n-1 + (n-1)(a_0-1) + n + 1 + \sum_{i = 0}^n (a_i-1) \\
&= 2n + (n-1)(a_0-1) + \sum_{i = 0}^n (a_i-1) \end{align} dove ho tirato fuori gli indici del C++.
L'uso invece di \(\displaystyle (1\, a_0)(1\, a_1)\dotsb (1\,a_n)(1\, a_0) \) ha peso \begin{align}w_2 &= (n+2) + a_0 + \sum_{i = 0}^n a_i \\
&= 2(n+2) + (a_0-1) + \sum_{i = 0}^n (a_i-1) \\
&= 2n + 4 + (a_0-1) + \sum_{i = 0}^n (a_i-1) \end{align}
Se io ora faccio \(\displaystyle w_1 - w_2 \) ricavo \(\displaystyle (n-2)(a_0-1) - 4 \) che fornisce una condizione piuttosto comoda per determinare quale delle due formule conviene. Inoltre il fattore \(\displaystyle 2n + (a_0-1) + \sum_{i=0}^{n} (a_i-1) \) è comune ad entrambi i pesi.
1) Per i singoli cicli c'è un modo per determinare il minimo numero di scambi
2) Dati due cicli disgiunti il minimo è fare lo scambio ad uno e all'altro separatamente e indipendentemente.
Dati questi due ipotesi (io non le ho ancora dimostrate) si ha il metodo usato sopra.
Il punto qui è che però lui/lei ignora una cosa.
Se il ciclo esterno è arrivato a \(\displaystyle i \) allora ogni indice inferiore è già comparso in qualche ciclo. Quindi \(\displaystyle i+1 \) è l'elemento minimo.
Inoltre veniamo alle formule.
Se si ha il ciclo \(\displaystyle (a_0\, a_1,\dotsc, a_n) \) allora la trasformazione \(\displaystyle (a_0\, a_1)\dotsb (a_0\,a_n) \) ha ‘peso’ \begin{align}w_1 &= n a_0 + \sum_{i = 1}^n a_i \\
&= (n-1)a_0 + \sum_{i = 0}^n a_i \\
&= n-1 + (n-1)(a_0-1) + n + 1 + \sum_{i = 0}^n (a_i-1) \\
&= 2n + (n-1)(a_0-1) + \sum_{i = 0}^n (a_i-1) \end{align} dove ho tirato fuori gli indici del C++.
L'uso invece di \(\displaystyle (1\, a_0)(1\, a_1)\dotsb (1\,a_n)(1\, a_0) \) ha peso \begin{align}w_2 &= (n+2) + a_0 + \sum_{i = 0}^n a_i \\
&= 2(n+2) + (a_0-1) + \sum_{i = 0}^n (a_i-1) \\
&= 2n + 4 + (a_0-1) + \sum_{i = 0}^n (a_i-1) \end{align}
Se io ora faccio \(\displaystyle w_1 - w_2 \) ricavo \(\displaystyle (n-2)(a_0-1) - 4 \) che fornisce una condizione piuttosto comoda per determinare quale delle due formule conviene. Inoltre il fattore \(\displaystyle 2n + (a_0-1) + \sum_{i=0}^{n} (a_i-1) \) è comune ad entrambi i pesi.
Mi sono accorto che il tuo codice conta in modo errato le mosse perché nel caso in cui “prenda in prestito l'1” deve fare due mosse in più.
----------------------------------------------------
EDIT: Ho modificato il messaggio perché mi sono accorto che il vettore nel tuo codice aveva come primo elemento la dimensione del vettore. E avendolo letto erroneamente mi sembrava facesse il calcolo errato.
----------------------------------------------------
EDIT: Ho modificato il messaggio perché mi sono accorto che il vettore nel tuo codice aveva come primo elemento la dimensione del vettore. E avendolo letto erroneamente mi sembrava facesse il calcolo errato.
In realtà non proponevo alcun metodo particolare. Volevo solo mostrare come fosse possibile vedere questo problema sotto una luce diversa usando la teoria dei grafi, ma il metodo proposto non era fattibile per la esagerata richiesta di spazio e tempo di calcolo. È comunque utile averlo presente nel caso in cui si facessero richieste un po' diverse. Se per esempio si richiedesse la condizione aggiuntiva che la differenza tra i due valori nelle coppie sia minore di un qualche valore k, l'approccio basato sui grafi potrebbe rendersi utile.
Grazie ragazzi!
A livello di mero codice cosa proponete?
A livello di mero codice cosa proponete?
A livello di mero codice, e includendo la dimensione nel vettore in posizione 0. Sono giunto a questa versione modificata dal codice da te proposto. Fai solo attenzione al fatto che ho usato delle funzioni C++11 per generare delle permutazioni casuali. Avrei ovviamente potuto evitare di usare il vettore di bool come nell'altra discussione.
#include <vector>
#include <random> // questa libreria è C++11
#include <algorithm>
#include <numeric>
#include <iostream>
/*
* ATTENZIONE: questa funzione è C++11
*/
int generate_permutation(std::vector<int> &v, unsigned const n)
{
if (!v.empty())
v.clear();
v = std::vector<int>(n+1, 1);
std::partial_sum(v.begin()+1, v.end(), v.begin()+1);
v.at(0) = n;
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v.begin()+1, v.end(), g);
return n;
}
int cont_weight_swaps(std::vector<int> const &p, int & prezzo)
{
int const n = p[0];
int const N = n + 1;
std::vector<bool> vis(N, true);
int mosse = 0;
prezzo = 0;
for (int i = 1; i != N; ++i) {
if (vis[i]) {
if (p[i] != i ) {
prezzo += 2*i;
int m = 0;
int j = p[i];
while (j != i) {
prezzo += j;
vis[j] = false;
++m;
j = p[j];
}
int t = (m - 2)*i;
int const t2 = 2 + m;
if (t > t2) {
t = t2;
mosse += 2;
}
prezzo += t;
mosse += m;
}
vis[i] = false;
}
}
return mosse;
}
int main(void)
{
// Creo una permutazione
std::vector<int> v;
generate_permutation(v, 2745);
int prezzo;
int const mosse = cont_weight_swaps(v, prezzo);
std::cout << mosse << " " << prezzo << std::endl;
return 0;
}
C++11 va benissimo, grazie Vic!!
L'indice che parte da uno era per comodità poiché si ragionava coi grafi.
Quindi matrice di adiacenza con la prima riga che contiene N e M: numero di nodi e numero di archi.
Successive M righe contengono gli archi (eventualmente con peso).
Lista di adiacenza implementata come array di vector o vector di vector. Se servono altre variabili (open, close) si creano altri array. Poi si leggeva da file dove la prima riga contiene la lunghezza dell’array e la riga successiva contiene l’array, con gli elementi separati da spazio.
esempio :
-------------------
4
3 2 4 1
-------------------
Semplice output che contiene due interi: il primo intero rappresenta il numero minimo di turni per ottenere
l’array ordinato ed il secondo intero rappresenta il prezzo minimo per ordinare l’array.
esempio :
--------------------
2 9
--------------------
Il numero minimo di mosse per un ciclo di N elementi è N − 1 e la soluzione più ovvia sposta sempre l’elemento piu piccolo con gli altri elementi. Potrebbe convenire “prendere in prestito” l’elemento 1, scambiandolo con l’elemento più piccolo del ciclo, poi ordinare il resto del ciclo e rimettere a posto giusto l’elemento 1.
L'indice che parte da uno era per comodità poiché si ragionava coi grafi.
Quindi matrice di adiacenza con la prima riga che contiene N e M: numero di nodi e numero di archi.
Successive M righe contengono gli archi (eventualmente con peso).
Lista di adiacenza implementata come array di vector o vector di vector. Se servono altre variabili (open, close) si creano altri array. Poi si leggeva da file
esempio
-------------------
4
3 2 4 1
-------------------
Semplice output che contiene due interi: il primo intero rappresenta il numero minimo di turni per ottenere
l’array ordinato ed il secondo intero rappresenta il prezzo minimo per ordinare l’array.
esempio
--------------------
2 9
--------------------
Il numero minimo di mosse per un ciclo di N elementi è N − 1 e la soluzione più ovvia sposta sempre l’elemento piu piccolo con gli altri elementi. Potrebbe convenire “prendere in prestito” l’elemento 1, scambiandolo con l’elemento più piccolo del ciclo, poi ordinare il resto del ciclo e rimettere a posto giusto l’elemento 1.
Dopo aver passato un po’ di tempo con gente che lavora sui solutori dell'algebra lineare tendo ad evitare oggetti come array di vector o vector di vector. Detto questo sono piuttosto confuso dalle tue parole. È la prima volta che parli di grafi e non si usano grafi, in genere, per ordinare array.
Non capisco quindi il collegamento tra la prima e la seconda parte del tuo discorso.
Riguardo al prendere in prestito si è sfruttato il fatto che la struttura ciclica si mantiene per coniugazione. Detto questo non penso che computazionalmente ci siano ragioni per ritenere questo peso sensato. Rispesso a quello della prima discussione intendo e ignorando la questione puramente teorica.
Non capisco quindi il collegamento tra la prima e la seconda parte del tuo discorso.
Riguardo al prendere in prestito si è sfruttato il fatto che la struttura ciclica si mantiene per coniugazione. Detto questo non penso che computazionalmente ci siano ragioni per ritenere questo peso sensato. Rispesso a quello della prima discussione intendo e ignorando la questione puramente teorica.
Mi sembra che l'esercizio era stato proposto anni fa alle olimpiadi dell'informatica ed era giusto un esercizio che non sono riuscito a risolvere. La soluzione proposta che ho "copiato_ed_incollato" penso sia stata pensata proprio come suggeriva apatriarca immaginando di risolverla coi grafi. Forse, nell'ultimo post, non mi ero spiegato bene; avevo solo immaginato e descritto la "creatività" avuta da coloro i quali hanno risolto in quel modo il suddetto esercizio.
"Giova411":
Mi sembra che l'esercizio era stato proposto anni fa alle olimpiadi dell'informatica ed era giusto un esercizio che non sono riuscito a risolvere. La soluzione proposta che ho "copiato_ed_incollato" penso sia stata pensata proprio come suggeriva apatriarca immaginando di risolverla coi grafi. Forse, nell'ultimo post, non mi ero spiegato bene; avevo solo immaginato e descritto la "creatività" avuta da coloro i quali hanno risolto in quel modo il suddetto esercizio.
Non direi, il metodo con i grafi arriva alla soluzione ma ha senso solo se non hai assolutamente idea di come procedere. Insomma è esponenziale mentre questo è lineare. Esistono metodi per ridurre l'esponenziale ma questo è un procedimento che non è basato minimamente su quello con i grafi (in realtà parlerei più di alberi). Ritengo che abbia usato delle considerazioni sull'insieme delle permutazioni esattamente come ho fatto io.
OII di che anno e che livello?
No forse non proprio OII, ma penso che sia stato preso da un Collegiate Programming Contest di Valencia (massimo 4 anno). Oppure da onlinejudge.... Insomma so solo che mi ha bloccato de giorni =(
Come riferimento prendo la tua soluzione e ti ringrazio tanto!
Come riferimento prendo la tua soluzione e ti ringrazio tanto!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo