The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Problem :-
Print all possible permutation of array elements.
Consider the array { 3, 2, 5 }.
Possible permutations : { 3, 2, 5 } | { 3, 5, 2 } | { 2, 3, 5 } | { 2, 5, 3 } | { 5, 2, 3 } | { 5, 3, 2 }

Solution :-
An array of length n has n ! permutations.
The implementation show below uses a recursive approach with swapping of array elements to obtain possible permutations
and then swapping of elements in the permuted arrays to obtain further permutations.
We iterate over the array elements and at each iteration level, we do the swap and permute step described above. After
the jth iteration, j elements in the obtained permuted arrays are fixed and we move to the next iteration.

#include<iostream>using namespace std;
// swap elements in the arrayvoid swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
// print the permutationvoid printPermute(int arr[],int size) {
int i;
for (i=0;i<=size;i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
// permute the elements recursivelyvoid permute(int arr[],int start_idx,int end_idx) {
int i;
if (start_idx == end_idx) {
printPermute(arr,end_idx);
}
for (i=start_idx;i<=end_idx;i++) {
swap(arr,start_idx,i);
permute(arr,start_idx+1,end_idx);
swap(arr,start_idx,i);
}
}
// mainint main() {
int arr[] = {3,2,5};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nAll possible permutations of the given array :-\n";
permute(arr,0,size-1);
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// swap elements in the arrayvoid swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
// print the permutationvoid printPermute(int arr[],int size) {
int i;
for (i=0;i<=size;i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
// permute the elements recursivelyvoid permute(int arr[],int start_idx,int end_idx) {
int i;
if (start_idx == end_idx) {
printPermute(arr,end_idx);
}
for (i=start_idx;i<=end_idx;i++) {
swap(arr,start_idx,i);
permute(arr,start_idx+1,end_idx);
swap(arr,start_idx,i);
}
}
// mainint main() {
int arr[] = {3,2,5};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nAll possible permutations of the given array :-\n";
permute(arr,0,size-1);
cout<<endl;
return 0;
}