MCN Professionals | Interview Question of the day
To receive one interview question in your mailbox daily, please subscribe to "A Question A Day" at MCN Professionals home page.-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
This question is a variation of a question which I posted earlier "Print Permutations of an Array or String". The code which I had written there will not work if we have repetitions in the array. Today's post is to write the code to print all permutations and takes care of the case if there is any duplication in the array.
For example: If the array is {1, 2, 3} then the result should be
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
But if the array is {1, 2, 2} then the output s
(rest all are just the repetitions)
Solution:
We will take forward from this
post only. When there is no duplicates, The code to compute permutations is as below:
/** Recursive function to print all permutations of an Integer array.
* arr: Array of integers.
* n: Number of elements in the array.
* x: at any given point where we are.
**/
Void permutation (int * arr, int n, int x)
{
if(x == n-1){
prinArray(arr, n);
}
for (int i=x; i<n; i++){
swap( &arr[i], &arr[x] );
permutation ( arr, n , x+1);
swap( &arr[i], &arr[x] );
}
}
If we have duplicates, then we just need to keep a check of not to swap two elements if they are same. so just one extra check in the for loop:
/** Recursive function to print all permutations of an Integer array.
* arr: Array of integers.
* n: Number of elements in the array.
* x: at any given point where we are.
**/
Void permutation (int * arr, int n, int x)
{
if(x == n-1){
prinArray(arr, n);
}
for (int i=x; i<n; i++){
swap( &arr[i], &arr[x] );
permutation ( arr, n , x+1);
swap( &arr[i], &arr[x] );
}
}
-----------------------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...