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 }
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.
Say the given string is ABC
ABC
Output should be ABC ACB BAC BCA CBA CAB
ACB
BAC
BCA
CBA
CAB
Please help me to find out such algorithm?
Input: arr[] = {5, 5, 10, -10, -20, 40, 50, 35, -20, -50} Output: 125 (40, 50, 35)