0

We have an array, int array={1,2,3};
Display all the possible permutations which will be 

{1,3,2} ,
{2,1,3} , 
{2,3,1} , 
{3,1,2} , 
{3,2,1} etc.


all n! possibilities.

I know both ways direct recursive and backtracking too.
Is there any better way to do the same ?
Thank You.

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
Pushpa
  • 448
  • 3
  • 10

1 Answers1

1

You can use the methods described here.

You can modify his algo slightly for your need:

#include <stdio.h>


void print(const int *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%c", i ? ',':'{');
      printf("%d", v[i] );
    }
    printf("}\n");
  }
} // print


void permute(int *v, const int start, const int n)
{  
  if (start == n-1) {
    print(v, n);
  }
  else {
    for (int i = start; i < n; i++) {
      int tmp = v[i];

      v[i] = v[start];
      v[start] = tmp;
      permute(v, start+1, n);
      v[start] = v[i];
      v[i] = tmp;
    }
  }
}


int main(void)
{
  int v[] = {1, 2, 3};
  permute(v, 0, sizeof(v)/sizeof(int));
}

Live example here

As described in other answer, C++ stl library provides an implmentation of next_permutation. You can peep inside stl code and make necessary changes to port it to C code.

Gyapti Jain
  • 4,056
  • 20
  • 40
  • Yes thank you.I still do't have a 15 point so won't be able to +1 , but I Started with the same code as above but what I want is that whether possible to reduce it? or is there exists any declarative way to the same In C or at least an algo overview of the same. – Pushpa Dec 22 '14 at 06:28
  • @Pushpa Try to understand the logic behind the code and try to reduce it by making 1 change each time and recompile and verify the result. You should be able to reduce it to your requirements in some time. – Gyapti Jain Dec 22 '14 at 07:08