Выразительная Простота Python На Примере Задач Из Комбинаторики

В процессе самостоятельного изучения языка программирования Python (имея знания C/C++) я решил написать генерирующие элементы из различных наборов в виде присваивания функции.

комбинаторные конфигурации .

Конечно, справедливо будет сказать, что подобный функционал уже существует в стандартной библиотеке Python в модуле itertools, но каждый должен иметь право изобретать велосипед, особенно в целях обучения… Любой, кто знаком с основами теории вероятностей, должен запомнить, что такое узоры урн и о чем эта таблица:



И так техническое задание состоит в том, чтобы написать четыре генератора, которые принимают строку с , состоящий из уникальных символов, и размер выборки К , вернуть строку — образец с повторением/без повторения из к символы строки с Порядок важен/не важен.

В результате получился следующий код:

   

 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 #Алгоритмы #комбинаторика #python #Алгоритмы

• Что Нужно Знать О Планшетном Пк

  19 Oct, 24

• Социолингвистика

  19 Oct, 24

• Как Уйти Из Школы И Перевести Ребенка На Дистанционное Обучение

  19 Oct, 24

• Обзор Raise3D N1 Dual От Rec

  19 Oct, 24

• Облачные Игры С Открытым Исходным Кодом На Webrtc: P2P, Мультиплеер, Нулевая Задержка

  19 Oct, 24

• Повреждение Головного Мозга Спасло Его Музыку

  19 Oct, 24

• Поговорим О Метриках Как Способе Оценки Работы Программиста

  19 Oct, 24

• История Создания И Запуска Веселой Мобильной Игры Про Разбиение Бутылок Об Голову

  19 Oct, 24

• Тулдуино

  19 Oct, 24

• В Digg.com Было Инвестировано 8,5 Миллионов Долларов.

  19 Oct, 24