Генератор натурального ряда

Учебная задача на знание языка и не только:

g = (...)

for n in g:
    print(n)
    if n > 20:
        break

На первой строке выражение-генератор. Генератор должен бесконечно производить натуральные числа: 1, 2, 3, …. Три задачки в порядке увеличения сложности:

  1. Написать выражение-генератор с использованием стандартной библиотеки. Можно импортировать стандартные модули.
  2. То же, без импортов.
  3. То же, без импортов и глобальных функций и объектов.

P.S. Подразумеваю, что в третьем пункте нет импортов, не вызываются встроенные функции, нет обращений ко встроенным объектам, не определяются именованные функции или объекты.


Ответы (8 шт):

Автор решения: mrgervant

2 вариант задачи:

g = (i for i, _ in enumerate(iter(int, 1), 1))

Через (iter(int, 1)) получаем вечный итератор, который возвращает нули.

А с enumerate() получаем возрастающие натуральные числа, но без необходимости создавать переменную для счетчика итераций.

Не забываем указать параметр start = 1, чтобы начать enumerate() с 1, а не 0.

P.S.: бесконечно 0 можно получать и иначе:

g = (i for i, _ in enumerate(iter(lambda: 0, 1), 1))
→ Ссылка
Автор решения: CrazyElf

Можно сделать простой, но условно-бесконечный цикл. Вряд ли кто-то возьмётся его перебирать до конца:

g = range(1, 10**1_000_000)
→ Ссылка
Автор решения: Serge3leo

Формулировка п. 3, лично мне, немного не понятна, ну вот вариант без рабочих глобальных функций и объектов.

def test():
    def numbersN():
        n = 1
        while True:
            yield n
            yield n + 1
            yield n + 2
            yield n + 3
            yield n + 4
            yield n + 5
            yield n + 6
            yield n + 7
            yield n + 8
            yield n + 9
            n += 10

    def test(g, n):
        for i in g:
            if i > n:
                break
        return i

    print(test(numbersN(), 10))
    nn = 1000_000
    %timeit test(numbersN(), nn)

test()

Конечно, проигрывает range(1, 10**18) процентов ≈50%, зато длинный и формально честный. Или нет? Кто знает?

→ Ссылка
Автор решения: mrgervant

Вариант решения через type():

g = type(
    "NaturalNumbers",
    (),
    {
        '__iter__': lambda x: x,
        '__next__': lambda x: setattr(x, 'counter', x.counter + 1) or x.counter,
        'counter': 0
    }
)()

Вышеуказанный код "сворачивается" и в одну строку:

g = type("NaturalNumbers", (), {'__iter__': lambda x: x, '__next__': lambda x: setattr(x, 'counter', x.counter + 1) or x.counter, 'counter': 0})()

Функция type() позволяет не только проверять тип объекта, но и создавать новые типы. Для этого передаем:

  • название создаваемого типа;
  • кортеж с родительскими классами (в нашем случае ничего);
  • словарь с именами, которые передадутся в __dict__ - для нас это значит, что можно задать магические методы __iter__ и __next__, а также создать переменную counter.

В iter просто определяем, чтобы возвращался объект итератора, а в counter задаем и храним переменную для счетчика натуральных чисел.

Вся магия в next:

  • при каждой итерации будет вызываться lambda-функция, которая выполняет or;
  • сначала значение counter прибавит 1 через setattr - с её помощью обходим проблемы с использованием присваивания через =;
  • из setattr возвращается None и функция переходит ко второй части or - просто возврату текущего значения counter.

Не забываем в конце добавить () для получения экземпляра свежеопределенного типа.

Можно использовать как указано, так и передать для создания выражения-генератора:

g = (i for i in type("NaturalNumbers"...)())
→ Ссылка
Автор решения: Stanislav Volodarskiy

1.

Первый вариант, с импортами, самый простой. Наружные скобки в определении g не нужны, оставлены только для формального соответствия условию. itertools.count умеет считать натуральные числа без остановки:

import itertools

g = (itertools.count(1))

2.

Второй вариант я утащу из ответа mrgervant. Поставьте ему плюсик.

g = (i for i, _ in enumerate(iter(int, 1), start=1))

iter создаёт бесконечный генератор из нулей, enumerate превращает его в последовательность натуральных чисел.

И это, кажется, единственный вариант решить задачу. Но неугомонный mrgervant предложил решение на основе type, который позволяет собрать объект-итератор.

3.

Лямбда в Питоне позволяет использовать выражения (yield ...), (yield from ...). При этом лямбда из обычной функции превращается в генератор. Выражение для g совмещает Y-комбинатор с рекурсивной лямбдой-генератором:

g = (lambda f, n: f(f, n))(lambda f, n: ((yield n), (yield from f(f, n + 1))), 1)

Читать это невозможно. Разберём на составляющие:

y = lambda f, n: f(f, n)
f = lambda f, n: ((yield n), (yield from f(f, n + 1)))
g = y(f, 1)

Если убрать комбинатор, получится:

f = lambda n: ((yield n), (yield from f(n + 1)))
g = f(1)

Но в этом варианте нужен глобальный символ f, чтобы сделать рекурсивный вызов. А в выражении с комбинатором он не нужен.

3.1.

Предыдущий вариант решает задачу, но глубина рекурсии ограничивает длину "бесконечного" генератора примерно тысячью элементов. Это просто смешно! Заменим линейную рекурсию на древовидную. Добавится ещё один комбинатор.

