def colour_boxes(boxes, tags, colours): """ boxes is a list of pairs (multiplicities of numbers, multiplicities of boxes) tags is a dict from colours to multiplicities of numbers of this colour colours is the list of colours to try for the first box EXAMPLE: ###################################################################### # easy: ###################################################################### sage: tags = {4: (0, 0, 2, 6, 13), 5: (0, 1, 4, 13, 31), 6: (1, 3, 5, 7, 12)} sage: boxes = [((1, 1, 1, 1, 3), 1), ((0, 1, 1, 2, 3), 2), ((0, 1, 1, 1, 4), 1), ((0, 0, 2, 2, 3), 1), ((0, 0, 1, 3, 3), 1), ((0, 0, 1, 2, 4), 3), ((0, 0, 1, 1, 5), 1), ((0, 0, 0, 3, 4), 1), ((0, 0, 0, 2, 5), 2), ((0, 0, 0, 1, 6), 1)] sage: [m for m in colour_boxes(boxes, tags, tags.keys())] [[6, 6, 6, 5, 6, 4, 4, 5, 5, 5, 5, 5, 5, 4], [6, 6, 6, 5, 6, 4, 5, 5, 5, 4, 5, 4, 5, 5], [6, 6, 6, 5, 6, 5, 4, 4, 5, 5, 5, 4, 5, 5], [6, 6, 6, 5, 6, 5, 4, 5, 5, 4, 4, 5, 5, 5]] ###################################################################### # not difficult: ###################################################################### sage: tags = {3: (1, 0, 1, 4, 5, 0, 26, 0, 19, 7), 4: (15, 1, 5, 14, 42, 4, 165, 0, 85, 33), 5: (10, 3, 5, 13, 28, 7, 74, 1, 47, 22)} sage: boxes = [((1, 0, 0, 0, 0, 1, 3, 1, 0, 1), 1), ((1, 1, 0, 1, 1, 0, 2, 0, 1, 0), 1), ((0, 1, 0, 1, 1, 0, 2, 0, 1, 1), 1), ((0, 1, 0, 1, 1, 0, 2, 0, 2, 0), 1), ((0, 1, 0, 1, 1, 0, 3, 0, 1, 0), 1), ((0, 0, 1, 0, 1, 1, 2, 0, 1, 1), 1), ((1, 0, 0, 0, 1, 1, 2, 0, 1, 1), 1), ((1, 0, 0, 0, 1, 1, 3, 0, 0, 1), 1), ((1, 0, 0, 0, 0, 1, 3, 0, 1, 1), 2), ((1, 0, 0, 0, 0, 1, 4, 0, 0, 1), 1), ((1, 0, 1, 0, 2, 0, 1, 0, 2, 0), 1), ((0, 0, 1, 1, 1, 0, 1, 0, 3, 0), 1), ((0, 0, 0, 0, 1, 1, 2, 0, 1, 2), 1), ((0, 0, 1, 0, 2, 0, 1, 0, 2, 1), 1), ((0, 0, 1, 0, 2, 0, 2, 0, 1, 1), 1), ((0, 0, 1, 0, 1, 0, 2, 0, 2, 1), 2), ((0, 0, 0, 0, 1, 1, 3, 0, 1, 1), 2), ((0, 0, 1, 0, 1, 0, 3, 0, 1, 1), 1), ((0, 0, 0, 0, 1, 1, 4, 0, 0, 1), 1), ((0, 0, 1, 0, 2, 0, 2, 0, 2, 0), 1), ((0, 0, 1, 0, 1, 0, 2, 0, 3, 0), 1), ((0, 0, 1, 0, 1, 0, 3, 0, 2, 0), 1), ((1, 0, 0, 2, 0, 0, 2, 0, 2, 0), 1), ((1, 0, 0, 1, 0, 0, 2, 0, 2, 1), 1), ((1, 0, 0, 1, 0, 0, 3, 0, 1, 1), 1), ((1, 0, 0, 1, 1, 0, 2, 0, 2, 0), 2), ((1, 0, 0, 1, 0, 0, 3, 0, 2, 0), 2), ((1, 0, 0, 1, 0, 0, 4, 0, 1, 0), 1), ((1, 0, 0, 0, 2, 0, 2, 0, 1, 1), 1), ((1, 0, 0, 0, 1, 0, 2, 0, 2, 1), 1), ((1, 0, 0, 0, 1, 0, 3, 0, 1, 1), 3), ((1, 0, 0, 0, 1, 0, 4, 0, 0, 1), 1), ((1, 0, 0, 0, 2, 0, 2, 0, 2, 0), 1), ((1, 0, 0, 0, 1, 0, 3, 0, 2, 0), 2), ((1, 0, 0, 0, 1, 0, 4, 0, 1, 0), 1), ((0, 0, 0, 2, 0, 0, 1, 0, 3, 1), 1), ((0, 0, 0, 2, 1, 0, 1, 0, 3, 0), 1), ((0, 0, 0, 2, 0, 0, 2, 0, 3, 0), 1), ((0, 0, 0, 1, 1, 0, 2, 0, 2, 1), 2), ((0, 0, 0, 1, 0, 0, 2, 0, 3, 1), 2), ((0, 0, 0, 1, 0, 0, 3, 0, 2, 1), 1), ((0, 0, 0, 1, 1, 0, 2, 0, 3, 0), 2), ((0, 0, 0, 1, 1, 0, 3, 0, 2, 0), 1), ((0, 0, 0, 1, 0, 0, 3, 0, 3, 0), 2), ((0, 0, 0, 1, 0, 0, 4, 0, 2, 0), 1), ((0, 0, 0, 0, 2, 0, 2, 0, 1, 2), 1), ((0, 0, 0, 0, 2, 0, 3, 0, 0, 2), 1), ((0, 0, 0, 0, 1, 0, 2, 0, 2, 2), 1), ((0, 0, 0, 0, 1, 0, 3, 0, 1, 2), 2), ((0, 0, 0, 0, 0, 0, 3, 0, 2, 2), 1), ((0, 0, 0, 0, 2, 0, 2, 0, 2, 1), 1), ((0, 0, 0, 0, 2, 0, 3, 0, 1, 1), 2), ((0, 0, 0, 0, 1, 0, 3, 0, 2, 1), 5), ((0, 0, 0, 0, 1, 0, 4, 0, 1, 1), 4), ((0, 0, 0, 0, 1, 0, 5, 0, 0, 1), 1), ((0, 0, 0, 0, 0, 0, 3, 0, 3, 1), 1), ((0, 0, 0, 0, 0, 0, 4, 0, 2, 1), 3), ((0, 0, 0, 0, 0, 0, 5, 0, 1, 1), 1), ((0, 0, 0, 0, 2, 0, 3, 0, 2, 0), 1), ((0, 0, 0, 0, 1, 0, 3, 0, 3, 0), 1), ((0, 0, 0, 0, 1, 0, 4, 0, 2, 0), 3), ((0, 0, 0, 0, 1, 0, 5, 0, 1, 0), 1), ((0, 0, 0, 0, 0, 0, 4, 0, 3, 0), 1), ((0, 0, 0, 0, 0, 0, 5, 0, 2, 0), 2), ((0, 0, 0, 0, 0, 0, 6, 0, 1, 0), 1)] sage: keys = [k for (k, v) in sorted(tags.items(), key= lambda (k, v): v.count(0))]; g = colour_boxes(boxes, tags, keys); keys sage: timeit("g.next()") # there are many many many solutions, display only the first 100 sage: [m for m in zip(colour_boxes(boxes, tags, tags.keys()), range(100))] ###################################################################### # the following is the challenge: ###################################################################### sage: tags = {3: (0, 6, 5, 0, 12, 12, 0, 5, 0, 1, 1, 0, 0, 0, 0), 4: (0, 110, 47, 13, 212, 359, 14, 91, 7, 19, 42, 0, 2, 0, 6), 5: (4, 162, 67, 31, 289, 492, 26, 125, 11, 36, 87, 0, 4, 1, 13), 6: (7, 62, 32, 13, 87, 127, 22, 45, 13, 19, 37, 1, 5, 3, 7)} sage: boxes = [((1, 0, 0, 1, 0, 3, 1, 1, 0, 0, 0, 1, 0, 0, 0), 1), ((0, 0, 1, 1, 1, 2, 0, 0, 1, 0, 1, 0, 0, 1, 0), 1), ((0, 0, 1, 0, 1, 2, 0, 1, 1, 0, 1, 0, 0, 1, 0), 1), ((0, 0, 1, 0, 2, 2, 0, 0, 1, 0, 1, 0, 0, 1, 0), 1), ((0, 0, 1, 0, 1, 3, 0, 0, 1, 0, 1, 0, 0, 1, 0), 1), ((1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((1, 0, 0, 1, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((1, 0, 0, 1, 0, 3, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((1, 0, 0, 1, 1, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0), 2), ((1, 0, 0, 1, 0, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 0, 2, 1, 1, 0, 1, 0, 0, 1, 0, 0), 1), ((1, 0, 0, 0, 1, 2, 1, 2, 0, 0, 1, 0, 0, 0, 0), 1), ((1, 0, 0, 0, 1, 3, 1, 1, 0, 0, 1, 0, 0, 0, 0), 2), ((1, 0, 0, 0, 0, 4, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 2, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 1, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 0, 0, 0, 1, 1, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 0, 1, 0, 1, 0, 0, 1, 0, 0), 2), ((0, 2, 0, 0, 0, 3, 0, 1, 0, 1, 0, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 2, 2, 0, 0, 0, 1, 0, 0, 1, 0, 0), 1), ((0, 2, 0, 0, 1, 3, 0, 0, 0, 1, 0, 0, 1, 0, 0), 1), ((0, 1, 1, 0, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1), 1), ((0, 2, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 0, 0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1), 2), ((0, 0, 0, 0, 2, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 0, 0, 0, 1, 3, 1, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 0, 2, 0, 3, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 1, 0, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0, 1), 1), ((0, 1, 1, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 0, 1, 0, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 1, 0, 3, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 1, 0, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 0, 1, 0, 3, 2, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 0, 1, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 2, 0, 0, 1, 1, 0, 1, 0, 0, 2, 0, 0, 0, 1), 1), ((0, 2, 0, 0, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0, 1), 1), ((0, 2, 0, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 2, 0, 0, 1, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 0, 0, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1), 2), ((0, 1, 0, 0, 1, 3, 0, 1, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 2, 0, 0, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 0, 0, 3, 2, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 0, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 1), 1), ((0, 1, 1, 1, 1, 2, 0, 0, 1, 1, 0, 0, 0, 0, 0), 1), ((0, 0, 2, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 1, 1, 2, 0, 0, 1, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 1, 1, 2, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 1, 1, 3, 0, 1, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 1, 2, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0), 2), ((0, 0, 1, 1, 1, 4, 0, 0, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 0, 1, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 2, 0, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 2, 0, 2, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 2, 0, 2, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 1, 2, 0, 1, 1, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 0, 1, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 1, 3, 0, 0, 1, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 1, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0), 2), ((0, 1, 1, 0, 1, 3, 0, 1, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 2, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0), 2), ((0, 1, 1, 0, 1, 4, 0, 0, 1, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 1, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 0, 3, 1, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 1, 0, 1, 0, 3, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 0, 1, 1, 3, 1, 1, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 0, 0, 1, 0, 4, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 2, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 1, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 1, 2, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 1, 2, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 1, 3, 0, 1, 0, 1, 0, 0, 0, 0, 0), 3), ((0, 1, 0, 1, 0, 4, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 2, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 2, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 1, 0, 1, 1, 4, 0, 0, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 0, 2, 1, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 1, 1, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 1, 1, 1, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 1, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 0, 1, 1, 1, 4, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 1, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 1, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0), 3), ((0, 1, 0, 1, 0, 4, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 1, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 1, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 1, 0, 1, 1, 4, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 2, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 3, 1, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 2, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 0, 2, 1, 2, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 2, 1, 2, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 0, 3, 1, 2, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 0, 0, 0, 1, 3, 1, 2, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 0, 0, 0, 0), 4), ((0, 1, 0, 0, 0, 4, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 2, 3, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 1, 4, 1, 1, 0, 0, 1, 0, 0, 0, 0), 3), ((0, 0, 0, 0, 0, 5, 1, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 1, 2, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 0, 3, 1, 2, 0, 0, 0, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 1, 3, 1, 2, 0, 0, 0, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 1, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 2, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 0, 5, 1, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 3, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 2, 1, 0, 1, 0, 2, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 3, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 1, 2, 0, 1, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 0, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 1, 1, 0, 2, 2, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 3, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 1, 1, 0, 3, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 2, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 0, 1, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 2, 2, 0, 0, 0, 1, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 0, 2, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 2, 2, 0, 2, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 2, 2, 0, 1, 0, 1, 0, 0, 0, 0, 0), 4), ((0, 2, 0, 0, 1, 3, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 3, 2, 0, 1, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 2, 3, 0, 1, 0, 1, 0, 0, 0, 0, 0), 3), ((0, 1, 0, 0, 1, 4, 0, 1, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 3, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 2, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 3, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 2, 4, 0, 0, 0, 1, 0, 0, 0, 0, 0), 1), ((0, 0, 3, 0, 3, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 3, 0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 2, 0, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 2, 0, 3, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 2, 0, 3, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 0, 2, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 2, 0, 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 2, 0, 3, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 2, 0, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 2, 0, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 2, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 1, 2, 0, 1, 0, 0, 2, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 1, 2, 0, 2, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 2, 2, 0, 2, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0), 4), ((0, 1, 1, 0, 1, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 0, 1, 0, 2, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0), 4), ((0, 0, 1, 0, 1, 4, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 3, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 1, 1, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 3), ((0, 0, 1, 0, 3, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 2, 4, 0, 0, 0, 0, 1, 0, 0, 0, 0), 3), ((0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 1, 5, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 2, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 3, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 3, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 1, 1, 0, 2, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 0, 1, 0, 3, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 0, 1, 0, 2, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 1, 0, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 1, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 1, 1, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 0, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 1, 0, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 0, 1, 0, 0, 2, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 2, 0, 2, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 0, 3, 0, 2, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 2, 2, 0, 2, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 3, 0, 2, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 2, 0, 0, 1, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0), 4), ((0, 1, 0, 0, 2, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0), 5), ((0, 1, 0, 0, 1, 4, 0, 1, 0, 0, 1, 0, 0, 0, 0), 4), ((0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 0, 5, 0, 1, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 2), ((0, 1, 0, 0, 3, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 2, 4, 0, 0, 0, 0, 1, 0, 0, 0, 0), 3), ((0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 5, 0, 0, 0, 0, 1, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 1, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 2, 0, 0, 0, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 2, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 1, 0, 0, 1, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 0, 0, 0, 3, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 2, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 2, 0, 0, 1, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 1, 0, 0, 3, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 1, 0, 0, 2, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0), 9), ((0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 5, 0, 1, 0, 0, 0, 0, 0, 0, 0), 5), ((0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 0, 6, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 3, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 0, 0, 0, 2, 5, 0, 1, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 1, 6, 0, 1, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 2, 0, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0), 3), ((0, 1, 0, 0, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0), 4), ((0, 1, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 1, 0, 0, 1, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0), 2), ((0, 0, 0, 0, 2, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0), 2), ((0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1), ((0, 0, 0, 0, 1, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1)] # a check that we have for every item of each number a tag: sage: sum([vector(m) for m in tags.values()]) (11, 340, 151, 57, 600, 990, 62, 266, 31, 75, 167, 1, 11, 4, 26) sage: sum([vector(m[0])*m[1] for m in boxes]) (11, 340, 151, 57, 600, 990, 62, 266, 31, 75, 167, 1, 11, 4, 26) """ if not boxes and not tags: yield [] elif boxes and tags: # consider the first box (item_multiplicities, box_multiplicity) = boxes[0] while colours: # try the first allowed colour colour = colours[0] # subtract tag_multiplicities from item_multiplicities # success = True if and only if the result is non-negative, # empty = True, if success = True and the difference is zero success = True empty = True tag_multiplicities = tags[colour] new_tag_multiplicities = [] for (o,c) in zip(item_multiplicities, tag_multiplicities): new = c-o if new < 0: success = False break else: new_tag_multiplicities += [new] if new > 0: empty = False if success: # removing empty colours saves us from considering # them over and over again if empty: del tags[colour] else: tags[colour] = tuple(new_tag_multiplicities) if box_multiplicity == 1: # we consider the next set of rows, all colours # are allowed again new_colours = sorted(tags.keys(), key= lambda k: (tags[k]).count(0)) maps = colour_boxes(boxes[1:], tags, new_colours) for f in maps: yield [colour]+f else: # we consider the next box in this set of boxes, # so we only allow colours that are at least as # large as the colour we just coloured with if empty: new_colours = colours[1:] else: new_colours = colours boxes[0] = (item_multiplicities, box_multiplicity-1) maps = colour_boxes(boxes, tags, new_colours) for f in maps: yield [colour]+f boxes[0] = (item_multiplicities, box_multiplicity) tags[colour] = tag_multiplicities # remove the first colour from the list of allowed colours colours = colours[1:]