2

I'm trying to write a prolog program that determines whether one list is a permutation of another. Input is of the form perm(L,M), which will be true if and only if list L is a permutation of list M.

This is for my AI class, so I cannot just use the nifty little permutation predicate that gprolog already provides. Our professor noted that the member predicate might be useful, but any ideas I have that involve it seem to require very tricky and not-so-declarative things (and I'm assuming there is a way to solve this without getting too advanced, since the class is new to prolog.)

Anyway, one way to check would supposedly be to see that L and M are the same size, each L element is in M, and each M element is in L (there's a use of member!). However, this wouldn't be enough for cases like [2,2,4] and [4,4,2], among others.

Another way could be to ensure that the same counts of each element are in the opposite list, but my impression of prolog is that any kind of variable 'memory' is rather difficult business (in fact, it seems that the example programs I see that perform sorts, etc., aren't really manipulating data at all; they're just 'hypothetically' rearranging things and then telling you yes or no...?)

Mentally, one could just sort both lists and check elements side-by-side, but that, among tons of other ways to think of it, seems a little too object-oriented...

Any hints? My biggest trouble seems to be (as mentioned) the fact that doing "operations" seems to be more like asking about them and hoping that things stay true long enough to get where you want.

**UPDATE: gprolog does offer a delete functionality, but it comes with the declarative-related trouble I was expecting, given an attempt like this:

perm([LH|LT], R) :- member(LH,R), delete([LH|LT],LH,R), perm(LT,R).

In the manual, delete is defined like this: "delete(List1, Element, List2) removes all occurrences of Element in List1 to provide List2. A strict term equality is required, cf. (==)/2"

Execution:

{trace}
| ?- perm([1,2,3],[3,1,2]).
      1    1  Call: perm([1,2,3],[3,1,2]) ? 
      2    2  Call: member(1,[3,1,2]) ? 
      2    2  Exit: member(1,[3,1,2]) ? 
      3    2  Call: delete([1,2,3],1,[3,1,2]) ? 
      3    2  Fail: delete([1,2,3],1,[3,1,2]) ? 
      2    2  Redo: member(1,[3,1,2]) ? 
      2    2  Fail: member(1,[3,1,2]) ? 
      1    1  Fail: perm([1,2,3],[3,1,2]) ? 

(1 ms) no

**UPDATE 2: I think I might have figured it out! It's kind of verbose, but I have tested it for quite a few cases and haven't found a bad one yet. If someone sees a major issue, please point it out:

perm([],[]). 
perm([LH|LT],R) :- length([LH|LT],A), length(R,B), A == B, member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.
perm_recurse([],X).  %If we get here, all elements successfully matched
perm_recurse([LH|LT],R) :- member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.

I do like the cut operator..

false
  • 10,264
  • 13
  • 101
  • 209
norman
  • 5,128
  • 13
  • 44
  • 75
  • What if you match the first element in L to an element in M and, if present, remove the matched element from both L and M? You would then have smaller lists to check... – beaker Jul 04 '13 at 16:19
  • How? See update...unfortunately, `delete` doesn't seem to actually do it as much as check whether your arguments constitute a proper delete. For example, `| ?- delete([1,2,3],1,[2,3]).` gives a yes, since removing 1 from [1,2,3] produces [2,3]. – norman Jul 04 '13 at 16:55
  • do you consider [2,2,4] and [4,4,2] permutations of each other or do you want it to fail? I think it should fail. – Will Ness Jul 04 '13 at 19:14
  • (do note that `delete([1,1,2,3],1,X)` succeeds with `X=[2,3]`. Probably not what you need). – Will Ness Jul 04 '13 at 19:15

4 Answers4

2
perm(L, M) :- sort(L, X), sort(M, X).

This gets you pretty close and is fully declarative ("two lists are permutations of each other if they have the same sorted representation", but sorting in Prolog removes duplicates). However, it will succeed for cases like perm([1,2], [2,2,2,1]) which I'm not sure if you want. It will handle [2,2,4] and [4,4,2] though, since they both sort to [2,4]. Another solution would be something like this:

perm([], []).
perm([L|Ls], M) :- select(L, M, Ms), !, perm(Ls, Ms).

This version won't succeed for [2,2,4] and [4,4,2], but it will properly fail for [1,2] and [2,2,2,1]. I'm not sure which one you want, but I think one or the other of these is probably correct.

Daniel Lyons
  • 22,421
  • 2
  • 50
  • 77
  • Well, at least partially correct. :-) I probably need to stay in the vicinity of the second one, since the next problem requires me to actually write a `sort` that uses this `perm`. – norman Jul 04 '13 at 17:01
  • 1
    msort does not eliminate duplicates and therefore msort(L, X), msort(M, X) is true if L is a permutation of M – Manolo Jul 05 '13 at 16:24
  • `sort/2` as such is not declarative, thus your `perm/2` cannot be declarative either... – false Jul 06 '13 at 20:58
  • @false What makes you say `sort/2` is not declarative? – Daniel Lyons Jul 08 '13 at 05:11
  • 1
    `sort([X,1],[2,1]), X = 2.` succeeds, but `X = 2, sort([X,1],[2,1]).` fails. The meaning depends on the precise instantiation at the point in time of calling `sort/2`. – false Jul 08 '13 at 13:34
2

Always good to define more general predicate and use it in a narrowed fashion:

perm(X,L):- mselect(X,L,[]).

mselect([A|B],L,R):- select(A,L,M), mselect(B,M,R).
mselect([],L,L).

member is no good as it leaves the second list unchanged. delete is no good either as it deletes the multiplicities.

You could use append though. :) It too combines picking and removing:

