3

hello everyone pls forgive any misuse of the language

i need to create myPermutation(L1,L2). which given a list L1 (which has elements with many concecutive appearances) returns a list L2 which is L1 sorted in a way that there are no two concecutive elements which are the same)

example: given the list L1[1,1,1,1,1,2,2,3,3,4,4,5,5] L2 should be [1,2,1,5,1,3,1,4,1,2,3,5,4] i have tried random permutations and checking each permutation for consistency but it is very slow (aprox 24 cpus for L1 with more than 12 elements)

the only possible solution is to make a consistent permutation instead of checking for one but how can i do this?

it probalby can be done even with standard prolog but since my understanding of logic programming is poor enough i can't get my head around it

thank you :D

false
  • 10,264
  • 13
  • 101
  • 209
ndp
  • 873
  • 1
  • 11
  • 24
  • Should the permutations be done in a way that doesn't "duplicate" solutions that involve equal items appearing in the same location as for another solution? That's the first thing that occurred to me to worry about. Avoiding "repeats" in the solution's sequence seems a fairly simple modification of the usual "permute" predicate. – hardmath Apr 10 '11 at 01:07

3 Answers3

4

You can build such permutations inspecting the list.

myPermutation([], []).
myPermutation(L, [H|P]):-
  select(H, L, NL), % Select one item from the list
  myPermutation(NL, H, P).

myPermutation([], _, []).
myPermutation(L, H, [I|P]):-
  select(I, L, NL), % Select another item
  I \= H, % Enforce restriction of no duplicate consecutive items
  myPermutation(NL, I, P).

This code will give, upon backtracking, all the valid permutations. I'll leave you as an exercise a way to discard duplicate permutations.

gusbro
  • 22,357
  • 35
  • 46
4

You can do this quite quickly with dif/2, which contrains two variables to have different values without knowing those values beforehand:

?- dif(X,Y).
dif(X, Y).

?- dif(X,Y), X=1.
X = 1,
dif(1, Y).

?- dif(X,Y), X=1, Y=1.
false.

Using this, you can make a predicate that constrains a list such that no two elements are the same:

conseq_dif([]).
conseq_dif([_]).
conseq_dif([X,Y|Xs]) :-
    dif(X,Y),
    conseq_dif([Y|Xs]).

Now to find the constrained permutations you want:

constrained_perm(Lst,Prm) :-
    length(Lst,N),
    length(Prm,N),           % make list of N unbound variables
    conseq_dif(Prm),
    permutation(Lst,Prm).    % "ordinary" (library) permutation finding

I'm not sure if dif/2 is standard Prolog, but the major implementations have it.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
2

We define my_perm/2 based on same_length/2, list_permuted/2, , and mapadj/2:

my_perm(Xs,Ys) :-
   same_length(Xs,Ys),
   mapadj(dif,Ys),
   list_permuted(Xs,Ys).

The versatile mapadj/2 can be defined like this:

:- meta_predicate mapadj(2,?), list_mapadj(?,2), list_prev_mapadj(?,?,2).
mapadj(P_2,Xs) :-
   list_mapadj(Xs,P_2).

list_mapadj([],_).
list_mapadj([A|As],P_2) :-
   list_prev_mapadj(As,A,P_2).

list_prev_mapadj([],_,_).
list_prev_mapadj([A1|As],A0,P_2) :-
   call(P_2,A0,A1),
   list_prev_mapadj(As,A1,P_2).

Here comes the sample query1,2 given by the OP.

We use call_time/2 for measuring the runtime in milli-seconds T_ms.

?- call_time(my_perm([1,1,1,1,1,2,2,3,3,4,4,5,5],[1,2,1,5,1,3,1,4,1,2,3,5,4]),T_ms).
T_ms = 0.

How long does it take us to find the first few solutions?

?- call_time(my_perm([1,2,1,5,1,3,1,4,1,2,3,5,4],Xs),T_ms).
  T_ms =  0, Xs = [1,2,1,5,1,3,1,4,1,2,3,5,4]
; T_ms =  0, Xs = [1,2,1,5,1,3,1,4,1,2,3,4,5]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,5,3,4]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,4,3,5]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,5,4,3]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,4,5,3]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,3,2,5,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,3,2,4,5]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,5,2,3,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,4,2,3,5]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,5,2,4,3]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,4,2,5,3]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,3,5,2,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,3,4,2,5]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,5,3,2,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,4,3,2,5]
; T_ms = 30, Xs = [1,2,1,5,1,3,1,4,1,5,4,2,3]
; T_ms = 30, Xs = [1,2,1,5,1,3,1,4,1,4,5,2,3]
...

Note that T_ms grows monotonically: it measures the time spent since it first called the given goal.

How long does it take to enumerate all solutions? 

?- call_time(\+((my_perm([1,1,1,1,1,2,2,3,3,4,4,5,5],_),false)),T_ms).
T_ms = 4030.

How many solutions are there?

?- use_module(library(aggregate)),
   aggregate(count,Xs,my_perm([1,2,1,5,1,3,1,4,1,2,3,5,4],Xs),N).
N = 197664.

Footnote 1: Using SICStus Prolog version 4.3.2 (x86_64-linux-glibc2.12).
Footnote 2: The answer sequences given by the Prolog processor have been adapted for the sake of readability.

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