Program for printing permutations of specified elements

Question

I recently participated in an ACM certification contest. This is a question I could not do at the time:

"For an array of integers containing n elements, write a program to print all permutations."

Please tell me how to do this. Is there any algorithm to fulfill such questions?

Answer 1

provided that there are no repetitions: just change each element with all possible next elements and call the function recursively.

void permute(int *array,int i,int length) { if (length == i){ printArray(array,length); return; } int j = i; for (j = i; j < length; j++) { swap(array+i,array+j); permute(array,i+1,length); swap(array+i,array+j); } return; } 

You can see the code with helper functions swap() and printArray() by running the basic test case in ideone

Bonus This is similar to the idea of dragging fishermen, etc. but here - change the element to i with the next element randomly selected - you change it with all of them - each at a time.

Answer 2

A recursive approach should do well:

 If the list is empty Return the only possible permutation, an empty list. Else For each element of the list Put the element at the first place (ie swap it with the first element) (If the element is same as the first one, don't swap) Recursively find all the permutations of the rest of the list 

This algorithm will not generate repeated permutations.

The python implementation is implemented here:

 def permute(s): if len(s) == 0: return [[]] ret = [s[0:1] + x for x in permute(s[1:])] for i in range(1, len(s)): if s[i] == s[0]: continue s[0], s[i] = s[i], s[0] ret += [s[0:1] + x for x in permute(s[1:])] return ret s = [0, 1, 2, 3] for x in permute(s): print x 

A similar thing in C should be like this:

 void swap(char* str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } void permute(char *string, int start, int end) { if(start == end) { printf("%s\n", string); return; } permute(string, start + 1, end); int i; for(i = start + 1; i < end; i++) { if(string[start] == string[i]) continue; swap(string, start, i); permute(string, start + 1, end); swap(string, start, i); } } 

Answer 3

Here is an iterative solution:

Sort the array first.

• Find the maximum index i a [i + 1]. (if such an index does not exist, more permutations remain)

Find the maximum index j

Change a [i] and [j].

Return a [i + 1] .. a [n-1] and go to step *.

Answer 4

to get the permutation, you have to use reclamation and backtracking, you can also solve it with brute force, but it becomes complicated.

  void swap(int *x1,int *x2) { int x=*x1; *x1=*x2; *x2=x; } void per(int *arr,int st,int ls) { int i=0; if(st==ls) { int k; for(k=0;k<ls;k++) { printf("%d ",arr[k]); } printf("\n"); } else { for(i=st;i<ls;i++) { swap(arr+st,arr+i); per(arr,st+1,ls); swap(arr+st,arr+i); } } } int main() { int arr[4]={1,2,3,1}; int st=0; int ls=4; per(arr,st,ls); }