The expressive simplicity of python using tasks from combinatorics as an example

redlinelm August 9, 2014 at 00:16

The expressive simplicity of python using tasks from combinatorics as an example

In the process of self-learning, the python programming language (having knowledge of c / c ++) decided to write generating functions from various sets of combinatorial configurations as a function job . Of course, you can rightly notice that such functionality is already in the standard python library in the itertools module, but everyone should have the right to invent a bicycle, especially for training purposes ...
Anyone familiar with the basics of probability theory should remember what urn schemes are and about than this table:

And so TK - write four generators that, taking a string s consisting of unique characters and a sample size of k , return a string - a sample with / without repetition of k characters of string sorder is important / not important.
The result is the following code:

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()

Since python is a language of an even higher level of abstraction than c / c ++, it therefore makes it easier and more expressive to write code that would look more bulky and confusing in other languages. To newbies in python, I would like to draw attention to a few points:

return after yield
Recursive generator
Strategy Template
Using lambda functions

PS
I can add that I did not immediately come up with a similar solution using a common "template" function. First, I wrote all the functions separately, and then highlighted the general and the different.

Tags: