मैं योजना में पुनरावृत्ति के साथ कुछ आकार के सभी क्रमपरिवर्तन कैसे उत्पन्न करूं?

Question

मैं योजना सीख रहा हूं और मैं कुछ आकार की पुनरावृत्ति के साथ क्रमपरिवर्तन उत्पन्न करने की कोशिश कर रहा हूं।

उदाहरण के लिए, दिया गया n = 4 और सेट एस = {ए, बी, सी, डी, ई, एफ}, मैं सभी संभावित क्रमपरिवर्तन उत्पन्न करना चाहता हूं: {a, a, a, a}, { एक, एक, a, b}, ..., {एक, एक, एक, च} {एक, क, ख, एक} {एक, ए, बी, b}, ..., {एक, ए, बी, एफ} ... {च, एक, एक, एक} {च, एक, a, b} ..., {च, एक, एक, च} ... {च, च , एफ, च}।

समस्या यह है कि मैं समझ नहीं पा रहा हूं कि '4' कैसे चुनें, और याद रखें कि मैंने इसे 4 बार चुना है, फिर 'ए' 3 बार, और 'बी' एक बार चुनें, और सभी को याद रखें यह, तो मैं इसे फिर से नहीं चुनता।

मुझे पता है कि इस तरह की समस्याओं को रिकर्सिव एल्गोरिदम के साथ सबसे अच्छा हल किया जाता है, लेकिन यह सब कुछ और जटिल बना देता है, जैसे कि मुझे रिकर्सन में कैसे याद है, मैंने कौन से तत्व उठाए हैं।

मुझे नहीं पता कि इस समस्या से कैसे संपर्क करें। अगर कोई इस समस्या को हल करने की विचार प्रक्रिया को लिखता है तो मुझे बहुत खुशी होगी। मैं इसकी बहुत सराहना करता हूं!

कृपया मेरी मदद करें।

धन्यवाद, बोडा साइडो।

Answer 1

प्रक्रिया के इंटरफ़ेस और अपेक्षित परिणामों से शुरू करना अच्छा है। आपकी प्रक्रिया को (permutations size elements) कहा जा रहा है और यह ELEMENTS में आइटमों के क्रमपरिवर्तन की एक सूची वापस करने की उम्मीद है, प्रत्येक क्रमपरिवर्तन SIZE आइटम लंबा है। चित्र आप एक सूची के रूप में "क्रमपरिवर्तन" का प्रतिनिधित्व करने जा रहे हैं। इसलिए यदि आपने (permutations 1 '(a b c)) कहा है तो आप ((a) (b) (c)) के आउटपुट की अपेक्षा करेंगे।

तो रिकर्सिव प्रक्रियाओं के बारे में चाल, क्या आपको यह पता लगाना होगा कि मूल स्थिति क्या है कि आप आसानी से जवाब दे सकते हैं, और एक सरल समस्या के समाधान को संशोधित करके आप रिकर्सिव चरण का उत्तर दे सकते हैं। PERMUTATIONS के लिए, रिकर्सिव चरण को घटते हुए SIZE को शामिल करने जा रहा है, इसलिए आधार चरण 0 होने पर आधार चरण होने वाला है, और उत्तर शून्य-लंबाई क्रमपरिवर्तन की एक सूची है, i। ई। (())।

रिकर्सिव चरण का उत्तर देने के लिए, आपको आकार एन के परिणाम प्राप्त करने के लिए आकार एन -1 के परिणाम के साथ क्या करना है, यह पता लगाने के लिए, यह छोटे एन के लिए कुछ अपेक्षित परिणाम लिखने में मदद कर सकता है और देखते हैं कि आप एक पैटर्न विचार कर सकते हैं यदि:

 
ELEMENTS = (a b) 
SIZE (PERMUTATIONS SIZE ELEMENTS) 
0  (()) 
1  ((a) (b)) 
2  ((a a) (a b) (b a) (b b)) 
3  ((a a a) (a a b) (a b a) (a b b) (b a a) ...) 

तो मूल रूप से क्या आप तत्वों में प्रत्येक तत्व E के लिए क्या करना है, यह देखते हुए आर = (permutations n elements), आप (permutations (+ n 1) elements) आर में एक क्रमचय पी लेने के द्वारा प्राप्त कर सकते हैं, और फिर चाहते हैं

, एक नया क्रमपरिवर्तन बनाने के लिए ई से पी को आसन्न करें, और उनकी एक सूची एकत्र करें। मैं बाहरी मानचित्रण के लिए FLATMAP उपयोग कर रहा हूँ, क्योंकि भीतरी एमएपी नई क्रमपरिवर्तन की सूची बनाता है

 
(define (permutations size elements) 
    (if (zero? size) 
     '(()) 
     (flatmap (lambda (p)   ; For each permutation we already have: 
       (map (lambda (e)  ; For each element in the set: 
         (cons e p)) ;  Add the element to the perm'n. 
         elements)) 
       (permutations (- size 1) elements)))) 

, और हम एक बड़ा फ्लैट बनाने के लिए एक साथ उन सूचियों संलग्न करने के लिए है: और हम नेस्टेड नक्शे के साथ ऐसा कर सकते हैं हम चाहते हैं कि क्रमिक क्रम की सूची।

बेशक, यह सब आपको लगता है कि आप जानते हैं और एमएपी जैसे अनुक्रम संचालन पर एक अच्छा संभाल है। यदि आपको ऐसा नहीं लगता है कि मैंने एक सुरुचिपूर्ण समाधान के साथ आना मुश्किल होगा जैसा मैंने अभी किया था।

Answer 2

संकेत: आप अन्य रिकर्सिव कॉल किए गए "याद रखने" के लिए एक रिकर्सिव कॉल पर पैरामीटर का उपयोग कर सकते हैं। ;)

Answer 3

यहां एक और संस्करण है: मैंने फ्लैटमैप को कम किया, कम किया। मैंने इसे MIT-scheme में लिखा था।

(define (per s) 

    (define (ins c before after) 
    (if (null? after) 
     (list (append before (list c))) 
     (append (list (append before (list c) after)) 
       (ins c 
        (append before (list (car after))) 
        (cdr after))))) 
    (define (iter l) 
    (cond ((null? l) 
      '(())) 
      (else 
      (let ((rest (iter (cdr l)))) 
      (reduce-left append 
         () 
          (map (lambda (x) (ins (car l)() x)) 
           rest)))))) 
    (iter s)) 

(per '(1 3 2 4))