Ce e în neregulă cu prima funcție de swaping?

Scriu un cod pentru a genera permutarea elementelor unei matrice. Am scris două tipuri diferite de funcții de swap, unul folosind lucrări de stocare temporară bine, în timp ce celălalt care nu utilizează niciun depozit temporar nu generează rezultate. De ce se întâmplă asta?

Următorul cod funcționează bine

#include
#include
using namespace std;
int tt=0;
void swap1 (int v[], int i, int j) {
    int t;

    t = v[i];
    v[i] = v[j];
    v[j] = t;
}   
void permute(int arr[],int n,int index)
{
     if(index==n)
                {
                for(int i=0;i< n ;j++)
         {
           swap1(arr,index,j);
           permute(arr,n,index+1); 
           swap1(arr,j,index);           
         }        
}
int main()
{
    int arr[]={'a','b','c','d'};
    permute(arr,4,0);
    cout<

În timp ce următorul cod nu emite permutările:

#include
#include
using namespace std;
int tt=0;
void swap(int v[],int i,int j)
{
     v[i]= v[i] + v[j];
     v[j]= v[i] - v[j];
     v[i]= v[i] - v[j];
}
void permute(int arr[],int n,int index)
{
     if(index==n)
                {
                for(int i=0;i< n ;j++)
         {
           swap(arr,index,j);
           permute(arr,n,index+1); 
           swap(arr,j,index);           
         }        
}
int main()
{
    int arr[]={'a','b','c','d'};
    permute(arr,4,0);
    cout<
0
Rețineți că std :: swap() există și ar trebui folosit când este posibil, dar funcția swap() poate avea un conflict de nume deoarece folosiți namespace std;
adăugat autor stefaanv, sursa

2 răspunsuri

Vă rog, pentru dragostea oricăror zeități pe care le credeți (sau altfel), nu utilizați hack-uri urâte, cum ar fi cea de-a doua funcție swap (sau temutul XOR-swap truc).

Sunt total inutile și, în general, mai lent decât o soluție tipică variabilă temporară. De asemenea, acestea vor determina apariția codului dvs. pe site-uri precum Daily WTF și generații de programatori (care au pentru a menține astfel de crustă) vă va blestema numele de-a lungul secolelor următoare :-)

Și, în orice caz, nu vor funcționa dacă cele două elemente pe care le "schimbi" sunt aceleași, deoarece, în momentul în care faceți:

v[i]= v[i] + v[j];

unde i și j sunt aceeași valoare, ați pierdut informațiile necesare pentru ca ceilalți pași să funcționeze.

Puteți vedea acest lucru în acțiune după cum urmează. Să presupunem că aveți două variabile distincte , a = 20 și b = 30 . Lucrați prin pașii dvs.:

a = a + b; //a <- (20 + 30) = 50, b still = 30.
b = a - b; //b <- (50 - 30) = 20, a still = 50.
a = a - b; //a <- (50 - 20) = 30, b still = 20.

Și ele sunt schimbate, deși probabil că doriți să vă uitați în cazurile de margine cu scheme de depășire și codificare care nu sunt complementul celor doi (în C oricum, nu sunteți sigur dacă C ++ vă permite să completați sau să semnați magnitudine).

Dar să vedem ce se întâmplă atunci când ambele a și b sunt aceeași variabilă (nu aceeași valoare aceeași variabilă, ca referință). Deci, "amândouă" au valoarea de 20 și ați aștepta ca aceștia să rămână amândoi 20 după o schimbare, dar să aruncăm o privire:

a = a + b; //a <- (20 + 20) = 40, AND b = 40 as well.
b = a - b; //b <- (40 - 40) =  0, AND a =  0 as well.
a = a - b; //a <- ( 0 -  0) =  0, AND b =  0 as well.

Acesta este nu cu adevărat rezultatul așteptat.

0
adăugat
@paxdiablo mulțumesc pentru sugestie ....
adăugat autor manyu, sursa
+1 pentru a împiedica utilizatorii să folosească hack-uri urâte care nu au niciun beneficiu, deoarece ne-am îndepărtat de la utilizarea limbajului de asamblare pe microprocesoare pe 8 biți ...
adăugat autor Axel, sursa
În plus, în funcție de conținutul matricei, se poate întâmpla o depășire/scurgere în timpul calculului.
adăugat autor swegi, sursa
void swap(int v[],int i,int j)
{
     v[i]= v[i] + v[j];
     v[j]= v[i] - v[j];
     v[i]= v[i] - v[j];
}

nu functioneaza atunci cand i == j (apoi setati v [i] la 0), ceea ce se intampla cu bucla

for (int j = index; j < n; ++j) {
    swap(arr, index, j);
0
adăugat
Doar nu mi-am dat seama de mintea mea ... Mulțumesc mult că mi-ai salvat mult timp. :)
adăugat autor manyu, sursa