# Calculate all permutations for an array of integers.

67 views

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 }

posted Aug 23, 2016

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.

Similar Questions
Say the given string is `ABC`
Output should be `ABC` `ACB` `BAC` `BCA` `CBA` `CAB`