Question

Calculate all permutations for an array of integers.

For example: Given {3, 5, 8} - Output should be: { 3, 5, 8 }, { 3, 8, 5 }, { 5, 3, 8 }, { 5, 8, 3 }, { 8, 5, 3 }, { 8, 3, 5 }

Answer 1

here is the link for the theory part of this program, basically what we here trying to implement is recursion tree see more by following the link:http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
code:

#include<bits/stdc++.h>
using namespace std;

void Swap(int *x,int *y){
    int temp;
    temp=*x;
    *x=*y;
    *y=temp;
}
void permute(int *A,int start, int end,int n){
    int i,j;
    if(start==end){
     for(i=0;i<n;i++)
      cout << A[i];
    cout << endl;
    }
    for(j=start;j<=end;j++){
        Swap(A+start,A+j);
        permute(A,start+1,end,n);
        Swap(A+start,A+j); // here we are backtracking, means we are restoring the previous order of the array elements 
    }
}
int main(){
    int n,i;
    // take input size of an array
    cin >> n;
    int A[n];
    for(i=0;i<n;i++)
        cin >> A[i];
    permute(A,0,n-1,n);
  return 0;
}

complexity is O(n*n!) as n! are the number of arrangements for n elements and n for printing the elements.