3

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

我需要创建 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 个）

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

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

谢谢 :D

4

3 回答 3

4

您可以使用 非常快速地做到这一点dif/2，它限制两个变量具有不同的值，而无需事先知道这些值：

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

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

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

使用它，您可以创建一个谓词来约束一个列表，使得没有两个元素是相同的：

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

现在找到你想要的约束排列：

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

我不确定是否dif/2是标准 Prolog，但主要实现都有它。

于 2011-04-15T15:06:03.820 回答
4

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

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

该代码将在回溯时给出所有有效的排列。我会留给你一个练习来丢弃重复排列。

于 2011-04-08T17:11:57.280 回答
2

我们my_perm/2基于same_length/2、 list_permuted/2、和定义mapadj/2：

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

通用 mapadj/2可以这样定义：

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

这是OP 给出的示例查询1,2 。

我们call_time/2用于以毫秒为单位测量运行时间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.

我们需要多长时间才能找到前几个解决方案？

?- 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]
...

请注意，T_ms它是单调增长的：它测量自首次调用给定目标以来所花费的时间。

枚举所有解决方案需要多长时间？

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

有多少解决方案？

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

脚注 1：使用 SICStus Prolog 版本 4.3.2 (x86_64-linux-glibc2.12)。
脚注 2：为了便于阅读，对 Prolog 处理器给出的答案序列进行了调整。

于 2015-10-19T11:06:46.147 回答