问题描述
我想获得3个元素的第n个排列.例如.
I would like to get the nth permutation of 3 elements.Eg.
列表= [1,2,3]n = 5
List = [1,2,3]n = 5
输出[1,2,3,1,2][1,2,3,2,1]...
Output[1,2,3,1,2][1,2,3,2,1]...
我不希望任何连续的相同元素，例如[1,1,1,1,1][1,2,3,3,2]...
I don't want any continuous same element such as[1,1,1,1,1][1,2,3,3,2]...
我尝试了很少的方法可以得到完整的排列，无法弄清楚如何获得所需的东西.
I have try few which can get the full permutation, couldn't figure how to get what I needed.
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([],[]).
推荐答案
做到这一点的一种方法(请注意，排列顺序按字典顺序)是明确声明两个连续的元素不能相同:
One way to do this (note that the permutations are in lexicographical order) is to explicitly state that two consecutive elements cannot be the same:
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标记了问题.与其他主要Prolog实现一样，它具有谓词 dif/2 . .您还可以在StackOverflow上找到很多有趣的关于dif/2的讨论，各有利弊.总而言之，它构成了两个论点不能统一的约束.它可以用于非实例化的变量，在这种情况下，可以避免很多不必要的回溯，而无需任何显式的削减或额外的参数.
You have tagged the question with swi-prolog. It has a predicate dif/2, like other major Prolog implementations. You can also find quite a few interesting discussions on StackOverflow about dif/2, with pros and cons. To summarize, it poses a constraint that its two arguments cannot unify. It can be used for non-instantiated variables and in this case prevents a lot of unnecessary backtracking without any explicit cuts or extra arguments.
此外，不赞成使用delete/3，而建议使用select/3.但是在这里，您只需要member/2(因为您想重用元素).
Also, delete/3 is deprecated in favor of select/3. Here however you only need member/2 (as you want to reuse elements).
编辑
如评论中所指出的那样，尽管dif/2使事情变得更短，但可能有些令人困惑.这是一个几乎完全相同，但没有dif/2的详细版本(对于较大的N，它的运行速度也要快得多).
As pointed out in the comments, while dif/2 keeps things shorter, it might be a bit confusing. Here is an almost identical, slightly more verbose version without dif/2 (which happens to also work much faster for larger N's).
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).
这篇关于Prolog-3个元素的第N个置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！