में भिन्न होती है, मैं ए के साथ लम्बाई के बाइनरी तारों के एल्गोरिदम उत्पन्न अनुक्रम के बारे में सोच रहा हूं, जहां अगली स्ट्रिंग दो अंकों में भिन्न होती है।के साथ बाइनरी स्ट्रिंग का अनुक्रम अनुक्रम जहां अगली स्ट्रिंग दो अंकों
उदाहरण के लिए:
11100
11010
11001
10101
10110
10011
00111
01011
01101
01110
11100
, सभी n \choose k द्विआधारी तार किया जाना चाहिए।
आपको अधिक पृष्ठभूमि प्राप्त करने के लिए इस तरह के क्रमपरिवर्तन (अन्य चीजों के साथ) my blog post पढ़ना चाहिए - और वहां कुछ लिंक का पालन करें।
यहाँ है के रूप में अनुरोध मेरी कोषगत क्रम-परिवर्तन का एक संस्करण Steinhaus-जॉनसन-ट्रोटर क्रमचय जनरेटर करता है की पीढ़ी अनुक्रम के बाद जमाने जनरेटर:
def l_perm3(items):
'Generator yielding Lexicographic permutations of a list of items'
if not items:
yield [[]]
else:
dir = 1
new_items = []
this = [items.pop()]
for item in l_perm(items):
lenitem = len(item)
try:
# Never insert 'this' above any other 'this' in the item
maxinsert = item.index(this[0])
except ValueError:
maxinsert = lenitem
if dir == 1:
# step down
for new_item in [item[:i] + this + item[i:]
for i in range(lenitem, -1, -1)
if i <= maxinsert]:
yield new_item
else:
# step up
for new_item in [item[:i] + this + item[i:]
for i in range(lenitem + 1)
if i <= maxinsert]:
yield new_item
dir *= -1
from math import factorial
def l_perm_length(items):
'''\
Returns the len of sequence of lexicographic perms of items.
Each item of items must itself be hashable'''
counts = [items.count(item) for item in set(items)]
ans = factorial(len(items))
for c in counts:
ans /= factorial(c)
return ans
if __name__ == '__main__':
n = [1, 1, 1, 0, 0]
print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
for i, x in enumerate(l_perm3(n[:])):
print('%3i %r' % (i, x))
assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'
उपरोक्त कार्यक्रम से उत्पादन उदाहरण के लिए निम्नलिखित है:
Lexicograpic Permutations of 5 items: [1, 1, 1, 0, 0]
0 [1, 1, 1, 0, 0]
1 [1, 1, 0, 1, 0]
2 [1, 0, 1, 1, 0]
3 [0, 1, 1, 1, 0]
4 [0, 1, 1, 0, 1]
5 [1, 0, 1, 0, 1]
6 [1, 1, 0, 0, 1]
7 [1, 0, 0, 1, 1]
8 [0, 1, 0, 1, 1]
9 [0, 0, 1, 1, 1]
यह है! बहुत धन्यवाद! – ushik
0 और 1 के बीच चक्र बनाएं।0000 1001 0011 1010 0110 1111 0101 1100
यह एन-बिट श्रृंखला के बिल्कुल आधा उत्पन्न होगा। यह सबसे अधिक है जिसे आप प्राप्त कर सकते हैं - दूसरा आधा उत्पन्न नहीं किया जा सकता है, उदाहरण के लिए, सभी 0 की स्ट्रिंग के साथ शुरू करना और एक समय में दो बिट्स बदलना, हमेशा 1 की संख्या भी होगी।
@Mooing: यह भी काम करेगा। हालांकि, मेरा संपादन देखें। –
यह वही नहीं है जो मैं चाहता था क्योंकि मुझे ** बिल्कुल के ** वाले तारों की आवश्यकता है। आपके उदाहरण में 0, 2, 2, 2, 2, 4, 2, 2 एक हैं ... – ushik
मुझे लगता है कि आप इसे रिकर्सन का उपयोग करके सेट अप कर सकते हैं।
मैं निम्नलिखित पहचान से प्रेरित था:
choose(n,k) = choose(n-1,k-1) + choose(n-1,k)
तो हम एक समारोह F (n, k) को परिभाषित है कि अनुरोध अनुक्रम का उत्पादन (यानी, वास्तव में कश्मीर बिट्स के साथ n लंबाई की बाइनरी तार का एक अनुक्रम सेट, जैसे कि लगातार तार दो बिट्स से भिन्न होते हैं)।
सबसे पहले, ध्यान दें कि हम किसी भी तरह से एफ (एन, के) के स्तंभों को फिर से व्यवस्थित कर सकते हैं और समान रूप से मान्य, एफ (एन, के) का उत्पादन कर सकते हैं।
ऊपर दी गई पहचान से पता चलता है कि हम एफ (एन -1, के -1) और एफ (एन -1, के) का उपयोग करके एफ (एन, के) का निर्माण करते हैं। एफ (एन -1, के -1) के कॉलम को पुन: व्यवस्थित करके तारों को प्राप्त करने दें ताकि अंतिम स्ट्रिंग के -1 1 1 एस में समाप्त हो जाए, फिर प्रत्येक को 1 जोड़ दें। बी को एफ (एन -1, के) के कॉलम को पुन: व्यवस्थित करके प्राप्त तारों को चलो, ताकि पहली स्ट्रिंग के 1 एस में समाप्त हो जाए, फिर प्रत्येक को 0 जोड़ दें। फिर एफ (एन, के) सिर्फ ए और बी का समापन है। परिणाम एक वैध एफ (एन, के) है, ए और बी के आंतरिक के रूप में तार दो बिट्स से भिन्न होता है, और ए और पहले की अंतिम स्ट्रिंग बी की स्ट्रिंग दो बिट्स (के + 1 वें से अंतिम बिट और अंतिम बिट) से भिन्न होती है।
मैं एन = 5, के = 2 का उपयोग करके एक उदाहरण दिखाऊंगा। हम निम्नलिखित दो एफ दृश्यों प्रत्यावर्तन द्वारा प्राप्त करें:
F(4,1): 0001
0010
0100
1000
F(4,2): 0011
0101
1001
1010
0110
1100
एक बनाने के लिए, एफ (4,1) के पहले और अंतिम स्तंभ स्वैप और प्रत्येक के लिए 1 जोड़ें:
A: 10001
00101
01001
00011
बनाने के लिए बी , कोई स्तंभ स्वैप जरूरी हैं, इसलिए हम बिल्कुल एफ की प्रत्येक पंक्ति (4,2) के लिए एक 0 जोड़ें:
B: 00110
01010
10010
10100
01100
11000
तो एफ (5,2) सिर्फ ए और बी के संयोजन है
यदि यह होमवर्क है, तो तदनुसार टैग करें। और एन \ select k द्वारा आपका क्या मतलब है? – Rndm
@shg नहीं, यह होमवर्क नहीं है। ;) और n \ select k से मेरा मतलब है के-संयोजन (बिनोमियल गुणांक) की संख्या। – ushik