*****************************************************************************
* www.FindStat.org - The Combinatorial Statistic Finder *
* *
* Copyright (C) 2019 The FindStatCrew <info@findstat.org> *
* *
* This information is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *
*****************************************************************************
-----------------------------------------------------------------------------
Statistic identifier: St000681
-----------------------------------------------------------------------------
Collection: Integer partitions
-----------------------------------------------------------------------------
Description: The Grundy value of Chomp on Ferrers diagrams.
Players take turns and choose a cell of the diagram, cutting off all cells below and to the right of this cell in English notation. The player who is left with the single cell partition looses. The traditional version is played on chocolate bars, see [1].
This statistic is the Grundy value of the partition, that is, the smallest non-negative integer which does not occur as value of a partition obtained by a single move.
-----------------------------------------------------------------------------
References: [1] [[wikipedia:Chomp]]
-----------------------------------------------------------------------------
Code:
@cached_function
def statistic(pi):
"""Return the Grundy value of the Ferrers diagram pi for Chomp.
sage: statistic(Partition([1]))
0
sage: statistic(Partition([1,1]))
1
sage: statistic(Partition([2,1]))
0
"""
def children(la):
for row, col in la.cells():
if (row,col) != (0,0):
yield Partition(la[:row] + [min(r, col) for r in la[row:]])
pi = Partition(pi)
if pi.size() == 0:
return
elif pi.size() == 1:
return 0
else:
l = [statistic(la) for la in children(pi)]
i = 0
while i in l:
i += 1
return i
-----------------------------------------------------------------------------
Statistic values:
[2] => 1
[1,1] => 1
[3] => 2
[2,1] => 0
[1,1,1] => 2
[4] => 3
[3,1] => 3
[2,2] => 2
[2,1,1] => 3
[1,1,1,1] => 3
[5] => 4
[4,1] => 2
[3,2] => 0
[3,1,1] => 0
[2,2,1] => 0
[2,1,1,1] => 2
[1,1,1,1,1] => 4
[6] => 5
[5,1] => 5
[4,2] => 4
[4,1,1] => 1
[3,3] => 4
[3,2,1] => 1
[3,1,1,1] => 1
[2,2,2] => 4
[2,2,1,1] => 4
[2,1,1,1,1] => 5
[1,1,1,1,1,1] => 5
[7] => 6
[6,1] => 4
[5,2] => 3
[5,1,1] => 6
[4,3] => 0
[4,2,1] => 5
[4,1,1,1] => 0
[3,3,1] => 3
[3,2,2] => 3
[3,2,1,1] => 5
[3,1,1,1,1] => 6
[2,2,2,1] => 0
[2,2,1,1,1] => 3
[2,1,1,1,1,1] => 4
[1,1,1,1,1,1,1] => 6
[8] => 7
[7,1] => 7
[6,2] => 6
[6,1,1] => 7
[5,3] => 6
[5,2,1] => 7
[5,1,1,1] => 7
[4,4] => 5
[4,3,1] => 4
[4,2,2] => 0
[4,2,1,1] => 1
[4,1,1,1,1] => 7
[3,3,2] => 1
[3,3,1,1] => 0
[3,2,2,1] => 4
[3,2,1,1,1] => 7
[3,1,1,1,1,1] => 7
[2,2,2,2] => 5
[2,2,2,1,1] => 6
[2,2,1,1,1,1] => 6
[2,1,1,1,1,1,1] => 7
[1,1,1,1,1,1,1,1] => 7
[9] => 8
[8,1] => 6
[7,2] => 5
[7,1,1] => 4
[6,3] => 3
[6,2,1] => 3
[6,1,1,1] => 6
[5,4] => 0
[5,3,1] => 1
[5,2,2] => 1
[5,2,1,1] => 0
[5,1,1,1,1] => 0
[4,4,1] => 6
[4,3,2] => 5
[4,3,1,1] => 2
[4,2,2,1] => 2
[4,2,1,1,1] => 0
[4,1,1,1,1,1] => 6
[3,3,3] => 5
[3,3,2,1] => 5
[3,3,1,1,1] => 1
[3,2,2,2] => 6
[3,2,2,1,1] => 1
[3,2,1,1,1,1] => 3
[3,1,1,1,1,1,1] => 4
[2,2,2,2,1] => 0
[2,2,2,1,1,1] => 3
[2,2,1,1,1,1,1] => 5
[2,1,1,1,1,1,1,1] => 6
[1,1,1,1,1,1,1,1,1] => 8
[10] => 9
[9,1] => 9
[8,2] => 8
[8,1,1] => 5
[7,3] => 8
[7,2,1] => 8
[7,1,1,1] => 5
[6,4] => 7
[6,3,1] => 6
[6,2,2] => 8
[6,2,1,1] => 2
[6,1,1,1,1] => 1
[5,5] => 7
[5,4,1] => 5
[5,3,2] => 0
[5,3,1,1] => 5
[5,2,2,1] => 5
[5,2,1,1,1] => 1
[5,1,1,1,1,1] => 1
[4,4,2] => 7
[4,4,1,1] => 7
[4,3,3] => 6
[4,3,2,1] => 1
[4,3,1,1,1] => 5
[4,2,2,2] => 7
[4,2,2,1,1] => 5
[4,2,1,1,1,1] => 2
[4,1,1,1,1,1,1] => 5
[3,3,3,1] => 6
[3,3,2,2] => 7
[3,3,2,1,1] => 0
[3,3,1,1,1,1] => 8
[3,2,2,2,1] => 5
[3,2,2,1,1,1] => 6
[3,2,1,1,1,1,1] => 8
[3,1,1,1,1,1,1,1] => 5
[2,2,2,2,2] => 7
[2,2,2,2,1,1] => 7
[2,2,2,1,1,1,1] => 8
[2,2,1,1,1,1,1,1] => 8
[2,1,1,1,1,1,1,1,1] => 9
[1,1,1,1,1,1,1,1,1,1] => 9
[11] => 10
[10,1] => 8
[9,2] => 7
[9,1,1] => 10
[8,3] => 5
[8,2,1] => 4
[8,1,1,1] => 4
[7,4] => 3
[7,3,1] => 5
[7,2,2] => 7
[7,2,1,1] => 7
[7,1,1,1,1] => 2
[6,5] => 0
[6,4,1] => 1
[6,3,2] => 9
[6,3,1,1] => 1
[6,2,2,1] => 1
[6,2,1,1,1] => 8
[6,1,1,1,1,1] => 0
[5,5,1] => 8
[5,4,2] => 3
[5,4,1,1] => 1
[5,3,3] => 3
[5,3,2,1] => 2
[5,3,1,1,1] => 2
[5,2,2,2] => 2
[5,2,2,1,1] => 2
[5,2,1,1,1,1] => 8
[5,1,1,1,1,1,1] => 2
[4,4,3] => 8
[4,4,2,1] => 4
[4,4,1,1,1] => 2
[4,3,3,1] => 4
[4,3,2,2] => 4
[4,3,2,1,1] => 2
[4,3,1,1,1,1] => 1
[4,2,2,2,1] => 1
[4,2,2,1,1,1] => 1
[4,2,1,1,1,1,1] => 7
[4,1,1,1,1,1,1,1] => 4
[3,3,3,2] => 8
[3,3,3,1,1] => 3
[3,3,2,2,1] => 3
[3,3,2,1,1,1] => 9
[3,3,1,1,1,1,1] => 7
[3,2,2,2,2] => 8
[3,2,2,2,1,1] => 1
[3,2,2,1,1,1,1] => 5
[3,2,1,1,1,1,1,1] => 4
[3,1,1,1,1,1,1,1,1] => 10
[2,2,2,2,2,1] => 0
[2,2,2,2,1,1,1] => 3
[2,2,2,1,1,1,1,1] => 5
[2,2,1,1,1,1,1,1,1] => 7
[2,1,1,1,1,1,1,1,1,1] => 8
[1,1,1,1,1,1,1,1,1,1,1] => 10
[12] => 11
[11,1] => 11
[10,2] => 10
[10,1,1] => 11
[9,3] => 10
[9,2,1] => 6
[9,1,1,1] => 11
[8,4] => 9
[8,3,1] => 8
[8,2,2] => 6
[8,2,1,1] => 6
[8,1,1,1,1] => 3
[7,5] => 9
[7,4,1] => 7
[7,3,2] => 3
[7,3,1,1] => 9
[7,2,2,1] => 8
[7,2,1,1,1] => 9
[7,1,1,1,1,1] => 3
[6,6] => 8
[6,5,1] => 4
[6,4,2] => 0
[6,4,1,1] => 8
[6,3,3] => 0
[6,3,2,1] => 4
[6,3,1,1,1] => 0
[6,2,2,2] => 0
[6,2,2,1,1] => 0
[6,2,1,1,1,1] => 1
[6,1,1,1,1,1,1] => 3
[5,5,2] => 5
[5,5,1,1] => 2
[5,4,3] => 7
[5,4,2,1] => 6
[5,4,1,1,1] => 6
[5,3,3,1] => 1
[5,3,2,2] => 1
[5,3,2,1,1] => 1
[5,3,1,1,1,1] => 0
[5,2,2,2,1] => 6
[5,2,2,1,1,1] => 0
[5,2,1,1,1,1,1] => 9
[5,1,1,1,1,1,1,1] => 3
[4,4,4] => 9
[4,4,3,1] => 1
[4,4,2,2] => 1
[4,4,2,1,1] => 1
[4,4,1,1,1,1] => 0
[4,3,3,2] => 1
[4,3,3,1,1] => 1
[4,3,2,2,1] => 6
[4,3,2,1,1,1] => 4
[4,3,1,1,1,1,1] => 8
[4,2,2,2,2] => 2
[4,2,2,2,1,1] => 8
[4,2,2,1,1,1,1] => 9
[4,2,1,1,1,1,1,1] => 6
[4,1,1,1,1,1,1,1,1] => 11
[3,3,3,3] => 9
[3,3,3,2,1] => 7
[3,3,3,1,1,1] => 0
[3,3,2,2,2] => 5
[3,3,2,2,1,1] => 0
[3,3,2,1,1,1,1] => 3
[3,3,1,1,1,1,1,1] => 6
[3,2,2,2,2,1] => 4
[3,2,2,2,1,1,1] => 7
[3,2,2,1,1,1,1,1] => 8
[3,2,1,1,1,1,1,1,1] => 6
[3,1,1,1,1,1,1,1,1,1] => 11
[2,2,2,2,2,2] => 8
[2,2,2,2,2,1,1] => 9
[2,2,2,2,1,1,1,1] => 9
[2,2,2,1,1,1,1,1,1] => 10
[2,2,1,1,1,1,1,1,1,1] => 10
[2,1,1,1,1,1,1,1,1,1,1] => 11
[1,1,1,1,1,1,1,1,1,1,1,1] => 11
-----------------------------------------------------------------------------
Created: Jan 05, 2017 at 20:33 by Martin Rubey
-----------------------------------------------------------------------------
Last Updated: Jan 05, 2017 at 20:33 by Martin Rubey