Foundations of Computational Economics #12

Foundations of Computational Economics #12¶

by Fedor Iskhakov, ANU

Enumeration of discrete compositions¶

https://youtu.be/eU2WRHBTFBw

Description: Combinatorial enumeration. Python generators.

Generators in Python¶

yield keyword is a special kind of return from a function

“pauses” the function execution
waits fro the next iteration request from the caller
saves its state for the next call

Use generators instead of lists when only one element of the list is needed at any time

saves memory: alternative is a list of objects to be generated
overhead in keeping the state of the generator function

Iterator vs Iterable vs Generator¶

Iterator:

object that can return its members one at a time
has iter and next methods
support StopIteration error
can be used in for loops

Iterable:

object that can be converted to an iterator with iter() function
can be used in for loops directly
examples: lists, tuples, strings

Generator:

a particular kind of iterator
can be implemented as a function with yield returns
or as comprehension expression similar to list comprehension

Note on range()¶

Range object is an itarable, therefore

iter() function converts it to iterator
it can be used directly in for loops
but it is more than a generator: can be used in many other tasks besides looping

In [4]:

# simple examples of generators
def test_generator():
    '''Testing generator
    '''
    yield 1
    yield 5
    yield 15
    yield 25

g = test_generator()
print('initial call returned %d' % (next(g)))
for i in g:
    print('loop call returned %d' % (i))
print('loop finished gracefully')
next(g)  # impossible to get any output once generator is done

initial call returned 1
loop call returned 5
loop call returned 15
loop call returned 25
loop finished gracefully

---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-4-cb7c6099be2a> in <module>
     13     print('loop call returned %d' % (i))
     14 print('loop finished gracefully')
---> 15 next(g)  # impossible to get any output once generator is done

StopIteration:

In [3]:

def test_generator_steps():
    '''Testing generator
    '''
    for i in range(10):
        print('generator at step %d'%(i))
        yield i

g = test_generator_steps()
for i in g:
    print('main code at step %d' % (i))

generator at step 0
main code at step 0
generator at step 1
main code at step 1
generator at step 2
main code at step 2
generator at step 3
main code at step 3
generator at step 4
main code at step 4
generator at step 5
main code at step 5
generator at step 6
main code at step 6
generator at step 7
main code at step 7
generator at step 8
main code at step 8
generator at step 9
main code at step 9

Discrete compositions¶

$$ (p_1, p_2, \dots, p_n) \text{ such that } p_i \in \mathbb{Z}, 0 \le p_i \le M, \sum_{i=1}^{n}p_i = M $$

$ (p_1,p_2,\dots,p_n) $ is composition of number $ M $ into $ n $ parts.

Number of compositions¶

composition corresponds to cutting the interval of length $ M $ into $ n $ parts
but cut points can be at the same place to allow for zeros
instead let interval of length $ M+n $ be cut
discrete $ \rightarrow $ have $ M+n-1 $ points for $ n-1 $ cuts
no overlaps in the latter scheme

$$ \text{Number of compositions} = {M+n-1 \choose n-1} = \frac{(M+n-1)!}{n!(M-1)!} $$

In [3]:

import scipy.special
def number_compositions(n,M):
    '''Returns the number of discrete compositions for given parameters
    '''
    return int(scipy.special.comb(M+n-1,n-1)) # M+n-1 choose n-1

print('n=%3d, M=%3d --> NC=%d'%(2,2,number_compositions(2,2)))
print('n=%3d, M=%3d --> NC=%d'%(2,10,number_compositions(2,10)))
print('n=%3d, M=%3d --> NC=%d'%(2,100,number_compositions(2,100)))
print('n=%3d, M=%3d --> NC=%d'%(5,10,number_compositions(5,10)))
print('n=%3d, M=%3d --> NC=%d'%(5,100,number_compositions(5,100)))
print('n=%3d, M=%3d --> NC=%d'%(10,100,number_compositions(10,100)))
print('n=%3d, M=%3d --> NC=%d'%(50,100,number_compositions(50,100)))

n=  2, M=  2 --> NC=3
n=  2, M= 10 --> NC=11
n=  2, M=100 --> NC=101
n=  5, M= 10 --> NC=1001
n=  5, M=100 --> NC=4598126
n= 10, M=100 --> NC=4263421511270
n= 50, M=100 --> NC=6709553636577312758557068362648666505216

