0

我想获得 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([],[]).
4

2 回答 2

2

从您的示例来看，您不需要 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] ...
于 2013-08-19T07:55:49.500 回答
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。但是，在这里您只需要 member/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).
于 2013-08-19T06:51:35.913 回答