list - 具有多个相同元素的列表的排列Prolog

Question

大家好，请原谅任何对语言的滥用

我需要创建 myPermutation(L1,L2)。给定一个列表 L1(它具有许多连续出现的元素)返回一个列表 L2，该列表 L1 的排序方式是没有两个相同的连续元素)

例子:给定列表 L1[1,1,1,1,1,2,2,3,3,4,4,5,5] L2 应该是 [1,2,1,5,1, 3,1,4,1,2,3,5,4]我已经尝试过随机排列并检查每个排列的一致性，但它非常慢(L1 大约 24 cpu，超过 12 个元素)

唯一可能的解决方案是进行一致的排列而不是检查一个但是我该怎么做呢？

即使使用标准 prolog 也可以做到这一点，但由于我对逻辑编程的理解很差，我无法理解它

谢谢你:D

Answer 1

您可以构建这样的排列来检查列表。

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).

此代码将在回溯时给出所有有效的排列。我将留给你一个练习，作为一种丢弃重复排列的方法。