Prolog-3个元素的第N个排列

Question

我想得到3个元素的第n个排列。如。

列表=[1,2,3]n=5

输出 [1，2，3，1，2] [1，2，3，2，1] ...

我不想要任何连续的相同元素，例如[1，1，1，1，1] [1，2，3，3，2]...

我尝试了几个可以获得完整排列的方法，无法弄清楚如何获得我需要的东西。

varia_repp(N,RVaria):-varia_rep(N,[1,2,3],RVaria).

varia_rep(0,_,[]).
varia_rep(N,[H|L],RVaria):-N>0,N1 is N-1,delete(H,[H|L],_),varia_rep(N1,[H|L],RVaria).

或

perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([],[]).

Answer 1

从您的示例来看，您不需要K个元素的第N次排列(在您的示例中K = 3)，但是需要N个元素的排列，其中N的列表是用模板列表中的元素填充构建的，然后进行过滤以排除连续的相等元素:

varia_rep(N, L, P) :-
  build_rep(L, N, P0),
  permutation(P0, P),
  \+ append(_, [X,X|_], P).

build_rep(L, N, P0) :-
  length(L, K),
  findall(X, (between(1, N, I), J is ((I-1) mod K) + 1, nth1(J, L, X)), P0).

测试：

?- build_rep([1,2,3],5,P).
P = [1, 2, 3, 1, 2].

?- varia_rep(5,[1,2,3],P).
P = [1, 2, 3, 1, 2] ;
P = [1, 2, 3, 2, 1] ;
P = [1, 2, 1, 3, 2] ...

Answer 2

这样做的一种方法（请注意，排列是按词典顺序排列的）是明确声明两个连续的元素不能相同：

perm(1, Input, [Last]) :-
    member(Last, Input).
perm(N, Input, [First,Second|Perm]) :-
    N > 1, N0 is N-1,
    member(First, Input),
    dif(First, Second),
    perm(N0, Input, [Second|Perm]).

?- perm(3,[a,b,c],R).
R = [a, b, a] ;
R = [a, b, c] ;
R = [a, c, a] ;
R = [a, c, b] ;
R = [b, a, b] ;
R = [b, a, c] ;
R = [b, c, a] ;
R = [b, c, b] ;
R = [c, a, b] ;
R = [c, a, c] ;
R = [c, b, a] ;
R = [c, b, c] ;
false.

您已经用swi-prolog标记了这个问题。它有一个谓词dif/2，就像其他主要的Prolog实现一样。您还可以在StackOverflow上找到一些关于dif/2的有趣讨论，包括优点和缺点。总而言之，它提出了一个约束，它的两个参数无法统一。它可以用于非实例化变量，在这种情况下，可以防止大量不必要的回溯，而无需任何明确的切割或额外的参数。

此外，不推荐使用 delete/3，取而代之的是 select/3。但是，在这里您只需要成员/ 2（因为您想重用元素）。

编辑

正如评论中指出的，虽然dif/2使内容更短，但它可能会有点混乱。这是一个几乎相同的版本，没有dif/2(对于较大的N来说，它的运行速度也快得多)。

p(N, Input, [First|Rest]) :-
    N >= 1, N0 is N-1,
    member(First, Input),
    p(N0, Input, First, Rest).

p(0, _, _, []).
p(N, Input, Prev, [This|Rest]) :-
    N > 0, N0 is N-1,
    member(This, Input), This \= Prev,
    p(N0, Input, This, Rest).