प्रोलॉग

Question

में एक सूची को सॉर्ट करना Prolog के पास चीजों को संभालने का एक अनोखा तरीका है, खासकर जब से प्रत्येक ऑपरेशन में एक तरह से या किसी अन्य का पुनरावृत्ति शामिल होता है।

प्रत्येक भाषा में क्लासिक उदाहरणों में से एक पूर्णांक की सूची को आरोही क्रम में क्रमबद्ध कर रहा है।

पूर्णांक की एक यादृच्छिक सूची क्रमबद्ध करने के लिए एक बहुत ही सही तरीका है (बहुत से अंतर्निर्मित भविष्यवाणियों का उपयोग किए बिना, जो एक प्रकार/2 भविष्यवाणी को रोकता है)?

Answer 1

रोमन बार्टैक की प्रोलॉग प्रोग्रामिंग साइट examples of different sort algorithms देती है, जो एक अनुकूलित क्विकॉर्ट के साथ समाप्त होती है।

quick_sort2(List,Sorted):-q_sort(List,[],Sorted). 
q_sort([],Acc,Acc). 
q_sort([H|T],Acc,Sorted):- 
    pivoting(H,T,L1,L2), 
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted) 

Answer 2

जहाँ तक मुझे सबसे अच्छा छँटाई सीधे Prolog में लिखा एल्गोरिदम पता है, संदर्भ के बिना करने के लिए किसी विशेष बनाया-इन मर्ज प्रकार के कुछ फार्म का उपयोग के रूप में।

एक लगातार अनुकूलन लंबाई 1 की सूचियों के साथ विलय शुरू करना है, लेकिन पहले से क्रमबद्ध सेगमेंट के साथ।

है, सूची [4,5,3,6,2,7,1,2], सूचियों [4,5], [3,6], [2,7] सॉर्ट करने के लिए, [1,2] विलय कर दिया जाएगा।

इसे क्रमबद्ध दिशाओं में न केवल क्रमबद्ध दिशाओं में, बल्कि दूसरी दिशा में भी जोड़कर अनुकूलित किया जा सकता है। इस उपर्युक्त उदाहरण के लिए मतलब यह होगा कि हल कर खंड इस प्रकार इकट्ठे जाता है:

[4,5|_] 
[3,4,5|_] 
[3,4,5,6|_] 
... 

ध्यान दें कि Prolog में यह सीधे आगे है दोनों शुरुआत में और अंत में एक सूची का विस्तार करने के लिए।

इस प्रकार, हमें केवल [1,2,3,4,5,6,7] और [2] मर्ज करना होगा।

रिचर्ड ओ'केफ के मूल कार्यान्वयन (~ 1 9 84) का उपयोग करने वाली एक मौजूदा प्रणाली Ciao-Prolog ciao-1.15/lib/sort.pl में Ciao-Prolog है।