perm([A|B],L):- length(L,N), between(0,N,I),length(X,I),
  append(X,[A],Y), append(Y,Z,L),
  append(X,Z,M), perm(B,M).
perm([],[]).
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • I like the first idea and noticed that I had to do something similar to the `mselect([],L,L)` line to prevent failure. My rather verbose crack at it is now added to the question in an edit. :-) – norman Jul 04 '13 at 20:45
1

The usual model to follow is inductive.

If you know how to build all permutation of N-1 elements, then all permutations of N elements are obtained inserting the element in all available positions.

A 'trick of the trade' is using the select/3 builtin, that, like member, 'peek' an element, but removes it from the list and 'returns' the smaller list. Those verbs are not really appropriate for Prolog. Let's say that select/3 is a relation among an element, a list containing it, and an identical list where it's missing.

Then let Prolog do all the search... The resulting code is really tiny...

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • Doesn't `select` still just do a check? This, for example, doesn't work, since the right side list has not been changed: `perm([LH|LT], R) :- select(LH,[LH|LT],R), perm(LT,R).` Maybe I'm missing another level of embedding that I need? This one basically just says, 'Is R the result of removing L's head?," which is of course no, because that's what I'm trying to achieve and not what's true now. – norman Jul 04 '13 at 17:13
  • @nicole, per the GNU Prolog manual, "`select(Element, List1, List2)` removes one occurrence of `Element` in `List1` to provide `List2`." – lurker Jul 04 '13 at 17:32
  • Indeed. But that doesn't seem to be the case when I run it. – norman Jul 04 '13 at 18:51
  • @nicole, `select/3` should do the same thing all the time, as it was designed, unless you are using someone else's custom version. :) So there's something else gone awry. If you want to show your code where you use it, we can resolve that issue. – lurker Jul 04 '13 at 19:04
  • It's in my first comment. The trace is like this on execution: {trace} | ?- perm([1,2,3],[3,1,2]). 1 1 Call: perm([1,2,3],[3,1,2]) ? 2 2 Call: select(1,[1,2,3],[3,1,2]) ? 2 2 Fail: select(1,[1,2,3],[3,1,2]) ? 1 1 Fail: perm([1,2,3],[3,1,2]) ? no – norman Jul 04 '13 at 19:09
  • @nicole `select(1,[1,2,3],X)` succeeds with `X=[2,3]`. – Will Ness Jul 04 '13 at 19:12
  • Right. But something like `X = [2,3]` is what I am trying to achieve in the right list...I don't have it in advance. This declarative stuff is tricky. – norman Jul 04 '13 at 19:17
  • @nicole, your example shows that the predicate fails for appropriate reasons, per Will Ness' comment. `select(1, [1,2,3], [3,1,2]) will fail because `[3,1,2]` is not `[1,2,3]` with the `1` element removed, which is what `select` wants. – lurker Jul 04 '13 at 19:18
  • Exactly. I'm trying to say that maybe I cannot use select to check for permutations because I cannot actually use select to manipulate lists--only to query about them. – norman Jul 04 '13 at 19:22
  • @nicole, you can use `select` to manipulate a list as well. Query occurs when you instantiate everything. If, for example, you want to remove an element from a list (i.e., manipulate) then you would provide an uninstantiated variable for the 3rd parameter. But perhaps that's not what you want in your algorithm. I'm just saying, a predicate can manipulate or query depending upon how you use the parameters. – lurker Jul 04 '13 at 19:28
0

just sort both lists and compare result

user2553650
  • 1