Итерации всех взаимно простых пар с использованием постоянного пространства?

я могу генерировать все пары копервичной, следуя алгоритм тройного дерева, перечисленные в Википедии: https://en.wikipedia.org/wiki/Coprime_integers Итерации всех взаимно простых пар с использованием постоянного пространства?

Быстро:

Start with two coprime branches: (2,1), (3,1), then iterate: 
Branch 1: (2m-n,m) 
Branch 2: (2m+n,m) 
Branch 3: (m+2n,n)

Однако пространство, используемое будет расти в три раза для каждой пары производства (и печатать, или иначе не хранить в памяти).

Здесь может быть решением в Haskell: Generating sorted list of all possible coprimes

Но я искал что-то в Python, который не имеет ленивые вычисления или бесконечные списки.

источник

2017-01-14 user318904

Просьба уточнить: Вам нужны те же ограничения, что и в проблеме Haskell? 'Первый элемент в каждой паре должен быть меньше второго. Сортировка должна выполняться в порядке возрастания - суммой парных элементов; и если две суммы равны, то по первому элементу пары. Если это так, вы хотите поменять эти пары в своем алгоритме. И у Python есть бесконечные генераторы, которые, вероятно, похожи на ваши «бесконечные списки». И пытаетесь ли вы избежать «роста в три раза» или вам просто нужен простой код Python? –

* «Но я искал что-то в python, у которого нет ленивых оценок или бесконечных списков». * Python имеет генераторы (которые дают значения лениво) и функции (особенно в 'itertools'), которые дают потенциально бесконечные последовательности. – Tagc

Я не искал ограничений от решения haskell, я должен был это сказать. И любое идиоматическое решение python будет работать независимо от ленивой/бесконечной терминологии. – user318904

Это использует логарифмическое пространство, может быть, это хорошо достаточно? И это линейное время (использует O (k) время для создания первых k пар).

def coprimes(): 
    yield (2, 1) 
    yield (3, 1) 
    for m, n in coprimes(): 
     yield (2*m - n, m) 
     yield (2*m + n, m) 
     yield (m + 2*n, n)

Вы можете прочитать больше о таких самостоятельных рекурсивных генераторах в этих статьях Дэвида Eppstein:

Demo показывая первые 20 пар:

>>> pairs = coprimes() 
>>> for _ in range(20): 
     print(next(pairs)) 

(2, 1) 
(3, 1) 
(3, 2) 
(5, 2) 
(4, 1) 
(5, 3) 
(7, 3) 
(5, 1) 
(4, 3) 
(8, 3) 
(7, 2) 
(8, 5) 
(12, 5) 
(9, 2) 
(7, 4) 
(9, 4) 
(6, 1) 
(7, 5) 
(13, 5) 
(11, 3)

Demo показывая миллиардной пара, которая берет мой компьютер около 4 минут, а использование памяти процесса Python остается на 9,5 MB базового уровне, что любой процесс Python берет меня по крайней мере.

>>> from itertools import islice 
>>> next(islice(coprimes(), 10**9-1, None)) 
(175577, 63087)

источник

2017-01-14 22:36:42

Это намного более элегантно и должно быть принято! Информационные ссылки тоже. – IVlad

Да, спасибо, это изящное решение, и я не знал, что вы можете сделать это с помощью итераторов. – user318904

Python версии принятого решения Haskell

def find_coprimes(): 
    l = 1 
    while True: 
     i = 2 
     while i < l-i: 
      if gcd(i, l-i) == 1: 
       yield i, l-i 
      i += 1 
     l += 1

Чтобы получить лишь некоторые из них:

iterator = find_coprimes() 
for i in range(10): 
    print(next(iterator))

Выход:

(2, 3) 
(2, 5) 
(3, 4) 
(3, 5) 
(2, 7) 
(4, 5) 
(3, 7) 
(2, 9) 
(3, 8) 
(4, 7)

источник

2017-01-14 20:57:37 IVlad

Итерации всех взаимно простых пар с использованием постоянного пространства?

ответ

Смежные вопросы