Write a program that takes as input an array of integers and generates a permuta

Question

Write a program that takes as input an array of integers and generates a permutation that rearranges the input to satisfy the following condition: * Let x be the value of the last element of an array A * In a new array B, x will be in a position B[i] such that B[j] <= x for all j < i and B[j] >= x for j > i. * For example, suppose A has the following sequence of integers: 5,2,3,7,6,8,1,4. One among several possible partitions that satisfy the above condition is the following one: 3,1,2,4,8,6,7,5. The rightmost element of A, 4, is positioned in the resulting array B so that all elements less than 4 (that is, 1, 2, 3) are to its left (in no particular order), and all elements larger than 4 are to its right (again, in no particular order). * Your program should be able to open and read a file named InputArray that contains a single line of less than 100 inte- gers. Your program will output its permutation on the standard output, i.e. on the computer screen.

Explanation / Answer

A recursive approach should do fine: 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 (i.e. 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 won't generate repeated permutations. Here's a python implementation: 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 The 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 ", string); return; } permute(string, start + 1, end); int i; for(i = start + 1; i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.