अपने प्रमुख कारकों को देखते हुए संख्याएं कैसे उत्पन्न करें, लेकिन अज्ञात घाटियों के साथ?

Question

संभावित डुप्लिकेट:
nth ugly number
Find the Kth least number for expression (2^x)*(3^y)*(5^z)

मैं कैसे एक तेजी से और सुरुचिपूर्ण तरीके से इस समस्या को हल करने की सोच रहा हूँ:

हम परिभाषित "बदसूरत" प्रत्येक नंबर n जिसे फ़ॉर्म में लिखा जा सकता है: 2^x * 3^y * 5^जेड ;, जहां एक्स, वाई और जेड प्राकृतिक संख्याएं हैं। 1500 वें बदसूरत नंबर खोजें।

जैसे पहले "बदसूरत" संख्या हैं:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... 

मैं जानवर बल का उपयोग कर इस समस्या को हल करने के लिए कोशिश की है इस तरह से,:

import itertools as it 

def is_ugly(n): 
    '''Return `True` if *n* is an ugly number.''' 

    if n == 1: 
     return True 
    while not n % 2: 
     n //= 2 
    while not n % 3: 
     n //= 3 
    while not n % 5: 
     n //= 5 
    return n == 1 

def nth_ugly(n): 
    '''Return the nth ugly number.''' 

    num = 0 
    for i in it.count(1): 
     if is_ugly(i): 
      num += 1 
      if num == n: 
       return i 

लेकिन यह काफी समय का एक बहुत लेता है, और मैं एक तेज़ और बेहतर समाधान ढूंढना पसंद है।

मैं बदसूरत संख्या के प्रधानमंत्री कारकों पता है, लेकिन मैं एक तरह से सही क्रम निम्नलिखित इन नंबरों उत्पन्न करने के लिए सोच भी नहीं सकते।

मुझे लगता है कि एक तरह से सभी नंबरों की जांच किए बिना इन नंबरों उत्पन्न करने के लिए होना चाहिए। समस्या यह है कि ऐसा लगता है कि प्रमुख कारकों के घाटे को काफी यादृच्छिक रूप से वितरित किया जाता है। इस तालिका में

देखो:

n |number| x | y | z | 
------------------------ 
1 | 1 | 0 | 0 | 0 | 
------------------------ 
2 | 2 | 1 | 0 | 0 | 
------------------------ 
3 | 3 | 0 | 1 | 0 | 
------------------------ 
4 | 4 | 2 | 0 | 0 | 
------------------------ 
5 | 5 | 0 | 0 | 1 | 
------------------------ 
6 | 6 | 1 | 1 | 0 | 
------------------------ 
7 | 8 | 3 | 0 | 0 | 
------------------------ 
8 | 9 | 0 | 2 | 0 | 
------------------------ 
9 | 10 | 1 | 0 | 1 | 
------------------------ 
10 | 12 | 2 | 1 | 0 | 
------------------------ 
11 | 15 | 0 | 1 | 1 | 
------------------------ 
12 | 16 | 4 | 0 | 0 | 
------------------------ 
13 | 18 | 1 | 2 | 0 | 
------------------------ 
14 | 20 | 2 | 0 | 1 | 
------------------------ 
15 | 24 | 3 | 1 | 0 | 
------------------------ 

आप देख सकते हैं एक्स, वाई और जेड मूल्यों किसी भी नियम का पालन करने के लिए नहीं है।

आप में से किसी को इस समस्या के लिए किसी भी समाधान मिल सकता है?

मैं विभिन्न भागों में समस्या को विभाजित करने की कोशिश कर के बारे में सोच रहा हूँ। चूंकि समस्या एक्सपोनेंट की यादृच्छिकता से निर्धारित होती है, इसलिए मैं स्वतंत्र रूप से 2s, 3s, 5s की शक्तियों और फिर 2^x * 3^y, 2^x * 5^z आदि की शक्तियों को उत्पन्न करने का प्रयास कर सकता हूं। और अंत में उन्हें एक साथ रखा, लेकिन मुझे नहीं पता कि यह मेरी समस्या का समाधान करेगा या नहीं।

Answer 1

यहां एक पूरा समाधान है। ओ (एन) जटिलता, यह एक बार और क्रम में हर नंबर उत्पन्न करता है।

# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF 

n = 15 
bases = [2, 3, 5] 

