permutations

[DalekThay]

I am having problems with understanding this code. The program should write all permutations of first N numbers.

#include <stdio.h>
#include <iostream>
using namespace std;
void print(const int *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
  }
}
void visit(int *Value, int N, int k)
{
  static int level = -1;
  level = level+1; Value[k] = level;

  if (level == N)
    print(Value, N);
  else
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)
        visit(Value, N, i);

  level = level-1; Value[k] = 0;
}
main()
{
  const int N = 3;
  int Value[N];
  for (int i = 0; i < N; i++) {
    Value[i] = 0;
  }
  visit(Value, N, 0);
system("PAUSE");
}

This part of code is hard to understand

static int level = -1;
level = level+1; Value[k] = level;

I mean, i understand it but the question is WHY? ...I am having problems with permutations for a while now.

[DalekThay]

I got it..sorry for bothering you..only thing that I don't understand is:
how does function "visit" gets called after the permutation is printed...when level reaches 3 ...the if condition is correct and it prints permutation..comes back to the visit ...decrements level..and what then?

[raptr_dflo]

After it prints the permutation, it decrements level, returns the k'th element of Value to 0, and returns from this call of visit() to where it was called from -- in this case back to line 23 of the previous call to visit() and it continues with the for-loop. This is the essence of recursion(): the function calls itself, presumably with different parameters and some notion of when to stop calling itself so it doesn't get stuck forever. Instead of:

function a() calls function b(), which calls function c(); when function c() returns, control picks back up in function b(); when function b() returns, control picks back up in function a()

you have:

function a() calls iteslf, which calls itself; when the third invocation returns, control picks back up in the second invocation; when the second invocation returns, control picks back up in the original.

[MrEARTHSHAcKER]

function a() calls iteslf, which calls itself; when the third invocation returns, control picks back up in the second invocation; when the second invocation returns, control picks back up in the original.

Yes, but the code goes like this:

if (level == N)
    print(Value, N);
  else
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)
        visit(Value, N, i);

So if level is equal to N, it will print.
Else it will start to increment i, until Value equals to 0, when it calls visit(Value,N,i).

So if level is equal to N already, doesn't it mean compiler will skip the part where function is being called by itself?!

[raptr_dflo]

So if level is equal to N already, doesn't it mean compiler will skip the part where function is being called by itself?!

Yes, that's exactly what it's supposed to do. level starts out as zero (well, -1, then immediately increments itself to zero), and by the time it equals N you've finished creating a permutation, so you print the contents of the Value array and return. This is the part about stopping the recursion so it doesn't get stuck in there forever. The else part takes care of what to do when it's not finished yet, including calling itself.

I will agree that this is really ugly code, but if you haven't figured out what it does yet: it puts 1 (level) in each possible position of Value (since they're all zero), then calls Visit(N, k) for each remaining empty position k (where level will then be 2), and so on until it has used all of the valid values of level (the last remaining slot will still be zero, but that's OK, it's a valid value for a slot). If you want to see it working, call print() from a variety of additional places and watch how the values change!