spis wszystkich produktów zawierających czynnik mniej niż maksymalna

Question

chcę wyliczać wszystkie możliwe produkty niektórych czynników całkowitymi, tylko do pewnej wartości maksymalnej:

• P((2, 3, 11), 10) wróci (2, 3, 4, 6, 8, 9).
• P((5, 7, 13), 30) zwróci (5, 7, 13, 25).

Wydaje się, że to drzewo, gdzie gałęzie przestają rosnąć, gdy osiągają maksimum, ale nie wiem, co to jest granica liczby gałęzi. Jaki algorytm lub idiom jest zalecany dla tego problemu? najbliższą rzeczą, jaką widziałem do tej pory, jest itertools.product(), która wydaje się ustawiać ustaloną liczbę warunków na zestaw wyników (np. 2).

Dla kontekstu, próbuję sprawdzić liczby, które są coprime do n. w tym przypadku n jest górną granicą, a lista czynników to n. Próbowałem uogólnić pytanie nieco wyżej.

Answer 1

Podoba mi się ta metoda, która polega na pomnożeniu 1 przez wszystkie elementy na liście wejściowej, a następnie pomnożenie wszystkich wyników przez elementy na liście wejściowej itp., Aż do osiągnięcia limitu.

def signature_seq(signature, limit): 
    products = set((1,)) 
    for factor in signature: 
    new_products = set() 
    for prod in products: 
     x = factor * prod 
     while x <= limit: 
     new_products.add(x) 
     x *= factor 
    products.update(new_products) 

    products.remove(1) 
    return products 

ten powinien robić to, co chcesz:

>>> print(sorted(signature_seq((2, 3, 11), 10))) 
[2, 3, 4, 6, 8, 9] 
>>> print(sorted(signature_seq((5, 7, 13), 30))) 
[5, 7, 13, 25] 

Nawiasem mówiąc, jeśli podano listę kolejnych liczb pierwszych zaczynających się od 2, to jest generator smooth number.

Answer 2

Oto rozwiązanie przy użyciu generatora (a itertools.count):

from itertools import count 

def products(numbers, limit): 
    numbers = set(numbers) # needs a set to pop from, not a tuple 
    while numbers: 
     n = numbers.pop() 
     for r in (n ** e for e in count(1)): 
      if r > limit: 
       break 
      yield r 
      for p in products(numbers, limit/r): 
       yield r * p 

ponieważ jest to generator, zwraca iterator - a wyniki nie są sortowane, więc dla konkretnego wyjścia chcesz, „d nazwać tak:

>>> sorted(products((2, 3, 11), 10)) 
[2, 3, 4, 6, 8, 9] 
>>> sorted(products((5, 7, 13), 30)) 
[5, 7, 13, 25] 

Answer 3

na pomysł, aby używać tylko itertools z krotki (2,3,4), na przykład:

mieć wiele iloczyn kartezjański:

(2,),(3,),(4,) # repeat 1 
(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4) # repeat 2 
... 

Dla każdego z tym krotki użyć reduce z operator.mul i wartość początkowa 1 pomnożyć je:

reduce(operator.mul, tuple, 1) 

to, otrzymując mnożenia dla produktu, poziom 2 kartezjańskie w:

[reduce(operator.mul,t,3) for t in itertools.product((1,2,3),repeat=2)] 
>>>[3, 6, 9, 6, 12, 18, 9, 18, 27] 

Teraz musimy zwiększyć repeat aż do spełnienia warunku zatrzymania, na przykład: każde mnożenie przyniesie wynik większy niż top. Ponieważ wartość samlesta, która się liczy, to 2 (ponieważ 1 razy 1 wiele razy jest tylko 1, więc nie będzie liczyć) możemy pomnożyć 2 razy x, podczas gdy jest niższa niż top.Więc: top/2 = x oznacza, że ​​możemy iterację range(1,top/2):

[reduce(operator.mul,t,1) for c in range(1,10/2) for t in itertools.product((1,2,3),repeat=2) if reduce(operator.mul, t, 1) < 10] 

To przynoszące powtarzające się wartości, więc niech przekształcić je w zestawie:

set([reduce(operator.mul,t,1) for c in range(1,10/2) for t in itertools.product((1,2,3),repeat=2) if reduce(operator.mul, t, 1) < 10]) 

Korzystanie tylko itertools może być kłopotliwe dla tego, ale rozwiązanie wydaje się ładne. Jestem pewien, że można go zoptymalizować, wprowadzając lepszy warunek zatrzymania. Ostateczny kod będzie wyglądać następująco:

UWAGA: Istnieje twierdzenie o liczbach pierwszych, które pozwalają zoptymalizować stan zatrzymania do math.sqrt(top)

import math 
def f(t,m): 
    return set([reduce(operator.mul, t1, 1) for c in range(1,int(math.sqrt(m)) for t1 in itertools.product(t,repeat=c) if reduce(operator.mul,t1,1) < m]) 

f((2,3,4),10) 
>>>set([2, 3, 4, 6, 8, 9]) 

Nadziei to może dać inny pomysł :)