Выразительная простота python на примере задач из комбинаторики
2 мин
Тот кто знаком с основами теории вероятностей должны помнить, что такое урновые схемы и о чем эта таблица:
И так ТЗ — написать четыре генератора, которые принимая строку s, состоящую из уникальных символов, и размер выборки к, возвращают строку — выборку с повторением/без повторений из k символов строки s порядок важен/не важен.
В результате получился следующий код:
import itertools
from functools import partial
import unittest
def template(s, k, assertion, reducer):
n = len(s)
assert assertion(n, k)
if k == 0:
yield ""
elif k == 1:
for c in s:
yield c
else:
k-=1
for i, c in enumerate(s):
new_s = reducer(s, i)
if not assertion(len(new_s), k):
break
for res in template(new_s, k, assertion, reducer):
yield c+res
assertion_norep = lambda n, k: n > 0 and n >= k and k >= 0
assertion_rep = lambda n, k: n > 0 and k >= 0
permutation_norep = partial(template, assertion=assertion_norep, reducer=lambda s, i: s[:i]+s[i+1:])
permutation_rep = partial(template, assertion=assertion_rep, reducer=lambda s, i: s)
combination_norep = partial(template, assertion=assertion_norep, reducer=lambda s, i: s[i+1:])
combination_rep = partial(template, assertion=assertion_rep, reducer=lambda s, i: s[i:])
class TestCombinatoricGenerators(unittest.TestCase):
@classmethod
def setUpClass(cls):
cls.test_string = "abcdefg"
cls.k = 5
def test_permutation_norep(self):
self.assertEquals(set(permutation_norep(self.test_string, self.k)),
set(map(''.join, itertools.permutations(self.test_string, self.k))))
def test_permutation_rep(self):
self.assertEquals(set(permutation_rep(self.test_string, self.k)),
set(map(''.join, itertools.product(self.test_string, repeat=self.k))))
def test_combination_norep(self):
self.assertEquals(set(combination_norep(self.test_string, self.k)),
set(map(''.join, itertools.combinations(self.test_string, self.k))))
def test_combination_rep(self):
self.assertEquals(set(combination_rep(self.test_string, self.k)),
set(map(''.join, itertools.combinations_with_replacement(self.test_string, self.k))))
if __name__ == '__main__':
unittest.main()Так как python является языком еще более высокого уровня абстракции, чем с/с++, поэтому он позволяет проще и выразительнее писать код, который бы на других языках выглядел бы более громоздко и запутаннее. Новичкам в python я хотел бы обратить внимание на несколько моментов:
- return после yield
- Рекурсивный генератор
- Шаблон стратегия
- Использование lambda функций
P.S.
Могу добавить, что я не сразу пришел к подобному решению, использующему общую «шаблонную» функцию. Сначала я написал все функции по отдельности, а потом выделил общее и различное.
Как-то я экспериментировал с клеточными автоматами. С одномерными и двумерными. Придумывал на каком исходном состоянии применить какое-то правило. Когда, в качестве исходного состояния двумерного клеточного автомата я начал использовать бит-реверсивную перестановку диагональной линии, то после применения автомата получались своеобразные узоры. Время от времени среди узоров появлялись явно выраженные характерные паттерны. Я выделил эти паттерны и немного с ними поэкспериментировал. С тем, что мне удалось выяснить, я делюсь в этой статье.
