चक्रीय आवर्तन

Question

को छोड़कर सभी क्रमपरिवर्तन जनरेट कर रहा है तो मैं एक एल्गोरिथ्म की जरूरत है चक्रीय रोटेशन को छोड़कर नंबर की एक सूची के सभी क्रमपरिवर्तन (उत्पन्न करने के लिए जैसे [1,2,3] == [2,3,1] == [3,1,2])।

अनुक्रम में कम से कम 1 अद्वितीय संख्या होने पर यह काफी सीधे आगे है, उस अद्वितीय संख्या को निकालें, शेष संख्याओं के सभी क्रमपरिवर्तन उत्पन्न करें (लेकिन 'मानक' क्रमपरिवर्तन एल्गोरिदम में एक छोटे से संशोधन के साथ) और जोड़ें सामने के लिए अद्वितीय संख्या।

क्रमपरिवर्तन मैंने पाया है कि यह करने के लिए क्रमपरिवर्तन कोड बदलने के लिए आवश्यक है पैदा करने के लिए:

def permutations(done, options) 
    permuts = [] 
    seen = [] 
    for each o in options 
     if o not in seen 
      seen.add(o) 
      permuts += permutations(done+o, options.remove(o)) 
    return permuts 

केवल विकल्पों में से प्रत्येक अद्वितीय संख्या का उपयोग कर एक बार मतलब है कि आप 322 दो बार नहीं मिलता है।

इस एल्गोरिथ्म अभी भी रोटेशन आउटपुट जब कोई अद्वितीय तत्व, जैसे हैं [1,1,2,2] के लिए यह उत्पादन [1,1,2,2], [1,2,2,1] और [1,2,1,2] होगा और पहले दो चक्रीय घूर्णन होंगे।

तो वहाँ एक कुशल एल्गोरिथ्म है कि मुझे चक्रीय आवर्तन दूर करने के लिए बाद में के माध्यम से जाने के बिना सभी क्रमपरिवर्तन उत्पन्न करने के लिए अनुमति होगी है?

यदि नहीं, तो क्या चक्रीय रोटेशन को दूर करने के लिए सबसे कारगर तरीका हो सकता है?

नोट: इस नहीं अजगर उपयोग कर रहा है, बल्कि सी ++।

Answer 1

आपके द्वारा उत्पादित प्रत्येक क्रमिक परीक्षणों के परीक्षण के बारे में सोचें, जो चक्रीय रोटेशन की तलाश में है जो आपके पास पहले से "लीक्सिकली" है। यदि कोई है, तो इसे वापस न करें - यह कहीं और गिनती होगी।

कोई "अद्वितीय" पहला तत्व चुनना, यदि कोई मौजूद है, तो आपको अनुकूलित करने में सहायता करता है। आप जानते हैं कि क्या आप पहले तत्व को ठीक करते हैं, और यह अद्वितीय है, तो आप इसे रोटेशन के साथ डुप्लीकेट नहीं कर सकते हैं। दूसरी तरफ, यदि कोई ऐसा अनूठा तत्व नहीं है, तो बस कम से कम एक चुनें। इस तरह आपको केवल चक्रीय घूर्णन की जांच करने की आवश्यकता होती है जिसमें पहला तत्व होता है। (उदाहरण, जब आप उत्पन्न करते हैं [1,2,2,1] - आपको केवल [1,1,2,2] जांचना होगा, न कि [2,2,1,1] या [2,1,1,2 ])।

---

ठीक है, स्यूडोकोड ... स्पष्ट रूप से O (n!), और मैं वहाँ कोई बेहतर तरीका है आश्वस्त "अलग सभी प्रतीकों" हूँ, मामले के बाद से स्पष्ट रूप से वापस जाने के लिए है (n-1)! तत्वों।

// generate all permutations with count[0] 0's, count[1] 1's... 
def permutations(count[]) 
    if(count[] all zero) 
     return just the empty permutation; 
    else 
     perms = []; 
     for all i with count[i] not zero 
      r = permutations(copy of count[] with element i decreased); 
      perms += i prefixed on every element of r 
     return perms; 

// generate all noncyclic permutations with count[0] 0's, count[1] 1's... 
def noncyclic(count[]) 
    choose f to be the index with smallest count[f]; 
    perms = permutations(copy of count[] with element f decreased); 
    if (count[f] is 1) 
     return perms; 
    else 
     noncyclic = []; 
     for each perm in perms 
      val = perm as a value in base(count.length); 
      for each occurence of f in perm 
       test = perm rotated so that f is first 
       tval = test as a value in base(count.length); 
       if (tval < val) continue to next perm; 
      if not skipped add perm to noncyclic; 
     return noncyclic; 

// return all noncyclic perms of the given symbols 
def main(symbols[]) 
    dictionary = array of all distinct items in symbols; 
    count = array of counts, count[i] = count of dictionary[i] in symbols 
    nc = noncyclic(count); 
    return (elements of nc translated back to symbols with the dictionary) 

Answer 2

