permutation of list with multiple same elements Prolog

Question

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

Answer 1

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.

Answer 2

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.