Tickled!
Sharing came up in something I was reading that got me revisiting the Wikipedia page on the Thue Morse Sequence. Tucked away to the right is a static image of ones and zeroes with the caption:"When counting in binary, the digit sum modulo 2 is the Thue-Morse sequence"Now I had already blogged about the Thue-Morse sequence with respect to sharing fairly:
If you had two people, Asia and Bain chosing from different cash bounties then if Asia went first she'd choose the largest cash bounty, then Bain would chose the next larget, ... if they alternate like this then Asia, who went first, would always get more than Bain; furthermore, Asias total accumulated bounty would increase over Bains over time like this:
In my earlier blog entry: Sharing Fairly, I looked into the Thue-Morse sequence for who gets to pick next and showed that using that sequence, and itsextension for more than two people sharing, the person with the most accumulated wealth switches over time and does not diverge like in the simple taking of turns shown above.
I showed how using a Thue-Morse sequence for multiple people sharing gave a "fairer" distribution of wealth, for example this graph of accumulated wealth for three people:
Old Code
My code to generate the Thue Morse sequence for sharing between multiple people was this function:def thue_morse(persons='ABC', mx=20, tutor=True)
Its algorithm works, and was straight forward to describe as a natural extension of the two-person case, but could generate more terms than requested that are then trimmed.
Back to the tickle
"When counting in binary, the digit sum modulo 2 is the Thue-Morse sequence"Now that method might be coded to only give the number of terms required. I might code it as a generator. But as it stands it applies only to two people (binary).
I thought that an equivalent statement for many people might be:
"When counting base b, the digit sum modulo b is the Thue-Morse sequence of fairer sharing between b people"I set out to code it.
Code Journey
"When counting base b" ... "digit sum" ...I am going to need to express an integer in different bases, and sum the digits.
Base changing
Normally when expressing an integer in a different base, b, it is for printout and the routine returns characters: The columns in the string denote, by position, the multiples of successive powers ob b.For example:
"123" base 10 == 3 * 10**0 + 2 * 10**1 + 1 * 10**2
If the base goes beyond 10 such as in hexadecimal, then letters A... are used to represent numbers beyond 9 as single characters.
We don't want that!
We need to sum the digits so in the _basechange_int function a list is returned of integers to make for easier summation later.
Integer 123 base 10 would return the list [1, 2, 3]
People representation
I am used to generating the Thue-Morse sequence as a string ofupper-case characters where each individual characters corresponds to one persons turn in sharing. as in my original, I will code my new function to have a persons parameter which is a string of different characters, each representing a person.The number of persons becomes the base, b, of my altered statement above.
The algorithm will generate an int that will then need to be represented as a corresponding character from the persons string.
Generate
I decided to code the algorithm as a generator of successive terms from the given persons. islice is my friend :-)Thue-Morse sequence generator from digit counts
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | # -*- coding: utf-8 -*- """ Created on Sat Jan 18 08:34:29 2020 @author: Paddy3118 """ #%% from itertools import count, islice def _basechange_int(num, b): """ Return list of ints representing positive num in base b >>> b = 3 >>> print(b, [_basechange_int(num, b) for num in range(11)]) 3 [[0], [1], [2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2], [1, 0, 0], [1, 0, 1]] >>> """ if num == 0: return [0] result = [] while num != 0: num, d = divmod(num, b) result.append(d) return result[::-1] def _sumdigits_int(numlist, b): "Return the sum of numbers in numlist modulo b, in base b" return sum(numlist) % b def fairshare(persons='ABC'): """ Sequence of fairer sharing between persons We have: "When counting in binary, the digit sum modulo 2 is the Thue-Morse sequence" This computes: When counting base b, the digit sum modulo b is the Thue-Morse sequence of fairer sharing between b people """ base = len(persons) # number base num2person = dict(zip(range(base), persons)) for i in count(): yield num2person[_sumdigits_int(_basechange_int(i, base), base)] if __name__ == '__main__': PERSONS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' for b in [10, 2, 3, 5, 7]: #print(b, [_basechange_int(num, b) for num in range(11)]) print(b, ''.join(islice(fairshare(PERSONS[:b]), 44))) |
Example runs:
In [24]: b = 3; print(b, ''.join(islice(fairshare(PERSONS[:b]), 44))) 3 ABCBCACABBCACABABCCABABCBCABCACABABCCABABCBC In [25]: b = 2; print(b, ''.join(islice(fairshare(PERSONS[:b]), 44))) 2 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBA In [26]:
