5
\$\begingroup\$

Given a table, I want to explore all possible transition between the elements in the table. ex: for a table with size 3 [0,1,2], the output of the algorithm should be 0->1, 1->0, 0->2, 2->1, 1->2, 2->0. I guess this can be regarded as traversing a complete graph.

I have an implementation of an algorithm doing this in Python:

def test1(n):
   theList=[]
   theList.append(0)

   for x in range(0,n+1):
      for y in range(n,x+1,-1):
         theList.append(y)
         theList.append(x)

      if x!=n:
         theList.append(x+1)

   for x in range(n,0,-1):
      theList.append(x-1)
   return theList

This code always start at element 0, and return a list of all the transitions.

But I need my algorithm i Prolog. So I have done an attempt to port the Python-code to Prolog. My main focus has been on writing readable and maintainable code. But I guess there is great room for improvement wrt. performance of the Prolog code:

:- use_module(library(clpfd)).
:- use_module(library(between)).
:- use_module(library(lists)).

dynappend( List, X ) :-
   (
   foreach( Item, List ),
   param(X,T)
   do
      var( Item ), var(T) ->
      Item = X ,
      T = 1
      ;
      true
   ).   

s3(List,N):-
   LSize is N*(N+1)+1,
   length(List,LSize),

   dynappend( List, 0 ),
   (
      for(X1, 0, N ),
      param( N, List )
      do
         X1T is X1+2,
         ( between:numlist( X1T, N, YList ) -> true ; YList=[] ) , 
         lists:reverse(YList,RYList),

         (
            foreach(Y, RYList ),
            param( X1, List )
            do
               dynappend( List, Y ),
               dynappend( List, X1 )
         ),

         (   X1 #\= N -> X1T2 is X1+1, dynappend( List, X1T2 ) ;  true )
   ),
   N1 is N-1,
   numlist( 0, N1, XList ), 
   lists:reverse(XList,RXList),
   (
   foreach(X2, RXList ),
   param(List)
   do
      dynappend( List, X2 )
   ).

Running the code:

| ?- s3(L, 2).
L = [0,2,0,1,2,1,0] ? 
yes

Any suggestions for improvements of the Prolog code?

\$\endgroup\$
  • \$\begingroup\$ if you get the habit to use 'yield' in Python, you will end with much more Prolog like code, very similar to what @Mat shows \$\endgroup\$ – CapelliC Jul 25 '13 at 9:30
  • \$\begingroup\$ If someone suggests that a question belongs to codereview.SE please flag/ask a moderator to move it next time. Make a comment to move the question if you can't see the flag button and someone else will flag it. Posting the same question on both sites isn't considered good. Just wait a bit. \$\endgroup\$ – Aseem Bansal Jul 31 '13 at 14:31
5
\$\begingroup\$

Consider describing what a transition is:

list_transition(List, (E1->E2)) :-
        select(E1, List, Rest),
        member(E2, Rest).

Example query:

?- list_transition([0,1,2], T).
T = (0->1) ;
T = (0->2) ;
T = (1->0) ;
T = (1->2) ;
T = (2->0) ;
T = (2->1) ;
false.

And to get all transitions:

?- findall(T, list_transition([0,1,2], T), Transitions).
Transitions = [ (0->1), (0->2), (1->0), (1->2), (2->0), (2->1)].
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.