Lexicographical order¶

Composition $ p = (p_1, p_2, \dots, p_n) $ is greater than composition $ p' = (p'_1, p'_2, \dots, p'_n) $ in lexicographical sense iff for some $ J \in \{1,\dots,n\} $ $ p_j=p'_j $ for all $ j<J $ and $ p_J>p'_J $.

$ j=n $ is the lowest digit, $ j=1 $ is the highest digit

Composition $ p $ is greater that $ p' $ iff the highest different digit of $ p $ is greater than that of $ p' $.

Examples of lexicographical order¶

numbers in any base system
words in a dictionary
compositions to be generated

In [4]:

def compositions(N,m):
    '''Iterable on compositions of N with m parts
    Returns the generator (to be used in for loops)
    '''
    pass

In [2]:

n, M = 4, 8
for i,k in enumerate(compositions(M,n)):
    print('%3d'%i,end=": ")
    print(k)

  0: [0, 0, 0, 8]
  1: [0, 0, 1, 7]
  2: [0, 0, 2, 6]
  3: [0, 0, 3, 5]
  4: [0, 0, 4, 4]
  5: [0, 0, 5, 3]
  6: [0, 0, 6, 2]
  7: [0, 0, 7, 1]
  8: [0, 0, 8, 0]
  9: [0, 1, 0, 7]
 10: [0, 1, 1, 6]
 11: [0, 1, 2, 5]
 12: [0, 1, 3, 4]
 13: [0, 1, 4, 3]
 14: [0, 1, 5, 2]
 15: [0, 1, 6, 1]
 16: [0, 1, 7, 0]
 17: [0, 2, 0, 6]
 18: [0, 2, 1, 5]
 19: [0, 2, 2, 4]
 20: [0, 2, 3, 3]
 21: [0, 2, 4, 2]
 22: [0, 2, 5, 1]
 23: [0, 2, 6, 0]
 24: [0, 3, 0, 5]
 25: [0, 3, 1, 4]
 26: [0, 3, 2, 3]
 27: [0, 3, 3, 2]
 28: [0, 3, 4, 1]
 29: [0, 3, 5, 0]
 30: [0, 4, 0, 4]
 31: [0, 4, 1, 3]
 32: [0, 4, 2, 2]
 33: [0, 4, 3, 1]
 34: [0, 4, 4, 0]
 35: [0, 5, 0, 3]
 36: [0, 5, 1, 2]
 37: [0, 5, 2, 1]
 38: [0, 5, 3, 0]
 39: [0, 6, 0, 2]
 40: [0, 6, 1, 1]
 41: [0, 6, 2, 0]
 42: [0, 7, 0, 1]
 43: [0, 7, 1, 0]
 44: [0, 8, 0, 0]
 45: [1, 0, 0, 7]
 46: [1, 0, 1, 6]
 47: [1, 0, 2, 5]
 48: [1, 0, 3, 4]
 49: [1, 0, 4, 3]
 50: [1, 0, 5, 2]
 51: [1, 0, 6, 1]
 52: [1, 0, 7, 0]
 53: [1, 1, 0, 6]
 54: [1, 1, 1, 5]
 55: [1, 1, 2, 4]
 56: [1, 1, 3, 3]
 57: [1, 1, 4, 2]
 58: [1, 1, 5, 1]
 59: [1, 1, 6, 0]
 60: [1, 2, 0, 5]
 61: [1, 2, 1, 4]
 62: [1, 2, 2, 3]
 63: [1, 2, 3, 2]
 64: [1, 2, 4, 1]
 65: [1, 2, 5, 0]
 66: [1, 3, 0, 4]
 67: [1, 3, 1, 3]
 68: [1, 3, 2, 2]
 69: [1, 3, 3, 1]
 70: [1, 3, 4, 0]
 71: [1, 4, 0, 3]
 72: [1, 4, 1, 2]
 73: [1, 4, 2, 1]
 74: [1, 4, 3, 0]
 75: [1, 5, 0, 2]
 76: [1, 5, 1, 1]
 77: [1, 5, 2, 0]
 78: [1, 6, 0, 1]
 79: [1, 6, 1, 0]
 80: [1, 7, 0, 0]
 81: [2, 0, 0, 6]
 82: [2, 0, 1, 5]
 83: [2, 0, 2, 4]
 84: [2, 0, 3, 3]
 85: [2, 0, 4, 2]
 86: [2, 0, 5, 1]
 87: [2, 0, 6, 0]
 88: [2, 1, 0, 5]
 89: [2, 1, 1, 4]
 90: [2, 1, 2, 3]
 91: [2, 1, 3, 2]
 92: [2, 1, 4, 1]
 93: [2, 1, 5, 0]
 94: [2, 2, 0, 4]
 95: [2, 2, 1, 3]
 96: [2, 2, 2, 2]
 97: [2, 2, 3, 1]
 98: [2, 2, 4, 0]
 99: [2, 3, 0, 3]