Этим кодом можно испугать любого, зато для глубины стека в одну тысячу вызовов он способен произвести 2499 - 1 натуральных чисел.

g = (lambda f, n, d: f(f, n, d))(
    lambda f, n, d: ((
        yield from (lambda h, n, d: h(h, n, d))(
            lambda h, n, d: (yield n) if d == 0 else ((yield from h(h, n, d - 1)), (yield from h(h, n + 2 ** (d - 1), d - 1))),
            n,
            d
        )
    ), (
        yield from f(f, n + 2 ** d, d + 1)
    )),
    1,
    0
)

P.S. Последние два варианта не используют никаких встроенных или глобальных символов, только ключевые слова lambda, yield, from, if, else. Вопрос со звёздочкой: можно ли решить задачу без from, if, else?

P.P.S. Когда я задавал вопрос, я думал что у последнего пункта нет решения. И даже придумал доказательство этого факта. Но я вам его не покажу. :)

→ Ссылка
Автор решения: Danis

Получилась следующая махина:

a=(lambda:0).__class__((lambda:0).__code__.__class__(0, 0, 0, 1, 2, 35, b'K\x00\x01\x00\x97\x00d\x01}\x00\t\x00|\x00\x96\x01\x97\x01\x01\x00|\x00d\x01z\r\x00\x00}\x00\x8c\n\xad\x03w\x01', (1, 1), (), ('i',), '', '', '', 140, b'\xe8\x00\xf8\x80\x00\xd8\x08\t\x80A\xd8\n\x0e\xd8\x0e\x0f\x8a\x07\xd8\x08\t\x88Q\x89\x06\x88\x01\xf0\x05\x00\x0b\x0f\xf9', b'\x82\x0e\x10\x01', (), ()),{},"")()
for i in a:
    print(i)

Запускал на Python 3.12.5, на других не факт, что будет работать.

Фактически, это нечто вида:

def f():
    i = 1
    while True:
        yield i
        i += 1

code = type(function.__code__)(*Данные функции f*)
a = function(code)()
→ Ссылка
Автор решения: Fox Fox
from itertools import count
g = count(1)
g = (x + 1 for x in range(10**100))
g = (lambda f: f(f))(lambda f: (n := [0]) and iter(lambda: (n.__setitem__(0, n[0]+1), n[0])[1], None))
for n in g:
 print(n)
 if n > 20: break

3.1)

g = (lambda f: f(f))(lambda f: (n := [0]) and (lambda: (n.__setitem__(0, n[0]+1), n[0])[1]))
i = 0
while True:
 i += 1
 print(g())
 if i >= 21: break
→ Ссылка
Автор решения: Serge3leo

Последние два варианта не используют никаких встроенных или глобальных символов, только ключевые слова lambda, yield, from, if, else. Вопрос со звёздочкой: можно ли решить задачу без from, if, else?

Строго говоря, достаточно одного ключевого слова - lambda. Оно достаточно мощное, что бы многие предложенные варианты свести только к нему одному (хотя для некоторых, нужны for и in).

def test_StanislavVolodarskiy_1():
    return (lambda:0).__globals__['__builtins__'].__import__(
           'itertools').count(1)
def test_mrgervant_1():
    return (i for i, _ in
              (lambda:0).__globals__['__builtins__'].enumerate(
                  (lambda:0).__globals__['__builtins__'].iter(
                      int, 1), 1))
mrgervant_2 = (lambda:0).__globals__['__builtins__'].type(
    "NaturalNumbers",
    (),
    {
        '__iter__': lambda x: x,
        '__next__': lambda x: (x.__setattr__('counter', x.counter + 1)
                               or x.counter),
        'counter': 0
    }
)
def test_CrazyElf():
    return (lambda:0).__globals__['__builtins__'].range(1, 2**63 - 1)
def test_FoxFox_3():
    return (lambda f: f(f))(
            lambda f: (n := [0]) and
                      (lambda:0).__globals__['__builtins__'].iter(
                          lambda: (n.__setitem__(0, n[0]+1), n[0])[1],
                          None
                      )
        )

def test_gen(g, n):
    j = 1
    for i in g:
        assert i == j, f"{i, j=}"
        if i > n:
            return True
        j += 1
    assert False
for nn in [1, 100, 10_000]:
    assert test_gen(test_StanislavVolodarskiy_1(), nn)
    assert test_gen(test_mrgervant_1(), nn)
    assert test_gen(mrgervant_2(), nn)
    assert test_gen(test_CrazyElf(), nn)
    assert test_gen(test_FoxFox_3(), nn)
    print(f"{nn} - Хорь")

def test_bench(g, n):
    for i in g:
        if i > n:
            return True
    assert False
nn = 1_000_000
%timeit test_bench(test_StanislavVolodarskiy_1(), nn)
%timeit test_bench(test_mrgervant_1(), nn)
%timeit test_bench(mrgervant_2(), nn)
%timeit test_bench(test_CrazyElf(), nn)
%timeit test_bench(test_FoxFox_3(), nn)
print("Хорь")
1 - Хорь
100 - Хорь
10000 - Хорь
29.6 ms ± 936 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
65.2 ms ± 2.26 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
222 ms ± 13.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
29.2 ms ± 225 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
202 ms ± 8.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Хорь
→ Ссылка