В предыдущей статье («Случай итератора 1: zip», использовал стандартную библиотеку Python itertools, в этой статье мы продолжим изучение нескольких интересных функций в этой стандартной библиотеке, чтобы понять применение итераторов.
Комбинация и расположение
«Комбинация» и «расстановка» в математике, если они реализованы программно, с использованием функций модуля itertools в Python очень просты и практичны. Попросту говоря, задача перестановок и комбинаций бессмысленна, можно посмотреть на классическую задачу.
тема: Допустим, есть несколько юаней: 3 штуки по 20 юаней, 5 штук по 10 юаней, 2 штуки по 5 юаней, 5 штук по 1 юаню. В: Как объединить, чтобы получить 100 юаней.
Во-первых, вы можете использовать список для представления известных юаней.
rmb = [20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1]
Задача сейчас — это задача на комбинации, например, можно думать об этом так: сначала найди кусок из 20, а потом пробуй по одному, возможны и другие комбинации, пока сумма не станет 100. В результате получается комбинация.
Itertools в стандартной библиотеке Python предоставляет нам такую функцию для достижения этой комбинации.
>>> import itertools
>>> com = itertools.combinations([1,2,3], 2)
>>> list(com)
[(1, 2), (1, 3), (2, 3)]
itertools.combinations([1,2,3], 2)Первый параметр — это объект, который нужно объединить, а второй параметр — это количество элементов в объединенном результате. Если эта функция используется дляrmbЭтот список является результатом этого:
>>> list(itertools.combinations(rmb, 3))
[(20, 20, 20), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 5), (20, 20, 5), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 5), (20, 20, 5), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 5, 5), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 5), (20, 20, 5), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 5, 5), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 5, 5), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (10, 10, 10), (10, 10, 10), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 10), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 10, 10), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (5, 5, 1), (5, 5, 1), (5, 5, 1), (5, 5, 1), (5, 5, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]
Затем из этих комбинаций выбираются те, которые могут удовлетворять определенным условиям, что и является решением данной задачи. Однако приведенное выше является лишь примером объединения 3 элементов. На самом деле он может начинаться с 1 и доходить до длины списка юаней. Конечно, сразу видно, что получается только 1 или 2, какая бы комбинация ни была, до 100 не дойдет. Другими словами, с точки зрения нашего анализа, наименьшая возможная комбинация должна быть (20, 20, 20, 10, 10, 10, 10), то есть для получения 100 юаней необходимо объединить как минимум 7 банкнот.
>>> makes_100 = []
>>> for n in range(7, len(rmb)+1):
... for comb in itertools.combinations(rmb, n):
... if sum(comb) == 100:
... makes_100.append(comb)
...
Отметим, что в это времяmakes_100, а не окончательный результат. Потому что в нем много повторений, причина этого в том, чтоrmbЭлементы повторяются. Значит, нам нужно идти дальше.
>>> set(makes_100)
{(20, 20, 20, 10, 10, 10, 5, 5), (20, 20, 20, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 10, 10, 10, 10, 10, 5, 5), (20, 20, 10, 10, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 20, 10, 10, 10, 10)}
Получен конечный результат, схем комбинаций для достижения цели в 100 юаней может быть 5.
В соответствии с привычками программирования Python приведенная выше программа может быть написана так:
>>> makes_100 = [comb for n in range(7, len(rmb)+1) for comb in itertools.combinations(rmb, n) if sum(comb)==100]
>>> set(makes_100)
{(20, 20, 20, 10, 10, 10, 5, 5), (20, 20, 20, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 10, 10, 10, 10, 10, 5, 5), (20, 20, 10, 10, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 20, 10, 10, 10, 10)}
Демонстрирует ли это простоту Python?
Этот вопрос также можно изменить следующим образом:
тема: Есть несколько юаней номиналом 50, 20, 10, 5 и 1 юань.Спросите, сколько способов вы можете объединить, чтобы получить 100 юаней.
По мере изменения проблемы меняется и используемая функция. так какcombinations()Роль состоит в том, чтобы выбрать несколько комбинаций элементов из известного набора данных, однако не достигает того, что требуется в этом вопросе. Например, самая прямая комбинация в вопросе — 100 1 юань. И это сочетаниеcombinationsфункция не может обеспечить.
В itertools есть еще одна функция, которая может помочь нам решить эту проблему.
>>> list(itertools.combinations_with_replacement([1, 2], 2))
[(1, 1), (1, 2), (2, 2)]
>>> list(itertools.combinations([1,2], 2)) #注意比较两者的结果
[(1, 2)]
Из приведенной выше операции видно, чтоcombinations_with_replacementиcombinationsразница.combinations_with_replacementэто функция, используемая для решения этой проблемы.
>>> rmbs = [50, 20, 10, 5, 1]
>>> makes_100_2 = []
>>> for n in range(2, 101):
... for comb in itertools.combinations_with_replacement(rmbs, n):
... if sum(comb) == 100:
... makes_100_2.append(comb)
...
#开始执行上面的程序，需要一段时间，你可以此时完成如下活动：喝水、上厕所、想想人生。
>>> len(makes_100_2)
343
Хотя приведенная выше программа требует много времени, она может решить вышеуказанную проблему методом перебора — необходимо выполнить 96 560 645 комбинаций.
Для задачи «сочетания монет» это классическая задача в алгоритме, здесь мы фактически используем метод «перебора грубой силы», который не является лучшим методом, а просто демонстрирует использование двух функций в itertools.
В itertools помимо вышеперечисленных функций, реализующих комбинирование, есть еще функции, реализующие перестановку:permutations()
>>> import itertools
>>> list(itertools.permutations(['a', 'b', 'c']))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
последовательность
itertoolsМодуль также предоставляет объект итератора, который содержит бесконечные элементы — обратите внимание, что хотя бесконечные элементы включены, не беспокойтесь, потому что они не считываются в память. В этом преимущество итераторов.
нечетные и четные числа
Говоря математическим языком, нечетные и четные числа имеют бесконечные члены. Итак, как такая коллекция представлена в Python? Это для создания итератора — по сути, следующее создание — это генератор, а генератор — это итератор.
>>> def evens():
... n = 0
... while True:
... yield n
... n += 2
...
Эта функция может генерировать четный набор, который на самом деле возвращает объект генератора — «Изучаем Python по-старому: легкий старт» подробно описывает генератор.
>>> e = evens() #①
>>> list(next(e) for _ in range(6)) #②
[0, 2, 4, 6, 8, 10]
①Получить объект-генератор набора четных чисел.В ②с помощью оператора цикла генерируется 6 четных чисел.В это время эти четные числа считываются в память.
То же самое справедливо и для генераторных функций с нечетными номерами.
>>> def odds():
... n = 1
... while True:
... yield n
... n += 2
...
бесконечное число
В itertools предусмотрена еще одна функция для реализации создания объекта итератора для набора определенных обычных чисел.
Например натуральные числа:
>>> counter = itertools.count()
>>> list(next(counter) for _ in range(9))
[0, 1, 2, 3, 4, 5, 6, 7, 8]
Подобно предыдущим объектам генератора для четных и нечетных наборов, здесь мы получаемcounterОбъект также считывает в память соответствующие натуральные числа в соответствии с заданным числом только тогда, когда значение считывается - является ли 0 натуральным числом? Вот и давайте так думать.
При использованииhelp()Глядя на справку для этой функции, вы можете увидеть это утверждение:
count(start=0, step=1) --> count object
существуетcounter = itertools.count()Не заданы параметрыstepзначение, означает, что по умолчаниюstep=1, и еще один параметрstart=0. Из настроек этих двух параметров мы можем задать набор натуральных чисел, начиная с определенного значения и до бесконечности, а шаги — это определенное значение. Тогда есть другой способ реализовать четные и нечетные наборы, продемонстрированные ранее.
#偶数的迭代器
>>> evens = itertools.count(step=2)
>>> list(next(evens) for _ in range(9))
[0, 2, 4, 6, 8, 10, 12, 14, 16]
#奇数的迭代器
>>> odds = itertools.count(start=1, step=2)
>>> list(next(odds) for _ in range(9))
[1, 3, 5, 7, 9, 11, 13, 15, 17]
На самом деле вы можете оперировать не только натуральными числами, но и числами с плавающей запятой. Примечание. Требуется версия после Python 3.1.
>>> counter_float = itertools.count(start=0.5, step=0.25)
>>> list(next(counter_float) for _ in range(9))
[0.5, 0.75, 1.0, 1.25, 1.5, 1.75, 2.0, 2.25, 2.5]
Возможны и отрицательные числа.
>>> counter_negative = itertools.count(start=-1, step=-0.3)
>>> list(next(counter_negative) for _ in range(9))
[-1, -1.3, -1.6, -1.9000000000000001, -2.2, -2.5, -2.8, -3.0999999999999996, -3.3999999999999995]
В приведенных выше результатах есть какие-то особые числа с плавающей запятой, почему так?
С помощью вышеперечисленных операцийitertools.count()иrange()Разница тоже очень очевидна. В части натуральных чисел обе функции аналогичны, иrangeТакже возвращает объект итератора. но,rangeВсе возвращенные объекты находятся в пределах ограниченного диапазона,countбесконечно. Другое отличие состоит в том, чтоcountМожет обрабатывать не только числа в диапазоне натуральных чисел, но также отрицательные числа и числа с плавающей запятой.
Генераторы упомянуты ранее, хотя наборов много с бесконечным числом, а выше перечислено несколько, большинство из них проходитitertools.countЭтого можно достичь, а для того, чего нельзя достичь, вы также можете написать функцию генератора (итератора) для достижения этого. В это время необходимо привести следующий пример, то есть функцию-генератор для записи последовательности Фибоначчи — для других способов записи последовательности Фибоначчи рекомендуется прочитать мою книгу «Изучаем Python со старым: легкое начало».
>>> def fibs():
... a, b = 0, 1
... while True:
... yield a
... a, b = b, a + b
...
С помощью этой генераторной функции можно получить бесконечное количество чисел Фибоначчи.
>>> f = fibs()
>>> list(next(f) for _ in range(9))
[0, 1, 1, 2, 3, 5, 8, 13, 21]
Получил 9-членную последовательность Фибоначчи.
Для набора бесконечных элементов необходимо извлечь некоторое конечное число чисел, за исключением использования описанного выше метода цикла.next(f) for _ in range(9)В качестве альтернативы можно использовать одну из функций itertools. Например:
>>> counter = itertools.count()
>>> list(itertools.islice(counter, 9))
[0, 1, 2, 3, 4, 5, 6, 7, 8]
itertools действительно оправдывает свое название.
рекуррентное соотношение
В математикерекурсияилирекуррентное соотношение(Рекуррентное отношение) распространено в последовательности, такой как арифметическая последовательность, пропорциональная последовательность и т. д., которые все являются рекурсивными отношениями. С этой точки зрения предыдущее использованиеitertools.countРезультирующая последовательность представляет собой последовательность рекурсивных отношений.
Числа последовательности Фибоначчи, перечисленные выше, на самом деле являются рекурсивными числами. Другими словами, функция последовательности Фибоначчи также может быть реализована «рекурсивно».
Однако существует также последовательность рекурсивных отношений, которые нельзя использовать сitertools.countПолучить, то есть все числа одинаковые, например, все они состоят из 1, или же они состоят из определенных чисел, таких как 1, 3 и 5.
Для этого в модуле itertools предусмотрены дополнительные функции.
>>> ones = itertools.repeat(1)
>>> list(itertools.islice(ones, 9))
[1, 1, 1, 1, 1, 1, 1, 1, 1]
itertools.repeatФункция предназначена для генерации бесконечно длинной последовательности чисел. Примечание. Помимо чисел, его параметрами могут быть и другие объекты, такие как строки, списки и т. д.
Конечно, также можно создать ограниченный, а затем добавить параметр, определяющий количество элементов.
>>> five_ones = itertools.repeat(1, 5)
>>> [i for i in five_ones]
[1, 1, 1, 1, 1]
В другом случае можно использоватьitertools.cycleреализация функции. Вы можете догадаться, как должен выглядеть результат, если посмотрите на имя функции, не заглядывая сначала в демонстрационный пример - [1,3,5,1,3,5,...], он должен быть таким, иначе он не может быть циклом.
>>> otf = itertools.cycle([1, 3, 5])
>>> list(itertools.islice(otf, 9))
[1, 3, 5, 1, 3, 5, 1, 3, 5, 1, 3, 5, 1, 3, 5]
В приведенной выше демонстрации удаляются только первые 15 элементов последовательности, как и ожидалось.
Вышеприведенные демонстрации являются частными случаями рекуррентного соотношения.Так называемые рекуррентные соотношения первого и второго порядка в рекуррентном соотношении будут объяснены ниже в математической форме.
Два соседних элемента в последовательности соответствуют этой формуле, которая представляет собой последовательность рекурсивных отношений первого порядка.
- P=1, для арифметической последовательности
- P=1 и h=0 — постоянный столбец
- P≠0 и h=0 — пропорциональная последовательность.
Существует еще одно рекуррентное отношение, которое представляет собой отношение между определенным элементом и двумя соседними элементами, например, в предыдущей последовательности Фибоначчи, где третий элемент равен сумме первых двух элементов. Общий термин этого отношения может быть выражен как:
Для этого общего термина, если P=Q=1 и h=0, то он называется последовательностью Фибоначчи.
Согласно приведенному выше общему термину видно, что предыдущийcount,repeat,cycleВсе последовательности, реализованные с помощью etc., являются специальными последовательностями. Есть ли что-нибудь более общее, чем они?
должен иметь.
>>> list(range(9))
[0, 1, 2, 3, 4, 5, 6, 7, 8]
>>> list(itertools.accumulate(range(9)))
[0, 1, 3, 6, 10, 15, 21, 28, 36]
Обратите внимание, что приведенная выше реализация не является последовательностью Фибоначчи, а получается новая последовательность, как показано на рисунке ниже.
Когда вы видите эту функцию, вам следует подумать о другой функции, если вы ее не помните, значит, ваши базовые знания еще есть куда развивать.
>>> import functools
>>> functools.reduce(lambda x,y :x+y, range(9))
36
иfunctools.reduceпо сравнению с,itertools.accumulateВозвращается не число, а массив, строго говоря, объект-итератор с элементами массива в качестве потенциальных объектов.
виделitertools.accumulate(range(9))результат. И дляaccumulate()Например, его полная форма параметра выглядит следующим образом:
accumulate(iterable[, func]) --> accumulate object
По умолчанию следующая функция является функцией сложения. Итак, способ, как показано ниже, такой же, как и в предыдущем примере.
>>> import operator
>>> list(itertools.accumulate(range(9), operator.add))
[0, 1, 3, 6, 10, 15, 21, 28, 36]
По этому принципу можно оперировать многими сериями, а другую серию можно получить по функциональному соотношению. Несколько примеров перечислены ниже по очереди.
>>> list(itertools.accumulate([9, 21, 17, 5, 11, 12, 2, 6], min))
[9, 9, 9, 5, 5, 5, 2, 2]
>>> list(itertools.accumulate([1, 2, 3, 4, 5], lambda x, y: (x + y) / 2))
[1, 1.5, 2.25, 3.125, 4.0625]
Помните отношение рекурсии первого порядка из предыдущего? Если вы пишете функцию, реализуете это реляционное выражение?
>>> def first_order(p, h, initial_val):
... return itertools.accumulate(itertools.repeat(initial_val), lambda a, _: p*a + h)
...
Эта функция является общим термином рекурсии первого порядка, с помощью которого можно получить рекурсивную последовательность первого порядка.
Две заученные функции используются в комбинации в функции. Проверьте это ниже.
>>> evens = first_order(p=1, h=2, initial_val=0) #得到偶数数列
>>> list(itertools.islice(evens, 5))
[0, 2, 4, 6, 8]
#能被3整除的数
>>> count_by_threes = first_order(p=1, h=3, initial_val=0)
>>> list(itertools.islice(count_by_threes, 5))
[0, 3, 6, 9, 12]
#由1，-1组成的数列
>>> alternating_ones = first_order(p=-1, h=0, initial_val=1)
>>> list(itertools.islice(alternating_ones, 5))
[1, -1, 1, -1, 1]
#都是1组成的数列
>>> all_ones = first_order(p=1, h=0, initial_val=1)
>>> list(itertools.islice(all_ones, 5))
[1, 1, 1, 1, 1]
Нетрудно видеть из вышеприведенного примера, что при получении общего члена рекуррентного соотношения первого порядка все рекуррентные последовательности первого порядка могут быть взяты во всех.
Здорово.
Точно так же может быть записана функция общего члена рекурсивного отношения второго порядка.
>>> def second_order(p, q, h, initial_val):
... itermediate = itertools.accumulate(
itertools.repeat(initial_val),
lambda a, _:(a[1], p*a[1] + q*a[0] + h))
... return map(lambda x: x[0], itermediate)
...
Общая терм-функция рекурсивного соотношения второго порядка кажется сложной. Поскольку в рекурсивном общем термине второго порядка начальным значением являются первые два термина, поэтому, если вы напрямую реализуете значение математической функции и возвращаете два значения, вы должны использоватьmapфункция для извлечения значений одно за другим.
После написания используйте его для создания последовательности Фибоначчи.
>>> fibs = second_order(p=1, q=1, h=0, initial_val=(0, 1))
>>> list(itertools.islice(fibs, 9))
[0, 1, 1, 2, 3, 5, 8, 13, 21]
Сравните предыдущую последовательность Фибоначчи. Почувствуйте прелесть общего члена функции рекуррентного соотношения второго порядка.
В дополнение к последовательности Фибоначчи типичное рекуррентное соотношение второго порядка также имеет число Пелла (Pell number) и число Лукаса (Lucas number).
Pell number:
Lucas Number:
Давайте воспользуемся общим термином рекуррентного соотношения второго порядка выше, чтобы реализовать эти две последовательности.
>>> pell = second_order(p=2, q=1, h=0, initial_val=(0, 1))
>>> list(itertools.islice(pell, 6))
[0, 1, 2, 5, 12, 29]
>>> lucas = second_order(p=1, q=1, h=0, initial_val=(2, 1))
>>> list(itertools.islice(lucas, 6))
[2, 1, 3, 4, 7, 11]
Итераторы — это хорошо, и в itertools есть еще кое-что.
Серия книг:
- «Изучайте Python со старым: Easy Getting Started»: для новичков в языке Python эта книга основана на Python3.x.
- «Изучайте Python со старым: Django в действии»: для читателей, которые изучают веб-разработку, первое издание этой книги основано на Django1.10, а второе издание основано на Django2.x.
- «Изучайте Python по-старому: анализ данных»: для начинающих изучать науку о данных (анализ данных, машинное обучение)