Prolog: की गणना OEIS A031877 ("nontrivial उलट संख्या") CLP का उपयोग कर (FD)

ब्राउज़िंग के माध्यम से भयानकOn-Line Encyclopedia of Integer Sequences (सीएफ en.wikipedia.org), मैं निम्नलिखित पूर्णांक अनुक्रम पर ठोकर खाई:Prolog: की गणना OEIS A031877 ("nontrivial उलट संख्या") CLP का उपयोग कर (FD)

A031877: nontrivial उलट संख्या (संख्या है जो अपने बदलाव के पूर्णांक गुणज हैं), मुरजबंध संबंधी संख्या और 10.

के गुणकों को बाहर निकाल कर कुछ कोड मैंने लिखा फिर से उपयोग करते हुए मेरा उत्तर th करने के लिए ई संबंधित प्रश्न "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 एक ठोस पूर्णांक है । N_digit के पहले 100 मानों के लिए स्वयं के लिए देखें!

?- 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 (*) डोमेन (बी, क्यू, आर, सेट) के बारे में क्या? या विभिन्न स्थिरता/प्रचार तकनीक? या बल्कि प्रोलॉग शैली coroutining?

विचार मिला? मुझे सब चाहिए! अग्रिम में धन्यवाद।

स्रोत

2015-09-16 repeat

अब तक ... कोई जवाब :(

मैं निम्नलिखित के साथ आया था ...

कैसे 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.

चलो कुछ runtimes मापें के बारे में!

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

अभी भी सुधार के लिए बहुत सारे कमरे हैं, निश्चित रूप से! वहाँ होना चाहिए ...

स्रोत

2015-09-25 12:51:42 repeat

हम संख्या-सैद्धांतिक गुणों को बाधाओं की भाषा में अनुवाद करके बेहतर कर सकते हैं!

सभी शर्तें फॉर्म 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.45 एम -> 73k, 5 एम -> 17 9 के, 15.1 एम -> 348k।

क्या हम और भी बेहतर कर सकते हैं (कोड की घोषणाशीलता को संरक्षित करते समय)? मुझे नहीं पता, मुझे लगता है ...

स्रोत

2015-10-29 03:14:06 repeat

Prolog: की गणना OEIS A031877 ("nontrivial उलट संख्या") CLP का उपयोग कर (FD)

उत्तर

संबंधित मुद्दे