Fairshare between two and more: Difference between revisions
(→{{header|Python}}: Added a functionally composed draft.) |
m (sp.) |
||
| Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
The [[Thue-Morse]] sequence is a |
The [[Thue-Morse]] sequence is a sequence of ones and zeros that if two people |
||
take turns in the given order, the first persons turn for every '0' in the |
take turns in the given order, the first persons turn for every '0' in the |
||
sequence, the second for every '1'; then this is shown to give a fairer, more |
sequence, the second for every '1'; then this is shown to give a fairer, more |
||
Revision as of 00:09, 2 February 2020
The Thue-Morse sequence is a sequence of ones and zeros that if two people take turns in the given order, the first persons turn for every '0' in the sequence, the second for every '1'; then this is shown to give a fairer, more equitable sharing of resources. (Football penalty shoot-outs for example, might not favour the team that goes first as much if the penalty takers take turns according to the Thue-Morse sequence and took 2^n penalties)
The Thue-Morse sequence of ones-and-zeroes can be generated by:
- "When counting in binary, the digit sum modulo 2 is the Thue-Morse sequence"
- Sharing fairly between two or more
Use this method:
- When counting base b, the digit sum modulo b is the Thue-Morse sequence of fairer sharing between b people.
- Task
Counting from zero; using a function/method/routine to express an integer count in base b, Sum the digits modulo b to produce the next member of the Thue-Morse fairshare series for b people.
Show the first 25 terms of the fairshare sequence
- For two people
- For three people
- For five people
- For eleven people
- References
- Non-decimal radices/Convert
- Thue-Morse
- A010060, A053838, A053840: The On-Line Encyclopedia of Integer Sequences® (OEIS®)
Go
<lang go>package main
import "fmt"
func fairshare(n, base int) []int {
res := make([]int, n)
for i := 0; i < n; i++ {
j := i
sum := 0
for j > 0 {
sum += j % base
j /= base
}
res[i] = sum%base
}
return res
}
func main() {
for _, base := range []int{2, 3, 5, 11} {
fmt.Printf("%2d : %2d\n", base, fairshare(25, base))
}
}</lang>
- Output:
2 : [ 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0] 3 : [ 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1] 5 : [ 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3] 11 : [ 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4]
Julia
<lang julia>fairshare(nplayers,len) = [sum(digits(n, base=nplayers)) % nplayers for n in 0:len-1]
for n in [2, 3, 5, 11]
println("Fairshare ", n > 2 ? "among" : "between", " $n people: ", fairshare(n, 25))
end
</lang>
- Output:
Fairshare between 2 people: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] Fairshare among 3 people: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1] Fairshare among 5 people: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3] Fairshare among 11 people: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]
Perl 6
<lang perl6>sub fairshare (\b) { ^∞ .hyper.map: { .polymod( b xx * ).sum % b } }
.say for <2 3 5 11>.map: { .fmt('%2d:') ~ .&fairshare[^25]».fmt('%2d').join: ', ' }
my $iterations = 50_000; say "\nHow many times does each person get a turn in $iterations iterations?";
for 191, 1377 -> $people {
say "With $people people: ", fairshare($people)[^$iterations].Bag.values.sort.unique.join: ' or ';
}</lang>
2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4 How many times does each get a turn in 50000 iterations? With 191 people: 261 or 262 With 1377 people: 36 or 37
Python
Procedural
<lang python>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 fairshare(b=2):
for i in count():
yield sum(_basechange_int(i, b)) % b
if __name__ == '__main__':
for b in (2, 3, 5, 11):
print(f"{b:>2}: {str(list(islice(fairshare(b), 25)))[1:-1]}")</lang>
- Output:
2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4
Functional
<lang python>Fairshare between two and more
from itertools import count, islice from functools import reduce
- thueMorse :: Int -> [Int]
def thueMorse(base):
Thue-Morse sequence for a given base. return map(baseDigitsSumModBase(base), count(0))
- baseDigitsSumModBase :: Int -> Int -> Int
def baseDigitsSumModBase(base):
For any integer n, the sum of its digits
in a given base, modulo that base.
def go(n):
return sum(unfoldl(
lambda x: Nothing() if 0 == x else Just(divmod(x, base))
)(n)) % base
return lambda n: go(n)
- TEST ----------------------------------------------------
- main :: IO ()
def main():
First 25 fairshare terms for a given number of players
print(
fTable(
main.__doc__ + ':\n'
)(repr)(
lambda xs: '[' + ','.join(
[str(x).rjust(2, ' ') for x in xs]
) + ' ]'
)(
compose(take(25), thueMorse)
)([2, 3, 5, 11])
)
- GENERIC -------------------------------------------------
- Just :: a -> Maybe a
def Just(x):
Constructor for an inhabited Maybe (option type) value.
Wrapper containing the result of a computation.
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
- Nothing :: Maybe a
def Nothing():
Constructor for an empty Maybe (option type) value.
Empty wrapper returned where a computation is not possible.
return {'type': 'Maybe', 'Nothing': True}
- compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
Composition, from right to left,
of a series of functions.
return lambda x: reduce(
lambda a, f: f(a),
fs[::-1], x
)
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n,
or xs itself if n > length xs.
return lambda xs: (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
- unfoldl(lambda x: Just(((x - 1), x)) if 0 != x else Nothing())(10)
- -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
def unfoldl(f):
Dual to reduce or foldl.
Where these reduce a list to a summary value, unfoldl
builds a list from a seed value.
Where f returns Just(a, b), a is appended to the list,
and the residual b is used as the argument for the next
application of f.
When f returns Nothing, the completed list is returned.
def go(v):
x, r = v, v
xs = []
while True:
mb = f(x)
if mb.get('Nothing'):
return xs
else:
x, r = mb.get('Just')
xs.insert(0, r)
return xs
return lambda x: go(x)
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
First 25 fairshare terms for a given number of players: 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ] 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ] 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ] 11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]
REXX
<lang rexx>/*REXX program calculates N terms of the fairshare sequence for some group of peoples.*/ parse arg n g /*obtain optional arguments from the CL*/ if n== | n=="," then n= 25 /*Not specified? Then use the default.*/ if g= | g="," then g= 2 3 5 11 /* " " " " " " */
/* [↑] a list of a number of peoples. */
do p=1 for words(g); r= word(g, p) /*traipse through the bases specfiied. */
$= 'base' right(r, 2)': ' /*construct start of the 1─line output.*/
do j=0 for n; $= $ right( sumDigs( base(j, r)) // r, 2)','
end /*j*/ /* [↑] append # (base R) mod R──►$ list*/
say strip($, , ",") /*elide trailing comma from the $ list.*/
end /*p*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ base: parse arg #,b,,y; @= 0123456789abcdefghijklmnopqrstuvwxyz; @@= substr(@,2)
do while #>=b; y= substr(@, (#//b) +1, 1)y; #= #%b; end; return substr(@, #+1, 1)y
/*──────────────────────────────────────────────────────────────────────────────────────*/ sumDigs: parse arg x; !=0; do i=1 for length(x); != !+pos(substr(x,i,1),@@); end; return !</lang>
- output when using the default inputs:
base 2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 base 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 base 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 base 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4
Sidef
<lang ruby>for b in (2,3,5,11) {
say ("#{'%2d' % b}: ", 25.of { .sumdigits(b) % b })
}</lang>
- Output:
2: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] 3: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1] 5: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3] 11: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]
zkl
<lang zkl>fcn fairShare(n,b){
n.pump(List,'wrap(n){ n.toString(b).split("").apply("toInt",b).sum(0)%b })
} foreach b in (T(2,3,5,11)){
println("%2d: %s".fmt(b,fairShare(25,b).pump(String,"%2d ".fmt)));
}</lang>
- Output:
2: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 3: 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 5: 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 11: 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4