Выразительная простота python на примере задач из комбинаторики

    В процессе самообучения языку программирования python(имея знания с/с++) решил написать в качестве задания функции генерирующие элементы из различных множеств комбинаторных конфигураций. Конечно, можно справедливо заметить, что подобный функционал уже есть в стандартной библиотеке python в модуле itertools, но у каждого должно быть право изобрести велосипед, тем более в целях обучения…
    Тот кто знаком с основами теории вероятностей должны помнить, что такое урновые схемы и о чем эта таблица:


    И так ТЗ — написать четыре генератора, которые принимая строку 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.
    Могу добавить, что я не сразу пришел к подобному решению, использующему общую «шаблонную» функцию. Сначала я написал все функции по отдельности, а потом выделил общее и различное.
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 36
    • +4
      Камрад, не умаляя значения проделанной работы, хочу напомнить о наличии в стандартной библиотеке itertools, в том числе функций product(), permutations(), combinations(), combinations_with_permutations().
      • +1
        Я уже написал о изобретения велосипеда, предвосхищая ваш коментарий. Зачем комениторовать не полность прочитанный текст…
    • +2
      Также совершенно нe к месту assert в теле функции, который работает лишь при заданном __debug__.
      • +1
        Наоборот, он не работает при включенных оптимизациях (никогда не видел, чтобы кто-то их включал). Более того, это очень правильный способ проверить, что что-то не так.
        • 0
          Так я о том же и написал. __debug__ == False при загрузке кода из *.pyo файла. https://docs.python.org/3/reference/simple_stmts.html#the-assert-statement.
          • +1
            assert в данном случае используется неправильно, по очень простой причине: он производит валидацию значений входных данных, чем должна заниматься бизнес-логика. assert нужен в качестве инструмента для поиска ошибок программиста, например:

            assert isinstance(k, int), 'Invalid input "k" argument type in template(), should be int, received %s' % type(k)
            
            • +4
              А я видел. Например, anki под win32.
              Отладка была мучительной, потому что внутри assert происходил какой-то побочный эффект.

              Итого, проверять assert'ом нужно только то, что не должно происходить в программе никогда. Неправильные аргументы функции нужно проверять if'ом с вызовом исключения в случае необходимости.
          • +5
            Выразительная простота python


            Я не осилил этот код в течении нескольких минут не смотря на то, что сам когда то ради интереса писал подобное. Не осилил потому что постоянно натыкался на странные слова template, reducer, assertion и пытался понять а что это за хрень такая и зачем она может быть нужна. Возможно с более интуитивно понятными именами получилось бы нагляднее.
            • +3
                  n = len(s)
                  ...
                  for i in range(n):
                      c = s[i]
              

              Откройте для себя enumerate.

              На самом деле Ваш код просто ужасен. Автор, извините, но у Вас C++ головного мозга, на python так не пишут. Pythonic-код — это понятный, легко-читаемый код с нормальными именами переменных, Вы же, видимо, стремились к максимально короткому и насыщенному лишними абстракциями коду.
              • 0
                Не могли бы вы написать это на питоне как надо? Я сам о питоне только слышал и поэтому любопытствую.
                • +1
                  for index, item in enumerate(n):
                  c = item

                  • +3
                    Конкретно этот код автора вот так можно переписать:

                    for i, c in enumerate(s):
                        ...
                    

                    Особо в код не вчитывался, может там вообще всё можно переписать. Сейчас код автора выглядит плохо. На Python так не пишут.
                    • 0
                      А как надо можно узнать?
                      • 0
                        Начать можно банально с форматирования, согласно PEP8.
                        • 0
                          Но в общем, переменные с ничего не говорящими именами s, k, c, new_s — это уровень первого курса. Если Вы сейчас закроете эту страницу и откроете её через пару месяцев, то может и Вам код покажется нечитаемым и непонятным. Очень рекомендую «Code complete» («Совершенный код» в русском переводе) для улучшения навыков написания красивого кода.
                          • 0
                            То есть ваши претезии только к форме, а не к содержанию? Насчет названия переменнных, что такое k, n должно быть понятно из таблицы над кодом(это стандартные обозначения в комбинаторике), а s для стороки и с для символа тоже не редкость
                            • +1
                              Нет, к содержанию тоже есть претензии. Я бы изначально написал каждую функцию по-отдельности, не используя общие template, с передачей в него пары лямбда-выражений.
                              • 0
                                А можно продолжить мысль и объяснить почему?
                                • +1
                                  Такой код было бы гораздо легче читать. Т.е. представьте себя на месте человека, который не особенно знаком с комбинаторикой и разбирает Ваш код. Он начинает с permutation_norep(). Тут же он сталкивается с тем, что далее идёт вызов template() да ещё с двумя аргументами-функциями. Хорошо, идём дальше в глубину template()… Опа, assertion(). Так, а что там за assertion() был? Ага, n и k дожны быть положительными, либо равны нулю, причём n >= k. Далее — reducer(). А что там этот reducer делает?.. Думаю, Вы поняли мысль.

                                  Вот как например будет выглядеть целостная permutation_norep:

                                  def permutation_norep(s, k):
                                      len_s = len(s)
                                      is_valid_input = len_s > 0 and len_s >= k and k >= 0
                                  
                                      if not is_valid_input:
                                          raise ValueError('Invalid input: s={}, k={}'.format(s, k))
                                  
                                      if k == 0:
                                          yield ""
                                          return
                                      k <= 1:
                                          yield from s
                                          return
                                  
                                      new_k = k - 1
                                  
                                      for i in range(len_s):
                                          new_s = s[:i] + s[i + 1:]
                                          for res in permutation_norep(new_s, new_k):
                                              yield s[i] + res
                                  
                                  • 0
                                    Тьфу ты, в коде elif потерял (там, где k == 1).
                                    • 0
                                      Хорошо… Но задача написать не одну функцию, а четыре. Как я упомянул в своем посте, сначала были написанны все 4 функции подобным образом. Когда перед тобой 4 почти одинаковые функции, а различия в состоят в двух строках кода, появляется естественное желание выделить общее. Такой код намного проще сопровождать, Что бы заменить assert на if(как вы предлагаете ), например, мне нужно одно изменение, а не в четыре. Шаблоны проектирования придуманы не мной, и не один я ими пользуюсь… Так что может ваш код и более «питонистый», но с точки зрения вопроса проектирования я вижу большой минус.
                                      • 0
                                        Я думал об этом, когда писал предыдущий ответ и решил, что я в данном случае я остановился бы на 4-х функциях. Спросите себя, неужто так много усилий стоит поддерживать конкретно эти функции? Скорее всего Вы напишете их и забудете надолго, до тех пор, пока не надо будет внести кардинальные изменения. Опять таки, это не должно занять так много времени, ведь функции по-сути одинаковые.
                                        При всём, я согласен, что в других случаях такой подход совершенно неприемлим и логичнее использовать пострение через шаблон.
                              • 0
                                Если взглянуть на itertools.combinations(iterable, r) то там тоже присутствует однабуквенная переменная…
                        • 0
                          Хотел бы взглянуть на просто прекрасный код…
                        • 0
                          >> поэтому он позволяет проще и выразительнее писать код, который бы на других языках выглядел бы более громоздко и запутаннее
                          Не обощайте: www.ruby-doc.org/core-2.1.2/Array.html#method-i-permutation
                          • +1
                            В python эти функции есть в стандартной библиотеке, о чем сказано в первом комментарии, автор просто попытался реализовать их самостоятельно.
                            • 0
                              Согласен, но сути не меняет. Python не самый выразительный язык, код на других я языках не будет выглядеть более громоздким и запутанным.
                              • 0
                                Ок, пусть так, только давайте не будет устраивать холивар Ruby vs. Python )
                                • 0
                                  Ruby vs Python был бы самым бессмысленным холиваром :)
                                  • 0
                                    Может с пыхой тогда? А то скучновато в субботу с утра.
                                    • –2
                                      С пыхой скучно, там даже ооп нет
                                      • 0
                            • +2
                              Кат бы не помешал.
                              • +1
                                Лично мне в качестве примера выразительности Питона больше нравится заметка Питера Норвига о решалке судоку.
                                • 0
                                  Господа критики, критика должна быть конструктивной. Выражения типа «код автора выглядит плохо. На Python так не пишут», «Ваш код просто ужасен» и т.д. без конкретных замечаний и реализаций смотрятся странно. Критикуя-предлагай.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.