योजना में हार पैदा करने के लिए अच्छा सरल एल्गोरिदम?

Question

लम्बाई एन के के-आरी हार लंबाई की एन की एक आदेशित सूची है जिसका आइटम लंबाई के वर्णमाला से खींचा जाता है, जो रोटेशन के तहत ऑर्डरिंग साझा करने वाली सभी सूचियों में लेक्सिकोोग्राफ़िक रूप से पहली सूची है।

उदाहरण: (1 2 3) और (1 3 2) वर्णमाला से लंबाई 3 के हार हैं {1 2 3}।

और जानकारी: http://en.wikipedia.org/wiki/Necklace_(combinatorics)

मैं योजना में इन जेनरेट करना चाहते हैं (या अपनी पसंद का एक लिस्प)। उत्पन्न हार
Sawada के लिए एक नई एल्गोरिथ्म - - मैं कुछ कागजात ...
सैवेज पाया है उत्पन्न लगातार परिशोधित समय में कंगन
Sawada - उत्पन्न हार निषिद्ध सबस्ट्रिंग
... लेकिन उनमें में प्रस्तुत कोड है साथ मेरे लिए अपारदर्शी मुख्य रूप से क्योंकि वे या तो वर्णमाला या लंबाई (एन) वांछित में गुजरने लगते हैं। जिस योजना की प्रक्रिया मैं ढूंढ रहा हूं वह फॉर्म (हारलेस एन '(ए बी सी ...) है।

मैं पहली बार के^एन सूचियों को उत्पन्न करके और फिर घूर्णन को फ़िल्टर करके इन्हें काफी आसान बना सकता हूं। लेकिन यह बहुत मेमोरी-अक्षम है ...

धन्यवाद!

Answer 1

मैं दो चरणों की प्रक्रिया करता हूं। सबसे पहले, वर्णों से एन तत्वों के प्रत्येक संयोजन को ढूंढें। फिर, प्रत्येक संयोजन के लिए, सबसे कम मूल्य चुनें, और शेष वस्तुओं के सभी क्रमपरिवर्तन उत्पन्न करें।

संपादित करें: यहां कुछ कोड है। यह मानता है कि इनपुट सूची पहले से ही क्रमबद्ध है और इसमें कोई डुप्लीकेट नहीं है।

(define (choose n l) 
    (let ((len (length l))) 
    (cond ((= n 0) '(())) 
      ((> n len) '()) 
      ((= n len) (list l)) 
      (else (append (map (lambda (x) (cons (car l) x)) 
          (choose (- n 1) (cdr l))) 
         (choose n (cdr l))))))) 

(define (filter pred l) 
    (cond ((null? l) '()) 
     ((pred (car l)) (cons (car l) (filter pred (cdr l)))) 
     (else (filter pred (cdr l))))) 

(define (permute l) 
    (cond ((null? l) '(())) 
     (else (apply append 
        (map (lambda (x) 
          (let ((rest (filter (lambda (y) (not (= x y))) l))) 
           (map (lambda (subperm) (cons x subperm)) 
            (permute rest)))) 
         l))))) 

(define (necklaces n l) 
    (apply 
    append 
    (map 
    (lambda (combination) 
     (map (lambda (permutation) 
       (cons (car combination) permutation)) 
      (permute (cdr combination)))) 
    (choose n l)))) 


(display (choose 1 '(1 2 3 4 5))) (newline) 
(display (choose 2 '(1 2 3 4 5))) (newline) 
(display (permute '(1 2))) (newline) 
(display (permute '(1 2 3))) (newline) 
(display (necklaces 3 '(1 2 3 4))) (newline) 
(display (necklaces 2 '(1 2 3 4))) (newline) 

Answer 2

उदाहरण: (1 2 3) और (1 से 3 2) वर्णमाला {1 2 3} से लंबाई 3 की हार है।

आप भूल गया (1 1 1) (1 1 2) (1 1 3) (1 2 2) (1 3 3) (2 2 2) (2 2 3) (2 3 3) (3 3 3)। हार में डुप्लिकेट हो सकते हैं।

यदि आप केवल आकार एन के वर्णमाला से खींचे गए लंबाई एन के हार की तलाश में थे, जिसमें कोई डुप्लिकेट नहीं है, तो यह बहुत आसान है: (एन -1) होगा! हार, और प्रत्येक हार (1 :: perm) के रूप में होगी जहां perm {2 .. एन} का कोई क्रमपरिवर्तन है। उदाहरण के लिए, {1 .. 4} के हार (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) । लंबाई के < एन के नो-डुप्लिकेट हार के साथ निपटने के लिए इस विधि को विस्तारित करने के लिए एन को पाठक के लिए एक अभ्यास के रूप में छोड़ दिया गया है।

लेकिन यदि आप असली हार ढूंढना चाहते हैं, जिसमें डुप्लिकेट तत्व हो सकते हैं, तो यह इतना आसान नहीं है।

Answer 3

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

(require srfi/43) 

(define (gennecklaces n alphabet) 
    (let* ([necklaces '()] 
     [alphavec (list->vector alphabet)] 
     [convert-necklace 
      (lambda (vec) 
      (map (lambda (x) (vector-ref alphavec x)) (cdr (vector->list vec))))] 
     [helper 
      (lambda (n k) 
      (let ([a (make-vector (+ n 1) 0)] 
        [i n]) 
       (set! necklaces (cons (convert-necklace a) necklaces)) 
       (let/ec done 
       (for ([X (in-naturals)]) 
        (vector-set! a i (add1 (vector-ref a i))) 
        (for ([j (in-range 1 (add1 (- n i)))]) 
        (vector-set! a (+ j i) 
           (vector-ref a j))) 
        (when (= 0 (modulo n i)) 
        (set! necklaces (cons (convert-necklace a) necklaces))) 
        (set! i n) 
        (let/ec done 
        (for ([X (in-naturals)]) 
         (unless (= (vector-ref a i) 
           (- k 1)) 
         (done)) 
         (set! i (- i 1)))) 
        (when (= i 0) 
        (done))))))]) 
    (helper n (length alphabet)) 
    necklaces)) 

Answer 4

पहली बार एक विचार के रूप में, आप स्पष्ट है, लेकिन अक्षम कर सकते हैंयदि वे तत्वों का सबसे छोटा घूर्णन (उपरोक्त पेपर में पी 5 पर औपचारिक परिभाषा) हैं। यह आपके द्वारा प्रस्तावित तरीके की तरह होगा, लेकिन जैसे ही वे उत्पन्न होते हैं, आप सभी गैर-हार को फेंक देंगे।

उसके अलावा, मुझे लगता है कि आप इस लेख (http://citeseer.ist.psu.edu/old/wang90new.html) को समझने के लिए करना होगा:

टी वांग और सी सैवेज, "पैदा करने हार के लिए एक नया एल्गोरिथ्म," रिपोर्ट TR-90-20 , कंप्यूटर साइंस विभाग, उत्तरी कैरोलिना स्टेट यूनिवर्सिटी (1 99 0)।

यह बहुत कठिन नहीं है, आप इसे tau और sigma कार्यों को कार्यान्वित करके और फिर लेख में उल्लिखित क्रम में लागू करने के द्वारा इसे तोड़ सकते हैं।