Backtracking with recursion

Question

i am developing high-level petri net editor / simulator. At first, here is a little of vocabulary

circle = place

rectangle = transition

integers in place = tokens

condition in transition = guard

And im stucked at passing the guard of the transition. Guard is a condition, that needs to be true if you want to execute the transition. I know that i should use backtracking somehow, but i dont know number of places entering the transition before the program start, So i cant use for loops since i dont know how many of them i will need.

Here is the picture that illustrates the problem

So, i want to take first token from first place, first token from second place, then try to pass the guard, if passed, then save tokens, and break the loop, if false, continue with second token of second place..etc... i finally pass guard with last token (4) of first place, and last token(2) of second place.

I would know how to code this, if i had constant number of places entering the transition, it would looks like this

for token in place 1
     for token in place 2
        try pass guard
        if (passed) 
            save tokens
             break;

but as i said before, i dont have constant number of places entering transition, so i cant use this approach. So, basically, i need to try combinations of tokens, and try to pass the guard - until i passed the guard, or until i tried all combinations. Do you have any ideas ? pseudocode would be enough. By the way i use these datastructure

list of places - normal java list, List places = new ArrayList();

and each place has its own list of tokens, List tokens = new ArrayList();

///EDIT: the guard has following format:

op1 rel op2, where op1 is variable, and op2 is constant or variable, rel is relation (<,>,=,...) there can be several conditions in guard connected with the logical operator AND - example: op1 rel op2 && op3 rel op4 ...

----EDIT:

So i tried to implement Rushil algorithm, but it is quite buggy, so im posting SSCCE so you can try it and maybe help a little.

First , create Place class:

public class Place {
public List<Integer> tokens ;

//constructor
public Place() {

  this.tokens = new ArrayList<Integer>();  
}

}

And then testing class:

public class TestyParmutace {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here

    List<Place> places = new ArrayList<Place>();

    Place place1 = new Place();
    place1.tokens.add(1);
    place1.tokens.add(2);
    place1.tokens.add(3);
    places.add(place1); //add place to the list

    Place place2 = new Place();
    place2.tokens.add(3);
    place2.tokens.add(4);
    place2.tokens.add(5);
    places.add(place2); //add place to the list

    Place place3 = new Place();
    place3.tokens.add(6);
    place3.tokens.add(7);
    place3.tokens.add(8);
    places.add(place3); //add place to the list


//so we have
    //P1 = {1,2,3}
    //P2 = {3,4,5}
    //P3 = {6,7,8}


    List<Integer> tokens = new ArrayList<Integer>();

    Func(places,0,tokens);

}

/**
 * 
 * @param places list of places
 * @param index index of current place
 * @param tokens list of tokens
 * @return true if we passed guard, false if we did not
 */


public static boolean Func( List<Place> places, int index, List<Integer> tokens) 

{

if (index >= places.size())
{

// if control reaches here, it means that we've recursed through a particular combination
// ( consisting of exactly 1 token from each place ), and there are no more "places" left



String outputTokens = "";
for (int i = 0; i< tokens.size(); i++) {

    outputTokens+= tokens.get(i) +",";
}
System.out.println("Tokens: "+outputTokens);

if (tokens.get(0) == 4 && tokens.get(1) == 5 && tokens.get(2) == 10) {
System.out.println("we passed the guard with 3,5,8");
return true;
}

else {
    tokens.remove(tokens.get(tokens.size()-1));
    return false;
}

}

Place p = places.get(index);

for (int i = 0; i< p.tokens.size(); i++)
{

tokens.add(p.tokens.get(i));
//System.out.println("Pridali sme token:" + p.tokens.get(i));

if ( Func( places, index+1, tokens ) ) return true;

}
if (tokens.size()>0)
tokens.remove(tokens.get(tokens.size()-1));

return false;

}
}

and here is the output of this code:

Tokens: 1,3,6,
Tokens: 1,3,7,
Tokens: 1,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 2,3,6,
Tokens: 2,3,7,
Tokens: 2,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 3,3,6,
Tokens: 3,3,7,
Tokens: 3,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,

So, you see, some combinations are correct, like 1,3,6, and 1,3,7... but 4,5,8 is absolute nonsense, since 4 is not even in the first place... and there are also combinations that are missing ompletely..like 2,4,6 etc... anybody see why is it like this ?

EDIT: Now it's working fine.

Answer 1

A recursive approach would make it easy:

boolean Func( ListOfPlaces places, int index ) // index points to the current "place"
{

 If index >= NumberOfTokens (if index points to a place, which doesn't exist)
   {
   // if control reaches here, it means that we've recursed through a particular combination ( consisting of exactly 1 token from each place ), and there are no more "places" left. You have all the tokens you need, in your stack.

   try pass guard; if passed, save tokens and return true

   else, remove token last added to the stack & and return false
   }

 place p = places[index] 

 foreach token in p
 {
   add token to your stack
   if ( Func( places, index+1 ) ) return true
 }

 remove last token added to the stack
 return false
}

Call the function initially with index = 0.

Hope this helps. :-)

Answer 2

Assume Transition has an isEnabled() method as well as input/outputArcs:

public boolean isEnabled() {
    // check for some special input/output conditions (no arcs, etc.)
    // return false if invalid

    // check to see if all input arcs are enabled
    for (Arc inputArc : inputArcs)
        if (!inputArc.isEnabled())
            return false;
    // should check if there's a guard first...
    return guard.evaluate();  // do the selection of tokens from inputs here and evaluate
}

Answer 3

What about something like this:

method getPassed(places, tokens):
    if places are empty:
        try pass guard
            if (passed) 
                save tokens
                return true
            else return false
    else:
        for token in places[0]:
            if getPassed(places[1:].clone(), tokens.clone().append(token)):
                break

Start it with call getPassed(places, []), where places is a list of places and [] is empty list. Note that you need to copy the lists always, so that you don't end up messing them up.

In the end, no need for pairs. If you keep the original places list you pass into the algorithm at the beginning, you know that token[i] was selected for originalPlaces[i].

But if you want to, you can keep tokenPlaces pairs instead of tokens, so something like this:

method getPassed(places, tokenPlacePairs):
    if places are empty:
        try pass guard
            if (passed) 
                save tokens
                return true
            else return false
    else:
        for token in places[0]:
            if getPassed(places[1:].clone(), tokens.clone().append((token, places[0]))):
                break

EDIT: Still some confusion, hopefully this will make it clear. I am trying to generate the for loops recursively. So if places has only 2 elements, you get as you suggested:

for token in place 1
     for token in place 2
        try pass guard
        if (passed) 
            save tokens
             break;

So what it does is that it takes the first place from the list and creates the "for token in place 1" loop. Then it cuts of that place from the places list and adds the current token to the tokens list. This recursive call now does the "for token in place 2" loop. And so on. Every recursive call we decrease the number of places by 1 and create 1 for loop. Hence, after the places list is empty we have n nested loops, where n is the number of places and as far as I understand, this is what you were looking for.

You can initiate the method in the following way:

originalPlaces = places.clone()
getPassed(places, [])

This way you can keep the originalPlaces unchanged and you can assign tokens[i] to originalPlaces[i] when you get to the base case in the recursion, i.e. when you try to determine the passing the guard. Hence you do not really need the pairs.

Answer 4

You could do the loop administration yourself. What I mean is: you would need a class to depict the iteration status for each place. Lets call it state_of_place. It would consist of two values: a current_index and a max_index.

Next you would have a class I would name iteration_admin, which consists of an array of state_of_place and a boolean called something like iteration_in_progress. Upon creation, the boolean is set to TRUE. You would create as many state_of_place objects as there are places. Current_index would be 0, max_index would be the number of tokens on that place.

The iteration_admin class needs a method to represent the increment of loop variables. Lets call it increment(). This method would increment the current_index of the state_of_place element with the highest index, if the current_index is still below the max_index. If the current_index is equal to the max_index, the current index is set to 0 and the current index of the state_of_place with the next lower index needs to be incremented. If that one has reached its max_index, it will be set to 0 and the next lower one will be incremented, and so on. Only exception, of course, is state_of_place[0]. If that elements current_index would exceed its max_index, the boolean iteration_in_progress will be set to FALSE. This would mean, that all combinations of tokens have been used.

Now, your code for trying out the guard would

• initialize an object of type iteration_admin
• while iteration_admin.iteration_in_progress is TRUE
• build the argument list for the pass() method by using the current_index values in the state_of_place elements
• call pass()
• if not passed, call the iteration_admin.increment() method
• end while

EDIT: Trying to express the idea in pseudo code. I fear it looks more like a mix of Java and PL/SQL than abstract pseudo code. Still, it should be somewhat clearer than my text description.

   // iteration state for one place
class state_of_a_place 
{
   integer current_index;
   integer max_index;
}

   // iteration administration for one transition
class iteration_admin
{
   boolean iteration_in_progress
   state_of_a_place[] state_of_places

   procedure increment
   {
         // move index through tokens
      FOR i IN state_of_places.count-1 .. 0 LOOP     
         IF state_of_places[i].current_index < state_of_places[i].max_index THEN
            state_of_places[i].current_index += 1
            return
         ELSE
            state_of_places[i].current_index = 0
            IF i = 0 THEN
               iteration_in_progress = FALSE
            END IF
         END IF
      END FOR         
   }
}

handle_transition (list_of_places)
{
      // initialize an object of type iteration_admin
   iteration_admin ia
   ia.iteration_in_progress = TRUE
   FOR i IN 0..list_of_places.count LOOP
      ia.state_of_places[i].current_index = 0
      ia.state_of_places[i].max_index = list_of_places[i].number_of_tokens
   END FOR

   WHILE ia.iteration_in_progress LOOP
         // build the argument list for the pass() method 
      token[] arguments
      FOR i IN 0..list_of_places.count LOOP
         arguments[i] = list_of_places[i].token[ia.state_of_places[i].current_index]
      END FOR

         // try to pass the guard
      call pass(arguments)
      IF (passed)
         // do whatever you need to do here
      ELSE
         ia.increment()
      END IF         
   END WHILE
}