Как максимально эффективно сгенерировать все приведенные дроби, равные N/D с 0<=N<=D для некоторого фиксированного D? ⇐ Python

[Anonymous]

Это не домашнее задание или работа. Я безработный, бросил среднюю школу в 2017 году, мне сейчас 26 лет, я пишу программы исключительно для развлечения и полностью изучил программирование самостоятельно из личного интереса.
Задача проста: учитывая фиксированный знаменатель, найти все дроби с заданными знаменателем и числителем в диапазоне от 0 до знаменателя и сократить их. Выходными данными должен быть список всех таких уменьшенных дробей, каждая дробь должна быть представлена как кортеж целых чисел с двумя элементами, и задача должна быть выполнена БЕЗ ИСПОЛЬЗОВАНИЯ НОД.
Я уже написал решение без использования НОД, совершенно самостоятельно, оно очень сложное и умное, и имеет лучшую временную сложность, чем наивный метод НОД, но медленнее для небольших входных данных.
Во-первых, наивный метод, он идеально описывает то, что я собираюсь сделать, и результат любого умного метода должен соответствовать результату наивного метода. Таким образом, наивный метод:

Код: Выделить всё

import math

def primitive_rationals_stupid(denominator: int) -> list[tuple[int, int]]:
assert isinstance(denominator, int) and denominator > 0
return (
[(0, 1)]
+ [
(n // (common := math.gcd(n, denominator)), denominator // common)
for n in range(1, denominator)
]
+ [(1, 1)]
)

Наивный метод быстр для небольших входных данных, но имеет высокую временную сложность. И это быстро только потому, что math.gcd реализован на C.
Для сравнения я реализовал версию с использованием двоичного евклидова НОД, реализованную на Python:

Код: Выделить всё

def gcd(a: int, b: int) -> int:
if not a or not b:
return a or b

t1 = (a & -a).bit_length() - 1
t2 = (b & -b).bit_length() - 1
a >>= t1
b >>= t2
k = t2 ^ ((t1 ^ t2) & -(t1 < t2))
while b:
c = a + b
a = b ^ ((a ^ b) & -(a < b))
b = c - a - a
b >>= ((b & -b).bit_length() or 1) - 1

return a  list[tuple[int, int]]:
assert isinstance(denominator, int) and denominator > 0
return (
[(0, 1)]
+ [
(n // (common := gcd(n, denominator)), denominator // common)
for n in range(1, denominator)
]
+ [(1, 1)]
)

Как мне удалось это сделать без использования GCD? Ну, во-первых, дробь уменьшается, если числитель и знаменатель взаимно простые, другими словами, у них нет общих простых делителей. Если числитель и знаменатель взаимно простые, то дробь сокращается.
Теперь запишите число N в виде произведения простых чисел, это называется его факторизацией простых чисел. Если простое число P1 является делителем N, то P1/N не уменьшается, а приведенная дробь равна 1/(N/P1). Теперь, если N=P1*P2, то 1/P2 = 1/(N/P1), и с небольшими выводами мы можем видеть, что все дроби, заданные следующим образом: [(i, P) для i в диапазоне (1, P)] являются подмножеством [(i, N) для i в диапазоне (N+1)], если P является простым делителем N, и они гарантированно уменьшаются.
N/P дает комбинация простых делителей N, если N составное. И наоборот, каждая дробь с числителем от 0 до N/P и знаменателем, равным N/P, содержится в исходном наборе. 1 взаимно просто с каждым целым числом, поэтому 1/D гарантированно сокращается.
Таким образом, у нас есть рекурсивное отношение, и задача состоит в том, чтобы найти все пары (n, d), где 1 = exp

for i in (3, 5, 7, 11):
div, mod = divmod(n, i)
if not mod:
exp, n = exp_factor(i, div)
factors = exp + 1

i = 0
k = 13
root = math.isqrt(n) + 1
while k previous else stack.remove(element)
result.append(stack.copy())
previous = gray_code

return result
[/code]
Вышеупомянутый метод максимально эффективен, но у него есть две проблемы: не сортируется каждое подмножество, не сортируется и набор мощности, а уникальность элементов не гарантируется. Вы сразу поймете, почему это проблемы.
И фиксированный код:

Код: Выделить всё

def bisect(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mi = lo + hi >> 1
if arr[mi] < x:
lo = mi + 1
else:
hi = mi

return lo

def powerset_sorted(series):
total = 1 > 1)
element = series[(gray_code ^ previous).bit_length() - 1]
if gray_code > previous:
stack.insert(bisect(stack, element), element)
else:
stack.remove(element)

result.append(tuple(stack))
previous = gray_code

return sorted(set(result))

Что теперь? Если N/D является рациональным числом, D > 0, 0 0
return (
[(0, 1)]
+ [
(i >> (tail := (i & -i).bit_length() - 1), 1 0 and n > 1
stack = [0] * exp
total = n**exp
last = exp - 1
result = []
for _ in range(total):
result.append(stack.copy())
i = last
carry = 1
while carry:
digit = stack
digit += 1
stack = (digit, 0)[carry := digit == n]
i -= 1

return result

def primitive_power_rationals(n: int, exp: int) -> list[tuple[int, int]]:
assert isinstance(exp, int) and isinstance(n, int) and exp > 0 and n > 1
power = 1
powers = [1] + [(power := power * n) for _ in range(exp)]
last = exp - 1
numerals = base_n_counting(n, exp)
numerals.pop(0)
result = [(0, 1)]
for n, numeral in enumerate(numerals, start=1):
i = last
tail = 0
while i >= 0 and not numeral:
tail += 1
i -= 1

result.append((n // powers[tail], powers[exp - tail]))

result.append((1, 1))
return result
[/code]
А затем, постепенно становясь ситом и сохраняя предыдущие сита в словаре, обрабатывая набор степеней множителей и находя все взаимно простые числа текущего произведения множителей, не превышающие произведение, используя метод, который я только что описал, я реализовал очень умный способ генерировать все нужные мне сокращенные дроби:

Код: Выделить всё

BASE_CASES = [
[(0, 1), (1, 1)],
[(0, 1), (1, 2), (1, 1)],
[(0, 1), (1, 3), (2, 3), (1, 1)],
]

def primitive_rationals(denominator: int) -> list[tuple[int, int]]:
assert isinstance(denominator, int) and denominator > 0
if denominator 

Подробнее здесь: [url]https://stackoverflow.com/questions/79886724/how-to-generate-all-reduced-fractions-equal-to-n-d-with-0-n-d-for-some-fixed-d[/url]