Recursive and exhaustive

[kanskje]

Hello,

I'm having difficulties returning the right values from a recursive call.

The problem is to check a list of items. Each item can be visited only once, and I want to find every possible path between the items, quite similiar to a TSP.

I've generated a list that includes all the previously visited items. However, when the recursive call returns, this list is remembered. Let me try to illustrate:

List of legal items: a, b, c
First path: a - b - c
Then I want it to go back to b, check the list of visited items, it discovers a and c, and goes to a.
a sees only b, not c, thus goes to c.
c sees that a has been visited, and goes to b.
thus the next path becomes
a - c - b

It would then check b, then c, and a. Since all legal items at a is visited, it turns to b and continues the process from start: b - c - a, b - a - c and soforth.

Unfortunately, the list that included visited items of each recursive layer is returned with all three items.

Please let me know if you understand the problem

I have the (not working) code ready to be pasted in, but i guess it would be quite a long and messy post

Thanks for any suggestions on how to return the right argument

kanskje

 

[xwb]

I think this is what you're saying

recursive subroutine fred
logical,dimension(10)::used
...
used(x) = .true.
call fred
end subroutine

Your list needs to be global. You can do this either by putting the list at module level or by putting it in a common block. eg

module FredMod
   integer::umax
   parameter (umax=10)
   logical,dimension(umax)::used
contains
   subroutine Init
      do i = 1, umax, 1
         used(i) = .false.
      enddo
   end subroutine

   subroutine Fred
      ...
      used(x) = .true.
      call Fred
      ...
   end subroutine Fred

Having said that, I'm not sure whether common blocks exist in F90/F95 but they're the same as global variables anyway.

 

[xwb]

Just tried it out - it works with common blocks too

subroutine Init
   integer usedmax
   parameter (usedmax = 10)
   logical used(usedmax)
   common /share/used
   integer i
   do i = 1, usedmax, 1
      used(i) = .false.
   enddo
   return
end subroutine init

recursive subroutine Useit()
   integer usedmax
   parameter (usedmax = 10)
   logical used(usedmax)
   common /share/used
   integer i
   
   do i = 1, usedmax, 1
      if (.not. used(i)) then
         write (*,*) 'Using ', i
         used(i) = .true.
         call UseIt
         return
      endif
   enddo
   return
end subroutine UseIt

program main
   call Init
   call UseIt
   stop
end program main

 

[kanskje]

First of all, thanks a lot for your help!
The program now outputs '1-2-3'
When Useit returns, all values of used = .true.

How can it be written such that it continues through all different cominations?

1-2-3
1-3-2
2-1-3
2-3-2 etc.

Any suggestions?

MODULE div

INTEGER, PARAMETER :: usedmax = 3
LOGICAL, DIMENSION(usedmax) :: used
INTEGER, DIMENSION(usedmax) :: choice

CONTAINS

RECURSIVE SUBROUTINE Useit()
INTEGER :: i, j

   DO i = 1, usedmax, 1
      IF (.NOT. used(i)) then
         used(i) = .TRUE.
         WRITE (*,*) 'made choice', choice(i)
         CALL UseIt()
         RETURN
      ENDIF
   ENDDO
RETURN
   
END SUBROUTINE UseIt

SUBROUTINE Init

   INTEGER :: i
   DO i = 1, usedmax, 1
      used(i) = .false.
      choice(i) = i
   ENDDO
   RETURN
   
END SUBROUTINE init
END MODULE

PROGRAM main
USE div
   CALL Init
   CALL UseIt()
   STOP
END PROGRAM main

 

[xwb]

You need to know how much you've done. And then undo it when you've finished with it

RECURSIVE SUBROUTINE Useit(done) !! new
INTEGER, INTENT(IN)::done !! The number of choices made
INTEGER :: i, j

   DO i = 1, usedmax, 1
      IF (.NOT. used(i)) then
         used(i) = .TRUE.
         choice(done) = i  !! note the new one
         if (done .eq. usedmax) then !! any more
            write (*,*) (choice(j), j = 1, usedmax)
         else
            CALL UseIt(done + 1) !! get the next one
         endif
         used(i) = .FALSE. !! undo
         !! RETURN - do not return here otherwise
         !!          we will not get the next sequence
      ENDIF
   ENDDO
RETURN
   
END SUBROUTINE UseIt

To start it off, in main

   CALL UseIt(1)

 

[kanskje]

I've spent many hours trying to understand how this recursion algorithm works!

And now, thanks to you, I finally think I do!
Thanks for your help, I appreciate it.

Keep up the good work!

Kanskje

 

[xwb]

Recursion is just one of those things. You need a few dry runs before you realize what is happening. Once you understand it, you don't know what you didn't understand because it is just so obvious.

The other problem is coding it. You basically start off writing the code and then find that you are repeating yourself with a different set of parameters. Parameterize the repeats and the algorithm will soon become obvious.

A note of warning: recursion isn't always necessary. In fact, sometimes using a loop is more efficient.