100: [2, 3, 1, 2]
101: [2, 3, 2, 1]
102: [2, 3, 3, 0]
103: [2, 4, 0, 2]
104: [2, 4, 1, 1]
105: [2, 4, 2, 0]
106: [2, 5, 0, 1]
107: [2, 5, 1, 0]
108: [2, 6, 0, 0]
109: [3, 0, 0, 5]
110: [3, 0, 1, 4]
111: [3, 0, 2, 3]
112: [3, 0, 3, 2]
113: [3, 0, 4, 1]
114: [3, 0, 5, 0]
115: [3, 1, 0, 4]
116: [3, 1, 1, 3]
117: [3, 1, 2, 2]
118: [3, 1, 3, 1]
119: [3, 1, 4, 0]
120: [3, 2, 0, 3]
121: [3, 2, 1, 2]
122: [3, 2, 2, 1]
123: [3, 2, 3, 0]
124: [3, 3, 0, 2]
125: [3, 3, 1, 1]
126: [3, 3, 2, 0]
127: [3, 4, 0, 1]
128: [3, 4, 1, 0]
129: [3, 5, 0, 0]
130: [4, 0, 0, 4]
131: [4, 0, 1, 3]
132: [4, 0, 2, 2]
133: [4, 0, 3, 1]
134: [4, 0, 4, 0]
135: [4, 1, 0, 3]
136: [4, 1, 1, 2]
137: [4, 1, 2, 1]
138: [4, 1, 3, 0]
139: [4, 2, 0, 2]
140: [4, 2, 1, 1]
141: [4, 2, 2, 0]
142: [4, 3, 0, 1]
143: [4, 3, 1, 0]
144: [4, 4, 0, 0]
145: [5, 0, 0, 3]
146: [5, 0, 1, 2]
147: [5, 0, 2, 1]
148: [5, 0, 3, 0]
149: [5, 1, 0, 2]
150: [5, 1, 1, 1]
151: [5, 1, 2, 0]
152: [5, 2, 0, 1]
153: [5, 2, 1, 0]
154: [5, 3, 0, 0]
155: [6, 0, 0, 2]
156: [6, 0, 1, 1]
157: [6, 0, 2, 0]
158: [6, 1, 0, 1]
159: [6, 1, 1, 0]
160: [6, 2, 0, 0]
161: [7, 0, 0, 1]
162: [7, 0, 1, 0]
163: [7, 1, 0, 0]
164: [8, 0, 0, 0]

In [1]:

def compositions(N,m):
    '''Iterable on compositions of N with m parts
    Returns the generator (to be used in for loops)
    '''
    cmp=[0,]*m
    cmp[m-1]=N  # initial composition is all to the last
    yield cmp
    while cmp[0]!=N:
        i=m-1
        while cmp[i]==0: i-=1  # find lowest non-zero digit
        cmp[i-1] = cmp[i-1]+1  # increment next digit
        cmp[m-1] = cmp[i]-1    # the rest to the lowest
        if i!=m-1: cmp[i] = 0  # maintain cost sum
        yield cmp

Further learning resources¶

Generators vs. lists in Python https://www.youtube.com/watch?v=bD05uGo_sVI
Iterators and generators in Trey Hunner blog https://treyhunner.com/2018/06/how-to-make-an-iterator-in-python/
Some examples of combinatorial optimization https://neos-guide.org/content/combinatorial-optimization