0

I was using a permutation function to compute all the permutations of an array in C language. A prototype of the function is :

#include <stdio.h>
int arr1[]={1,2,3,4,5},N,i,x,j;

void swap1(int s,int t)
{

    int temp1=arr1[s];
    arr1[s]=arr1[t];
    arr1[t]=temp1;
}

void permutate(int i)
{  
    if(i==N){
      for(x=0;x<N;x++){
        printf("%d",arr1[x]);
      }
    printf("\n");
   }
   else{
      for(j=i;j<N;j++){
        swap1(i,j);
        permutate(i+1);
        swap1(i,j);
      }
   }
}

int main(void)
{
        N=5;
        permutate(0);
    return 0;
}

Howewer,it just printed me the first combination. I debugged for a while and found out that adding a local variable 'j' to permutate function, it worked.

 void permutate(int i){
    int j;                  <<<---this is my problem
    if(i==N){
      for(x=0;x<N;x++){
        printf("%d",arr1[x]);
      }
    printf("\n");
   }
   else{
      for(j=i;j<N;j++){
        swap1(i,j);
        permutate(i+1);
        swap1(i,j);
      }
   }
}

Why is it occurring like this,when it is being initialized in for loop too and the value is not changed anywhere else?

kapilgm
  • 1,620
  • 1
  • 15
  • 22
  • 1
    ....because of your function is recursive...... – LPs Aug 30 '16 at 10:26
  • 4
    track the variable `j` with a print in the loop and you will see why... You need a "private" `j` for each call to permutate, if not recursion is short-circuited. – Jean-Baptiste Yunès Aug 30 '16 at 10:27
  • You just find why everyone discourages using global variable ;) break re-entrance, have side effect on global program, .... see http://stackoverflow.com/questions/484635/are-global-variables-bad – Garf365 Aug 30 '16 at 10:28

1 Answers1

0

You wrote a recursive function.

Using a global variable j each recursive call change the value of the global value.

So the value of j when it return from recursion is changed: the value before the call is lost.

LPs
  • 16,045
  • 8
  • 30
  • 61