सूची के सभी क्रमपरिवर्तन [1, 1, 2, 2, ..., एन, एन] उत्पन्न करें जहां प्रत्येक जोड़ी के बीच तत्वों की संख्या प्रोलॉग

Question

में भी है, मैंने हाल ही में प्रोलॉग सीखना शुरू किया और मुझे लिखने का काम मिला एक विधेय list(N, L) कि सूचियों एल ऐसी है कि उत्पन्न करता है:

• एल है लंबाई 2N,
• 1 और एन के बीच हर संख्या वास्तव में एल में दो बार होती है, तो
एक ही तत्व के प्रत्येक जोड़ी के बीच
• वहाँ एक और भी है अन्य तत्वों की संख्या,
• प्रत्येक संख्या की पहली घटनाएं बढ़ती क्रम में हैं एर।

लेखक कहता है कि एन हैं! ऐसी सूचियां

उदाहरण के लिए, एन = 3 के लिए सभी समाधान हैं:

?- list(3, L). 
L = [1, 1, 2, 2, 3, 3] ; 
L = [1, 1, 2, 3, 3, 2] ; 
L = [1, 2, 2, 1, 3, 3] ; 
L = [1, 2, 2, 3, 3, 1] ; 
L = [1, 2, 3, 3, 2, 1] ; 
L = [1, 2, 3, 1, 2, 3] ; 
false. 

मेरे वर्तमान समाधान लगता है:

even_distance(H, [H | _]) :- 
    !. 
even_distance(V, [_, _ | T]) :- 
    even_distance(V, T). 

list(N, [], _, Length, _, _) :- 
    Length =:= 2*N, 
    !. 
list(N, [New | L], Max, Length, Used, Duplicates) :- 
    select(New, Duplicates, NewDuplicates), 
    even_distance(New, Used), 
    NewLength is Length + 1, 
    list(N, L, Max, NewLength, [New | Used], NewDuplicates). 
list(N, [New | L], Max, Length, Used, Duplicates) :- 
    Max < N, 
    New is Max + 1, 
    NewLength is Length + 1, 
    list(N, L, New, NewLength, [New | Used], [New | Duplicates]). 

list(N, L) :- 
    list(N, L, 0, 0, [], []). 

यह है दो बातें:

• यदि वर्तमान अधिकतम है एन से कम, उस नंबर को सूची में जोड़ें, इसे डुप्लिकेट की सूची पर रखें, और अधिकतम अपडेट करें;
• कुछ डुप्लिकेट का चयन करें, जांचें कि इसके बीच तत्वों की संख्या और सूची में पहले से मौजूद संख्या (यानी वह संख्या अजीब स्थिति पर है), फिर इसे सूची में जोड़ें और इसे डुप्लिकेट से हटा दें।

यह काम करता है, लेकिन यह धीमा है और वास्तव में अच्छा नहीं दिखता है।

इस अभ्यास के लेखक से पता चलता है कि एन < 12 के लिए, उनका समाधान ~ 11 संदर्भों के औसत (time/1 का उपयोग करके और एन द्वारा परिणाम विभाजित करने के साथ) की एक सूची उत्पन्न करता है। मेरे समाधान के साथ यह ~ 60 तक बढ़ता है।

1. कैसे इस एल्गोरिथ्म सुधार करने के लिए:

   मैं दो प्रश्न हैं?

2. क्या यह समस्या किसी अन्य ज्ञात व्यक्ति को सामान्यीकृत की जा सकती है? मैं मल्टीसेट [1, 1, 2, 2, ..., n, n] (उदाहरण के लिए लैंगफोर्ड जोड़ी) के आधार पर समान समस्याओं के बारे में जानता हूं, लेकिन ऐसा कुछ नहीं मिला।

मैं पूछ रहा हूं क्योंकि मूल समस्या एक स्वयं-छेड़छाड़ बंद वक्र में चौराहे की गणना करने के बारे में है। आप इस तरह के वक्र को खींचते हैं, एक बिंदु और दिशा चुनें और वक्र का पालन करें, पहली बार मिलने पर प्रत्येक छेड़छाड़ की गणना करें और दूसरी बैठक में संख्या दोहराएं: example (उत्तर [1, 2, 3, 4, 5, 3, 6, 7, 8, 1, 9, 5, 4, 6, 7, 9, 2, 8] के साथ)।

लेखक कहता है कि प्रत्येक ऐसा वक्र अनुमानित list को संतुष्ट करता है, लेकिन प्रत्येक सूची एक वक्र से मेल नहीं खाती है।

Answer 1

मुझे तत्वों की गिनती से अलग पूर्णांक के जोड़े के बारे में आवश्यकता को पूरा करने के लिए अंकगणित का सहारा लेना पड़ा। अंकगणित के बिना हल करने में सक्षम होने के लिए अच्छा होगा ...

 

list(N,L) :- numlist (1,N,H), list_(H,L), even_(L). 

list_([D|Ds],[D|Rs]) :- 
    list_(Ds,Ts), 
    select (D,Rs,Ts). 
list_([],[]). 

even_(L) :- 
    forall(nth0(P,L,X), (nth0(Q,L,X), abs(P-Q) mod 2 =:= 1)). 

चयन/3 'डालने मोड' में उपयोग किया जाता है।

संपादित अंकगणित से बचने के लिए, हम इस अधिक वर्बोज़ स्कीमा

even_(L) :- 
    maplist(even_(L),L). 
even_(L,E) :- 
    append(_,[E|R],L), 
    even_p(E,R). 
even_p(E,[E|_]). 
even_p(E,[_,_|R]) :- even_p(E,R). 

संपादित

यहाँ खाली 'स्लॉट' के एक पहले से बनाए गए सूची में असाइनमेंट के आधार पर एक टुकड़ा है इस्तेमाल कर सकते हैं। मेरे परीक्षण के आधार पर, यह आपके समाधान से तेज़ है - लगभग 2 गुना।

list(N,L) :- 
    N2 is N*2, 
    length(L,N2), 
    numlist(1,N,Ns), 
    pairs(Ns,L). 

pairs([N|Ns],L) :- first(N,L,R),even_offset(N,R),pairs(Ns,L). 
pairs([],_). 

first(N,[N|R],R) :- !. 
first(N,[_|R],S) :- first(N,R,S). 

even_offset(N,[N|_]). 
even_offset(N,[_,_|R]) :- even_offset(N,R). 

मेरे पहले प्रयास, even_/1 के बाद हर प्रविष्टि के साथ छानने, बहुत धीमी थी। मैं शुरुआत में चयन/3 के तुरंत बाद फ़िल्टर को धक्का देने पर केंद्रित था, और प्रदर्शन वास्तव में आखिरी स्निपेट के रूप में लगभग अच्छा था, लेकिन हां, यह 6 में से एक समाधान खो देता है ...