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

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