nums = [1] * n 
candidates_indexes = [0 for _ in bases] 
candidates = [base for base in bases] 

for i in range(1, n): 
    nextn = min(candidates) 
    nums[i] = nextn 

    for index, val in enumerate(candidates): 
     if val == nextn: 
      candidates_indexes[index] += 1 
      candidates[index] = bases[index] * nums[candidates_indexes[index]] 

print(nums) 

Answer 2

मैं तुम्हें संवर्द्धित इस को हल करने और सभी बदसूरत नंबर आप एक सूची में मिल स्टोर सुझाव देते हैं।

जब कुरूपता के लिए एक नंबर की जाँच तो, आप केवल कि क्या यह आपके नंबर बार 2, 3 या 5

संपादित में से एक है की जाँच करने के लिए है: मैं सिर्फ इतना है कि इस

ugly = [1] 
candidate = 2 
while len(ugly) < 1500: 
    for u in ugly: 
     if any([(u * x == candidate) for x in (2, 3 ,5)]): 
      ugly.append(candidate) 
      break 
    candidate += 1 

print ugly[-1] 

तरह लागू करने के लिए करने की कोशिश की

लेकिन यह दृष्टिकोण निराशाजनक रूप से स्थिर हो जाता है। बहुत भोली है। :) Eratosthenes के बजाय कुछ प्रकार की चाकू का उपयोग करें।

Answer 3

सभी मौजूदा बदसूरत संख्याओं को संग्रहीत करने के लिए एक सूची (निम्नलिखित कोड में एन) का उपयोग करें, अगली बदसूरत संख्या न्यूनतम संख्या (एन * 2, एन * 3, एन * 5) है जो तब बड़ी है [ -1]:

n = [1] 
while len(n) < 1500: 
    n.append(min([next(x*s for x in n if x*s>n[-1]) for s in (2,3,5)]))  
print n[-1] 

यह ओ (एन^2) समाधान है, इसलिए बड़ी संख्या में प्रयास न करें।

Answer 4

यहां एक ढेर का उपयोग करके एक समाधान है। विचार यह है कि हम बदसूरत उत्पाद के साथ घाटियों का ट्रैक रखते हैं। प्रत्येक पुनरावृत्ति के लिए, एल्गोरिदम 3 find_min संचालन और 3 सम्मिलित संचालन करता है, find_mins अनावश्यक हो सकता है क्योंकि आप किसी को किसी भी एक्सपोनेंट में जोड़कर प्रत्येक को प्राप्त कर सकते हैं, और तीन एक्सपोनेंट हैं। हम तीन बार एक सम्मिलित करते हैं क्योंकि हम प्रत्येक एक्सपोनेंट में एक जोड़ते हैं और ढेर में डाल देते हैं। Nth बदसूरत संख्या को खोजने के लिए, हमें इस प्रकार एन ऑपरेशंस करना है जो 6 * ओ (लॉग एन) हैं, इस प्रकार एल्गोरिदम में ओ (एन लॉग एन) की समय जटिलता है। ढेर स्वयं, क्योंकि यह केवल प्रत्येक पुनरावृत्ति के लिए निरंतर राशि से बढ़ सकता है, स्पेस (ओ (एन))

>>> import heapq, itertools 
>>> class UglyGen(object): 
...  def __init__(self, x, y, z): 
...   self.x, self.y, self.z = x, y, z 
...   self.value = 2**self.x * 3**self.y * 5**self.z 
...  def incr(self): 
...   x, y, z = self.x, self.y, self.z 
...   return (UglyGen(x+1, y, z), 
...     UglyGen(x, y+1, z), 
...     UglyGen(x, y, z+1)) 
...  def __lt__(self, other): 
...   if not isinstance(other, UglyGen): 
...    return NotImplemented 
...   return self.value < other.value 
... 
>>> def gen_ugly(): 
...  gens = [UglyGen(0, 0, 0)] 
...  last = 0 
...  while gens: 
...   while gens[0].value == last: 
...    heapq.heappop(gens) 
...   top = heapq.heappop(gens) 
...   succ_items = top.incr() 
...   for succ in succ_items: 
...    heapq.heappush(gens, succ) 
...   last = top.value 
...   yield last 
... 
>>> def find_nth_ugly(n): 
...  for n0, u in itertools.izip(xrange(n), gen_ugly()): 
...   pass 
...  return u 
... 
>>> find_nth_ugly(15) 
24