相关疑难解决方法(0)

如何生成列表元素的所有可能组合？

例如,给定列表[1,2,3],我想设计一个谓词,其形式comb([1,2,3], L).应返回以下答案L:

[1]  
[2]  
[3]  
[1,2]  
[2,1]  
[1,3]  
[3,1]  
[2,3] 
[3,2]  
[1,2,3]  
[1,3,2]  
[2,1,3]  
[2,3,1]  
[3,1,2]  
[3,2,1] 

我想用DCG作为发电机.截至目前,语法是

s-->a,b.
a-->[].
a-->a,c.
c-->[t1].
c-->[t2].
b-->[t3].
b-->[t4].

我想生成所有s地方的长度a是< someNumber.

使用?- phrase(a,X),length(X,Y),Y<4.i可以获得 a少于4项的所有内容.但是,当所有组合都用尽时,系统(SWI-Prolog 6.2.5)似乎停滞不前.有时候,这里也提出了类似的问题.但是,作为Prolog的新手,我无法使用上面的语法.有任何想法吗？

更新:(canrememberthename)有一个评论被删除,不知何故.无论如何,有人建议between(1,4,Y),length(X,Y),phrase(a,X).用来设定限制.将代码更改为后,这很有效a-->c,a.

目前,我可以使用以下暴力Prolog代码枚举带根的 平面 未标记二进制树.

e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].

注意:请参阅下面的输出列表.

并使用增加大小输出它们

es(S) :-
    length(Ls, _),
    phrase(e, Ls),     % or e(Ls,[]),
    atomic_list_concat(Ls,S).

然而,这是低效的强力算法.

是否有更有效的算法来枚举带根的平面未标记二进制树？

注意:树可以通过使用前两次迭代中的树来生成,想一想Fibonacci数,并添加一元分支或二元分支,但这会导致重复的树.我自己可以做那个版本,我正在寻找的是一种算法,它可以在没有重复的情况下以高效的方式生成树.

注意:二叉树也称为二进制表达式树或K <= 2 的K-ary树.

补充

结果

我对M(15)的暴力版本需要1小时27分钟,而M(15)的高效版本需要大约2秒钟.

显然,有效的算法就是这样,效率更高,为什么我问这个问题.

莫兹金数字

具有N根节点平面未标记二进制树的节点的树的数量由Motzkin数给出.见:OEIS A001006

Nodes  Trees
1      1
2      1
3      2
4      4
5      9

具有N个内部节点的树的数量由带有根的平面未标记二进制树由加泰罗尼亚数字给出.有一种更有效的算法,用于使用加泰罗尼亚数生成有根平面二叉树.

注意:
基于加泰罗尼亚数字的树的数量没有一元分支,只计算内部节点.

而

基于Motzkin数字的树的数量 …

我试图了解N-queens问题的解决方案,如下所示:

:- use_module(library(clpfd)).

n_queens(N, Qs) :-
    length(Qs, N),
    Qs ins 1..N,
    safe_queens(Qs).

safe_queens([]).
safe_queens([Q|Qs]) :-
    safe_queens(Qs, Q, 1),
    safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
    Q0 #\= Q,
    abs(Q0 - Q) #\= D0,
    D1 #= D0 + 1,
    safe_queens(Qs, Q0, D1).

我无法理解以下代码段:

safe_queens([]).
safe_queens([Q|Qs]) :-
    safe_queens(Qs, Q, 1),
    safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
    Q0 #\= Q,
    abs(Q0 - Q) #\= D0,
    D1 #= D0 + 1,
    safe_queens(Qs, Q0, D1).

请帮我理解.任何帮助将不胜感激.