1

I am new to Prolog and I'm trying out list permutation predicates.

Most of them take two arguments (e.g., permutation/2).

I'm looking to create one which only takes one argument (list) and also finds out if the list has exactly 10 elements.

So for example:

| ?- permutation([7, 1, 2, 3, 4, 5, 6, 0, 8, 9]).
yes

| ?- permutation(X).
X = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
...      

| ?- permutation([A,B,C,D,E,F,G,H,I,J]).
A = 0
B = 1
C = 2 
...
J = 9 ;

Appreciate any tips!

repeat
  • 18,496
  • 4
  • 54
  • 166
Layos
  • 7
  • 3
  • 1
    Possible duplicate of [Permutation Prolog](http://stackoverflow.com/questions/27350677/permutation-prolog) –  Oct 24 '15 at 11:23
  • Hmm i dont think so, since im asking about permutation/1 and not permutation/2 – Layos Oct 24 '15 at 11:25
  • 1
    just define permutation10(X) :- permutation(10, X) . Then you can call permutation10([7, 1, 2, 3, 4, 5, 6, 0, 8, 9]), permutation10(X), or permutation10([A,B,C,D,E,F,G,H,I,J]), etc.. –  Oct 24 '15 at 11:26
  • oh god, thats so obvious, thanks! – Layos Oct 24 '15 at 11:29
  • But you have to check whether it really works. It might still not work, depends on how exactly permutation/2 is implemented and what input/output modes it supports. –  Oct 24 '15 at 11:30
  • 2
    To determine if a list has 10 elements, you would just say, `length(List, 10).` which will be true if `List` has 10 elements. But if you want a predicate to determine if a list is a permutation of the values `0` through `9`, just define it using `permutation/2`: `permutation10(List) :- permutation([0,1,2,3,4,5,6,7,8,9], List).` – lurker Oct 24 '15 at 11:35
  • takeout(X,[X|R],R). takeout(X,[F |R],[F|S]) :- takeout(X,R,S). perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W). perm([],[]). gen_perm(X) :- perm(X, Q), length(X, 10). – Layos Oct 24 '15 at 11:52
  • this is what i have right now. something is missing i guess – Layos Oct 24 '15 at 11:53
  • Don't put code in comments. If you have code, edit your question and put it there, properly formatted. – lurker Oct 24 '15 at 12:34

2 Answers2

2

Work smarter, not harder: Use !

:- use_module(library(clpfd)).

Using length/2, domain/2, all_different/1, and labeling/2 we define:

perm10(Zs) :-
   length(Zs,10),
   domain(Zs,0,9),
   all_different(Zs),
   labeling([],Zs).

Consider the goal gen_perm([8,0,1,2,3,4,5,6,7,8]). We expect1 it to fail, and, in fact, it does...
... but how much work is being performed executing above goal?

Let's measure runtimes2 using call_time/2!

?- use_module(library(between),[repeat/1]).
true.

?- _Zs = [8,0,1,2,3,4,5,6,7,8], call_time((repeat(1000),gen_perm(_Zs);true),T_us).
T_us = 21940.

?- _Zs = [8,0,1,2,3,4,5,6,7,8], call_time((repeat(1000),perm10(_Zs)  ;true),T_us).
T_us = 10.

Footnote 1: There are only 8 different integers in the list, so it cannot be a permutation of all integers between 0 and 9.
Footnote 2: Using SICStus Prolog version 4.3.2, x86_64-linux-glibc2.12.

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
0

Ok, thanks for the replies! This works:

takeout(X,[X|R],R).  
takeout(X,[F|R],[F|S]) :-
   takeout(X,R,S).

perm([X|Y],Z) :-
   perm(Y,W),
   takeout(X,Z,W).
perm([],[]).

gen_perm(List) :-
   perm([0,1,2,3,4,5,6,7,8,9],List),
   length(List,10).
repeat
  • 18,496
  • 4
  • 54
  • 166
Layos
  • 7
  • 3
  • If `perm` works properly, then you shouldn't need `length(List, 10)` since `perm` shouldn't be generating a list `List` which only consists of elements from `[0,1,2,3,4,5,6,7,8,9]`. – lurker Oct 24 '15 at 12:35