Пролога: вычисление OEIS A031877 ("нетривиальное число разворота") с помощью CLP (FD)

Question

просмотра через удивительныйOn-Line Encyclopedia of Integer Sequences (ср en.wikipedia.org), я наткнулся на следующую последовательность: целочисленного

A031877: Нетривиальные развороты номер (номер, которые являются целыми числами, кратными их инверсий), за исключением палиндромных чисел и кратных 10.

При повторном использовании код, который я написал для моего ответа я e related question "Faster implementation of verbal arithmetic in Prolog" Я мог бы написать решение довольно легко - благодаря clpfd!

:- use_module(library(clpfd)). 

Определим ядро ​​отношениеa031877_ndigits_/3, основанный на digits_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. 

OK! Давайте измерять время выполнения, необходимое для доказательства универсального завершения вышеуказанного запроса!

?- 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)? Или разные методы консистенции/распространения? Или, скорее, сопроводительный стиль Пролога?

Есть идеи? Я хочу их всех! Заранее спасибо.

Answer 1

до сих пор ... нет ответов :(

я придумал следующее ...

Как об использовании различных переменных для labeling/2?

 
a031877_ndigitsNEW_(Z_big,N_digits,/* [K,Z_small,Z_big] */ 
             [K|D_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. 

Замерят некоторую автономную работу!

?- 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. 

Есть еще много возможностей для улучшения, конечно! Должно быть ...

Answer 2

Мы можем сделать лучше, переведя теоретико-числовые свойства в язык ограничений!

Все термины имеют форму 87 ... 12 = 4 * 21 ... 78 или 98 ... 01 = 9 * 10 ... 89.

Мы реализуем a031877_ndigitsNEWER_/3 на a031877_ndigitsNEW_/3 основе и непосредственно добавить выше имущества в виде двух ограничений конечно-домена:

 
a031877_ndigitsNEWER_(Z_big,N_digits,[K|D_big]) :- 
    K in {4}\/{9},      % (new) 
    length(D_big,N_digits), 
    D_big ins (0..2)\/(7..9),    % (new) 
    reverse(D_small,D_big), 
    digits_number(D_big,Z_big), 
    digits_number(D_small,Z_small), 
    Z_big #= Z_small * K. 

Давайте повторно запустить тесты, которые мы использовали раньше!

?- time((a031877_ndigitsNEWER_(Z,5,Zs),labeling([ff],Zs),false)). 
% 73,011 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 11602554 Lips) 
false. 

?- time((a031877_ndigitsNEWER_(Z,6,Zs),labeling([ff],Zs),false)). 
% 179,424 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 6399871 Lips) 
false. 

?- time((a031877_ndigitsNEWER_(Z,7,Zs),labeling([ff],Zs),false)). 
% 348,525 inferences, 0.037 CPU in 0.037 seconds (100% CPU, 9490920 Lips) 
false. 

Резюме: В течение трех запросов мы последовательно наблюдали значительное сокращение требуемого поиска. Просто рассмотрите, насколько количество умозаключений сокращается: 1.45M -> 73k, 5M -> 179k, 15.1M -> 348k.

Можем ли мы сделать еще лучше (сохраняя декларативность кода)? Я не знаю, наверное ...