Permutation recursive help


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Permutation recursive help

Hybrid View

  1. #1
    Join Date
    Apr 2006
    Posts
    3

    Question 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 i-1 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 (n-1) 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..

  2. #2
    Join Date
    Aug 2008
    Posts
    1
    Hi,

    I have the same scenario for Producing consecutive permutations, Do you have the answer??
    plz help...

  3. #3
    Join Date
    Apr 2007
    Location
    Sterling Heights, Michigan
    Posts
    8,666
    Welcome to DevX

    What have you got so far that isn't working for you?
    I don't answer coding questions via PM or Email. Please post a thread in the appropriate forum section.
    Please use [Code]your code goes in here[/Code] tags when posting code.
    Before posting your question, did you look here?
    Got a question on Linux? Visit our Linux sister site.
    Modifications Required For VB6 Apps To Work On Vista

Similar Threads

  1. Permutation recursive
    By i.mogal in forum Java
    Replies: 2
    Last Post: 04-24-2006, 01:54 PM
  2. Re: Recursive sql query - Lot's of tips
    By Sparky in forum Database
    Replies: 0
    Last Post: 10-15-2002, 01:13 AM
  3. Recursive SQL Query
    By Andrew Merisanu in forum Database
    Replies: 1
    Last Post: 08-08-2002, 03:53 PM
  4. How to stop a recursive trigger in db2!!
    By Rodrigo in forum Database
    Replies: 1
    Last Post: 12-16-2000, 12:25 AM
  5. Hierarchial recordsets, recursive relationships in Access
    By Chris McCann in forum VB Classic
    Replies: 0
    Last Post: 10-20-2000, 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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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