current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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?

share|improve this question

migrated from stackoverflow.com Jul 31 '13 at 14:23

This question came from our site for professional and enthusiast programmers.
    
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 –  CapelliC Jul 25 '13 at 9:30
    
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. –  Aseem Bansal Jul 31 '13 at 14:31

1 Answer 1

up vote 5 down vote accepted

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)].
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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