Prolog:使用clp(FD)计算OEIS A031877("非平凡反转数")

Question

浏览令人敬畏 的整数序列在线百科全书(参见en.wikipedia.org),我偶然发现了以下整数序列:

A031877:非平凡反转数字(数字是其反转的整数倍),不包括回文数和10的倍数.

通过重新使用我为相关问题" 在Prolog中更快地实现语音算法 "的答案而编写的一些代码,我可以毫不费力地写下解决方案 - 感谢clpfd!

:- use_module(library(clpfd)).

我们基于 (先前定义)定义核心关系 :a031877_ndigits_/3digits_number/2

a031877_ndigits_(Z_big,N_digits,[K,Z_small,Z_big]) :-
   K #> 1,
   length(D_big,N_digits),
   reverse(D_small,D_big),
   digits_number(D_big,Z_big),
   digits_number(D_small,Z_small),
   Z_big #= Z_small * K.

核心关系是确定性的,只要是具体的整数,就会 普遍终止N_digit.亲眼看看前100个值N_digit!

?- time((N in 0..99,indomain(N),a031877_ndigits_(Z,N,Zs),false)).
% 3,888,222 inferences, 0.563 CPU in 0.563 seconds (100% CPU, 6903708 Lips)
false

让我们运行一些查询!

?- a031877_ndigits_(87912000000087912,17,_).
  true                                % succeeds, as expected
; false.

?- a031877_ndigits_(87912000000987912,17,_).
false.                                % fails, as expected

接下来,让我们找一些包含正好四位小数的非平凡反转数字:

?- a031877_ndigits_(Z,4,Zs), labeling([],Zs).
  Z = 8712, Zs = [4,2178,8712]
; Z = 9801, Zs = [9,1089,9801]
; false.

好!让我们测量证明上述查询的通用终止所需的运行时间!

?- time((a031877_ndigits_(Z,4,Zs),labeling([],Zs),false)).
% 11,611,502 inferences, 3.642 CPU in 3.641 seconds (100% CPU, 3188193 Lips)
false.                                % terminates universally

现在,这太长了!

我该怎么做才能加快速度？使用不同和/或其他约束？也许甚至多余的？或者可以识别并消除削减搜索空间大小的对称性？那些不同的clp(*)域(b,q,r,set)怎么样？或者不同的一致性/传播技术？或者更确切地说是Prolog风格的coroutining？

有想法吗？我想要他们!提前致谢.

Answer 1

到目前为止...没有答案:(

我想出了以下...

使用不同的变量怎么样labeling/2？

a031877_ndigits NEW _(Z_big,N_digits,/* [K,Z_small,Z_big] */
                                       [K|D_big] ) :-
   K #> 1,
   长度(D_big,N_digits),
   反向（D_小，D_大），
   数字数(D_big,Z_big),
   数字数（D_小，Z_小），
   Z_big #= Z_small * K。

让我们测量一些运行时间！

?- time((a031877_ndigits_(Z,4,Zs),labeling([ff],Zs),false)).
% 14,849,250 inferences, 4.545 CPU in 4.543 seconds (100% CPU, 3267070 Lips)
false.

?- time((a031877_ndigitsNEW_(Z,4,Zs),labeling([ff],Zs),false)).
%    464,917 inferences, 0.052 CPU in 0.052 seconds (100% CPU, 8962485 Lips)
false.

更好的！但我们能更进一步吗？

?- time((a031877_ndigitsNEW_(Z,5,Zs),labeling([ff],Zs),false)).
%  1,455,670 inferences, 0.174 CPU in 0.174 seconds (100% CPU, 8347374 Lips)
false.

?- time((a031877_ndigitsNEW_(Z,6,Zs),labeling([ff],Zs),false)).
%  5,020,125 inferences, 0.614 CPU in 0.613 seconds (100% CPU, 8181572 Lips)
false.

?- time((a031877_ndigitsNEW_(Z,7,Zs),labeling([ff],Zs),false)).
% 15,169,630 inferences, 1.752 CPU in 1.751 seconds (100% CPU, 8657015 Lips)
false.

当然，还有很大的改进空间！必须有...