Prolog - combinatorics

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Jul 04, 2006 at 07:11

I have tried various prolog forums to get help but i don’t seem to be getting any. :wallbash: Maybe people think i’m trying to get someone else to do my homework but that’s not the case. I’ve completed an introductory course in prolog which was an AI course which merely introduced us to prolog and lisp programming. Now i’m on holidays due to recommence study next week and won’t be doing prolog again. Since I enjoy prolog and am trying to keep from forgetting it altogether i’m trying to build my own small project but find i’ve still so much more to learn. :unsure:

varia(0,_,[]).
varia(N,L,[H|Varia]):-N>0,N1 is N-1,delete(H,L,Rest),varia(N1,Rest,Varia).

delete(X,[X T],T).  
delete(X,[H T],[H NT]):-delete(X,T,NT).

Using the above predicates and the ‘query’ below:

varia(3, [a, b, c],L3); varia(2, [a, b, c],L2); varia(1, [a, b, c],L1).

gives the following result:

L3 = [a, b, c]
L2 = _G632
L1 = _G645 ;

L3 = [a, c, b]
L2 = _G632
L1 = _G645 ;

L3 = [b, a, c]
L2 = _G632
L1 = _G645 ;

L3 = [b, c, a]
L2 = _G632
L1 = _G645 ;

L3 = [c, a, b]
L2 = _G632
L1 = _G645 ;

L3 = [c, b, a]
L2 = _G632
L1 = _G645 ;

L3 = _G619
L2 = [a, b]
L1 = _G645 ;

L3 = _G619
L2 = [a, c]
L1 = _G645 ;

L3 = _G619
L2 = [b, a]
L1 = _G645 ;

L3 = _G619
L2 = [b, c]
L1 = _G645 ;

L3 = _G619
L2 = [c, a]
L1 = _G645 ;

L3 = _G619
L2 = [c, b]
L1 = _G645 ;

L3 = _G619
L2 = _G632
L1 = [a] ;

L3 = _G619
L2 = _G632
L1 = ;

L3 = _G619
L2 = _G632
L1 = [c] ;

However, i wish to simply call with one predicate, such as:

modified_varia(3, [a, b, c],L):

(note I’ve ommitted unbound variables in the following output for clarity only)

i.e. Output similar to:

L = [a, b, c];

L = [a, c, b];

L = [b, a, c];

L = [b, c, a];

L = [c, a, b];

L = [c, b, a];

L = [a, b];

L = [a, c];

L = [b, a];

L = [b, c];

L = [c, a];

L = [c, b];

L = [a];

L = ;

L = [c];

My attempt at implementing the predicate “varia” recursively to achieve the above output is flawed: :blink:

modified_varia(0,_,_).
modified_varia(N,X,Y):- Z is N-1, varia(Z,X,Y), modified_varia(Z,X,Y).

If anyone out there can help me to code this i would most appreciate it. :worthy:

Thanks,
Brian :mellow:

9 Replies

Please log in or register to post a reply.

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Jul 18, 2006 at 05:57

The predicates i’m atempting to modify can be seen at http://ktiml.mff.cuni.cz/\~bartak/prolog.old/learning/LearningProlog4.html

…still waiting, atempting and hoping for a solution!

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Aug 29, 2006 at 22:44

Is that what you were hoping ?

modified_varia(0,_).
modified_varia(N,X):- 
    Z is N-1, 
    bagof(L, varia(N,X,L), LL), write(LL), nl, modified_varia(Z,X).

I get :

5 ?- modified_varia(3, [a, b, c]).
[[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]]
[[a, b], [a, c], [b, a], [b, c], [c, a], [c, b]]
[[a], [b], [c]] Yes

Perhaps it’s not exactly what you want :sad:

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Sep 06, 2006 at 04:41

oops! (can’t delete the duplicate i made by mistake)

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Sep 06, 2006 at 04:44

:yes: That’s exactly what I need! I’m really really happy! i never thought anyone would do it. I realize that mine included 3 input parameters instead of 2, but that was only because I assumed it would need 3. I was actually starting to wonder whether programming was for me; that if I couldn’t solve one problem how would I solve another? This was a big hurdle, it got me down that I couldn’t figure it out but more that I couldn’t get help, that is, until now.

I really appreciate your help. Thanks heaps :worthy: :yes:

PS: I’ve had no replies in other forums but now I aught to post a link ‘solved’ pointing to this page.
PPS: I’ll have to study the code it’s neat.

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Sep 06, 2006 at 20:51

If you want to learn Prolog, (and it is an excellent idea) I think you should buy the excellent book “The Art of Prolog: Advanced Programming Techniques”. Leon Sterling and Ehud Shapiro. MIT Press, 1994 (2nd ed).
Easyer are
“Programming In Prolog”. William F. Clocksin and Christopher S. Mellish. Springer-Verlag, 2003 (5th ed).
“Prolog Programming for Artificial Intelligence”. Ivan Bratko. Addison-Wesley, 2001 (3rd ed).

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Sep 07, 2006 at 03:05

Those books look like excellent books particularly the first one, though it would be nice to have them all! I’ve put them on my list.

:happy:

2f9f82c36ec6a28702dc365e43753d79
0
Ooka 101 Sep 08, 2006 at 05:53

This is out of curiousity, as I know very little about prolog or it’s history…
Why prolog, despite the fact that it’s been used for some high profile AI projects?

What makes it better than c++ or another standard language?

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Sep 08, 2006 at 12:42

I don’t know if it is better than C++ (I don’t really know C++, just C), but for me it’s another way of thinking the programmation, like Lisp/Scheme and that’s important. A good programmer MUST knows different ways of thinking, when you program always the same way, your mind becomes sclerosed, and it’s not good !

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Sep 11, 2006 at 06:18

I’ve only done a hello world in c++ but it’s a language i will learn.

Prolog is a declarative (non-procedural) language, C++ is procedural.
Using prolog means the programmer can concentrate more on expressing the problem itself; in a logical form rather than the procedure (algorithm) of getting to the solution.

A free prolog book to download :

Prolog Programming A First Course by Paul Brna

http://www.scre.ac.uk/personal/pb/prologbook/index.html

Why Prolog?

http://www.j-paine.org/why_prolog.html