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