Databases
StackOverflow2013
Postsdbo
POBacktracking with recursion
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBacktracking with recursion
    primarykey
    data
    text
    <p>i am developing high-level petri net editor / simulator. At first, here is a little of vocabulary</p> <p>circle = <strong>place</strong></p> <p>rectangle = <strong>transition</strong></p> <p>integers in place = <strong>tokens</strong></p> <p>condition in transition = <strong>guard</strong></p> <p>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.</p> <p>Here is the picture that illustrates the problem <img src="https://i.stack.imgur.com/DlSQj.png" alt="enter image description here"></p> <p>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.</p> <p>I would know how to code this, if i had constant number of places entering the transition, it would looks like this</p> <pre><code>for token in place 1 for token in place 2 try pass guard if (passed) save tokens break; </code></pre> <p>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</p> <p>list of places - normal java list, List places = new ArrayList();</p> <p>and each place has its own list of tokens, List tokens = new ArrayList();</p> <p>///EDIT: the guard has following format:</p> <p>op1 rel op2, where op1 is variable, and op2 is constant or variable, rel is relation (&lt;,>,=,...) there can be several conditions in guard connected with the logical operator AND - example: op1 rel op2 <strong>&amp;&amp;</strong> op3 rel op4 ...</p> <p>----EDIT:</p> <p>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.</p> <p>First , create Place class:</p> <pre><code>public class Place { public List&lt;Integer&gt; tokens ; //constructor public Place() { this.tokens = new ArrayList&lt;Integer&gt;(); } } </code></pre> <p>And then testing class:</p> <pre><code>public class TestyParmutace { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here List&lt;Place&gt; places = new ArrayList&lt;Place&gt;(); 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&lt;Integer&gt; tokens = new ArrayList&lt;Integer&gt;(); 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&lt;Place&gt; places, int index, List&lt;Integer&gt; tokens) { if (index &gt;= 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&lt; tokens.size(); i++) { outputTokens+= tokens.get(i) +","; } System.out.println("Tokens: "+outputTokens); if (tokens.get(0) == 4 &amp;&amp; tokens.get(1) == 5 &amp;&amp; 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&lt; 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()&gt;0) tokens.remove(tokens.get(tokens.size()-1)); return false; } } </code></pre> <p>and here is the output of this code:</p> <pre><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, </code></pre> <p>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 ?</p> <p>EDIT: Now it's working fine.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USRushil
    1. USAnton Giertli
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBacktracking with recursion
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POBacktracking with recursion
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POBacktracking with recursion
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload