
Permutation recursive help
Producing consecutive permutations.Need to develop a method that lists one by one all permutations of the numbers 1, 2, …, n (n is a positive integer).
(a) Recursive method . Given a verbal description of the algorithm listing all permutations one by one, you are supposed to develop a recursive method with the following header:
public static boolean nextPermutation(int[] array)
The method receives an integer array parameter which is a permutation of integers 1, 2, …, n. If there is “next” permutation to the permutation represented by the array, then the method returns true and the array is changed so that it represents the “next” permutation. If there is no “next” permutation, the method returns false and does not change the array.
Here is a verbal description of the recursive algorithm you need to implement:
1. The first permutation is the permutation represented by the sequence (1, 2, …, n).
2. The last permutation is the permutation represented by the sequence (n, …, 2, 1).
3. If n a ,...,a 1 is an arbitrary permutation, then the “next” permutation is produced by
the following procedure:
(i) If the maximal element of the array (which is n) is not in the first position of the array, say i n = a , where i > 1, then just swap i a and i1 a . This will give you the “next” permutation in this case.
(ii) If the maximal element of the array is in the first position, so 1 n = a , then to find
the “next” permutation to the permutation ( ,..., ) 1 n a a , first find the “next”
permutation to ( ,..., ) 2 n a a , and then add 1 a to the end of thus obtained array of (n1) elements.
(iii) Consecutively applying this algorithm to permutations starting from (1, 2, …, n),you will eventually list all n! possible permutations. The last one will be (n, …, 2, 1).For example, below is the sequence of permutations for n = 3 , listed by the described algorithm:
(0 1 2) ; (0 2 1) ; (2 0 1) ; (1 0 2) ; (1 2 0) ; (2 1 0)
Please help...i have done the iterative one..but unable to figure out the recursive..
Thank you in advance..
Similar Threads

Replies: 2
Last Post: 04242006, 01:54 PM

By Sparky in forum Database
Replies: 0
Last Post: 10152002, 01:13 AM

By Andrew Merisanu in forum Database
Replies: 1
Last Post: 08082002, 03:53 PM

By Rodrigo in forum Database
Replies: 1
Last Post: 12162000, 12:25 AM

By Chris McCann in forum VB Classic
Replies: 0
Last Post: 10202000, 01:02 PM
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