यह समाधान itertools.permutations उपयोग, set(), और कुछ अच्छा ol 'जमाने सेट अंतर का एक सा शामिल हो रहा है। ध्यान रखें, क्रमपरिवर्तन खोजने के लिए रनटाइम अभी भी ओ (एन!) होगा। मेरा समाधान इसे ऑनलाइन नहीं करेगा, लेकिन वहां एक और अधिक सुरुचिपूर्ण समाधान हो सकता है जो आपको ऐसा करने की अनुमति देता है (और इसमें itertools.permutations शामिल नहीं है)। इस उद्देश्य के लिए, यह कार्य पूरा करने का सीधा तरीका है।

चरण 1: दिए गए पहले तत्व का उपयोग करके चक्र उत्पन्न करने के लिए एल्गोरिदम। एक सूची के लिए [1, 1, 2, 2], यह हमें [1, 1, 2, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 2, 1, 1] देगा।

def rotations(li): 
    count = 0 
    while count < len(li): 
     yield tuple(li) 
     li = li[1:] + [li[0]] 
     count += 1 

चरण 2: आयात कर रहा है itertools.permutations हमें पहली जगह में क्रमपरिवर्तन देने के लिए है, तो एक set में अपने परिणामों की स्थापना।

from itertools import permutations 
perm = set(permutations([1, 1, 2, 2])) 

चरण 3: जनरेटर का उपयोग हमें अपने स्वयं के सेट चक्र के साथ (कुछ हम अपने आप से छुटकारा चाहते हैं) देने के लिए,।

cycles = set(((i for i in rotations([1, 1, 2, 2])))) 

चरण 4: प्रत्येक के लिए सेट अंतर लागू करें और चक्र निकाल दिए जाते हैं।

perm = perm.difference(cycles) 

उम्मीद है कि यह आपकी मदद करेगा। मैं सुझावों और/या सुधारों के लिए खुला हूं।

Answer 3

क्रमपरिवर्तन के मामले में जहां सभी संख्याएं अलग हैं, यह सरल है। मान लें कि संख्याएं 1,2,...,n हैं, फिर 1,2,...,n-1 के सभी क्रमपरिवर्तन उत्पन्न करें और आगे n चिपकाएं। यह पूर्ण सेट मॉड्यूलो चक्रीय घूर्णन के सभी क्रमपरिवर्तन देता है। उदाहरण के लिए, n=4 के साथ, आप

4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

करना होगा यह सुनिश्चित करता है कि 1,2,3,4 से प्रत्येक क्रमचय के कुछ चक्रीय रोटेशन ठीक एक बार सूची में है।

सामान्य मामले के लिए जहां आप एक मल्टीसेट (बार-बार प्रविष्टियों की अनुमति) के क्रमपरिवर्तन चाहते हैं, तो आप एक समान चाल का उपयोग कर सकते हैं। सबसे बड़े अक्षर n के सभी उदाहरणों को हटाएं (उपर्युक्त उदाहरण में 4 को अनदेखा करने के समान) और शेष मल्टीसेट के सभी क्रमपरिवर्तन उत्पन्न करें। अगला चरण n को कैननिकल तरीकों में क्रमिक क्रम में रखना है (उपरोक्त उदाहरण में शुरुआत में 4 डालने के समान)।

यह वास्तव में necklaces

Answer 4

पहले उत्पन्न करने के लिए मैं कंटेनर और एल्गोरिदम हम using हो जाएगा दिखाता हूँ सब Lyndon words पाने की सिर्फ एक मामला है:

#include <vector> 
#include <set> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 

using std::vector; 
using std::set; 
using std::sort; 
using std::next_permutation; 
using std::copy; 
using std::ostream_iterator; 
using std::cout; 

अगला हमारे vector का प्रतिनिधित्व करेंगी जो Permutation:

typedef vector<unsigned int> Permutation; 

हम wheth जाँच करने के लिए एक तुलना वस्तु की जरूरत है

struct CompareCyclicPermutationsEqual 
{ 
    bool operator()(const Permutation& lhs, const Permutation& rhs); 
}; 

और typedef एक set जो चक्रीय तुलना वस्तु का उपयोग करता है: एर एक क्रमचय एक रोटेशन है

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations; 

तो मुख्य कार्य काफी सरल है:

int main() 
{ 
    Permutation permutation = {1, 2, 1, 2}; 
    sort(permutation.begin(). permutation.end()); 

    Permutations permutations; 

    do { 
     permutations.insert(permutation); 
    } while(next_permutation(numbers.begin(), numbers.end())) 


    copy(permutations.begin(), permutations.end(), 
     ostream_iterator<Permutation>(cout, "\n"); 

    return 0; 
} 

आउटपुट:

1, 1, 2, 2, 
1, 2, 1, 2, 

मैंने अभी तक CompareCyclicPermutationsEqual लागू नहीं किया है। इसके अलावा आपको ostream& operator<<(ostream& os, const Permutation& permutation) को लागू करने की आवश्यकता होगी।