Geekly Articles each Day
📜 ⬆️ ⬇️

The expressive simplicity of python on the example of tasks from combinatorics

In the process of self-study, the python programming language (having knowledge of c / c ++) decided to write as a task the functions generating elements from different sets of combinatorial configurations . Of course, it can be fairly noted that such functionality already exists in the standard python library in the itertools module, but everyone should have the right to reinvent the wheel, especially for learning purposes ...
Those who are familiar with the basics of the theory of probability should remember what urn schemes are and what this table is about:


And so TK - to write four generators, which taking the string s , consisting of unique characters, and the sample size k , return the string - a sample with / without repetition of k characters of the string s .
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 an even higher level of abstraction than c / c ++, so it makes it easier and more expressive to write code that in other languages ​​would look more cumbersome and confusing. For beginners in python, I would like to draw attention to a few points:

  • return after yield
  • Recursive generator
  • Strategy pattern
  • Using lambda functions


PS
I can add that I did not immediately come to a similar decision using a common "template" function. First, I wrote all the functions separately, and then singled out the general and the different.

Source: https://habr.com/ru/post/232757/

More articles:


All Articles