Fairshare between two and more
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®)
Factor
<lang factor>USING: formatting kernel math math.parser sequences ;
- nth-fairshare ( n base -- m )
[ >base string>digits sum ] [ mod ] bi ;
- <fairshare> ( n base -- seq )
[ nth-fairshare ] curry { } map-integers ;
{ 2 3 5 11 } [ 25 over <fairshare> "%2d -> %u\n" printf ] each</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 }
Go
<lang go>package main
import (
"fmt" "sort" "strconv" "strings"
)
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 turns(n int, fss []int) string {
m := make(map[int]int)
for _, fs := range fss {
m[fs]++
}
m2 := make(map[int]int)
for _, v := range m {
m2[v]++
}
res := []int{}
sum := 0
for k, v := range m2 {
sum += v
res = append(res, k)
}
if sum != n {
return fmt.Sprintf("only %d have a turn", sum)
}
sort.Ints(res)
res2 := make([]string, len(res))
for i := range res {
res2[i] = strconv.Itoa(res[i])
}
return strings.Join(res2, " or ")
}
func main() {
for _, base := range []int{2, 3, 5, 11} {
fmt.Printf("%2d : %2d\n", base, fairshare(25, base))
}
fmt.Println("\nHow many times does each get a turn in 50000 iterations?")
for _, base := range []int{191, 1377, 49999, 50000, 50001} {
t := turns(base, fairshare(50000, base))
fmt.Printf(" With %d people: %s\n", base, t)
}
}</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] How many times does each get a turn in 50000 iterations? With 191 people: 261 or 262 With 1377 people: 36 or 37 With 49999 people: 1 or 2 With 50000 people: 1 With 50001 people: only 50000 have a turn
Haskell
<lang haskell>import Data.List (intercalate, unfoldr) import Data.Tuple (swap) import Data.Bool (bool)
thueMorse :: Int -> [Int] thueMorse base = baseDigitsSumModBase base <$> [0 ..]
baseDigitsSumModBase :: Int -> Int -> Int baseDigitsSumModBase base n =
mod
(sum
(unfoldr ((bool Nothing . Just . swap . flip quotRem base) <*> (0 <)) n))
base
TEST----------------------------
main :: IO () main =
putStrLn $
fTable
"First 25 fairshare terms for a given number of players:\n"
show
(('[' :) . (++ " ]") . intercalate "," . fmap (justifyRight 2 ' ' . show))
(take 25 . thueMorse)
[2, 3, 5, 11]
DISPLAY--------------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String fTable s xShow fxShow f xs =
unlines $
s :
fmap (((++) . justifyRight w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs
where
w = maximum (length . xShow <$> xs)
justifyRight :: Int -> a -> [a] -> [a] justifyRight n c = (drop . length) <*> (replicate n c ++)</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 ]
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
Add an extension showing the relative fairness correlation of this selection algorithm. An absolutely fair algorithm would have a correlation of 1 for each person (no person has an advantage or disadvantage due to an algorithmic artefact.) This algorithm is fair, and gets better the more iterations are done.
A lower correlation factor corresponds to an advantage, higher to a disadvantage, the closer to 1 it is, the fairer the algorithm. Absolute best possible advantage correlation is 0. Absolute worst is 2.
<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: ', ' }
say "\nRelative fairness of this method. Scaled fairness correlation. The closer to 1.0 each person is, the more fair the selection algorithm is. Gets better with more iterations.";
for <2 3 5 11 39> -> $people {
print "\n$people people: \n";
for $people * 1, $people * 10, $people * 1000 -> $iterations {
my @fairness;
fairshare($people)[^$iterations].kv.map: { @fairness[$^v % $people] += $^k }
my $scale = @fairness.sum / @fairness;
my @range = @fairness.map( { $_ / $scale } );
printf "After round %4d: Best advantage: %-10.8g - Worst disadvantage: %-10.8g - Spread between best and worst: %-10.8g\n",
$iterations/$people, @range.min, @range.max, @range.max - @range.min;
}
}</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 Relative fairness of this method. Scaled fairness correlation. The closer to 1.0 each person is, the more fair the selection algorithm is. Gets better with more iterations. 2 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 After round 1000: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 3 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 0.99310345 - Worst disadvantage: 1.0068966 - Spread between best and worst: 0.013793103 After round 1000: Best advantage: 0.99999933 - Worst disadvantage: 1.0000007 - Spread between best and worst: 1.3337779e-06 5 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 After round 1000: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 11 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 0.99082569 - Worst disadvantage: 1.0091743 - Spread between best and worst: 0.018348624 After round 1000: Best advantage: 0.99999909 - Worst disadvantage: 1.0000009 - Spread between best and worst: 1.8183471e-06 39 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 0.92544987 - Worst disadvantage: 1.0745501 - Spread between best and worst: 0.14910026 After round 1000: Best advantage: 0.99999103 - Worst disadvantage: 1.000009 - Spread between best and worst: 1.7949178e-05
Phix
<lang Phix>function fairshare(integer n, base)
sequence res = repeat(0,n)
for i=1 to n do
integer j = i-1,
t = 0
while j>0 do
t += remainder(j,base)
j = floor(j/base)
end while
res[i] = remainder(t,base)
end for
return {base,res}
end function
constant tests = {2,3,5,11} for i=1 to length(tests) do
printf(1,"%2d : %v\n", fairshare(25, tests[i]))
end for</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}
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