Prolog-3个元素的第N个置换 [英] Prolog - Nth Permutation of 3 elements

问题描述

我想获得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个置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！