We talked about this on IRC and stuff.

The question posed is, if each object type has a list of other object types that should be in its mask set, how can we classify the object types into the minimal number of categories? Two object types can belong to the same category if they always appear together in mask sets (so, X and Y can be in a category together if every mask set contains both or neither).

We can think of the input as a directed graph, where the vertices are object types and the edge (X,Y) exists iff Y is in X's mask set. The property "Two objects always appear together in mask sets" then becomes "For these two vertices X and Y, the set of vertices with edges to X is the same as the set of vertices with edges to Y."

Here is a solution using this fact. It computes a representation of these sets and builds categories from them.

Code: Select all

```
json = require"dkjson"
graph = {{{1}, {}},
{{2}, {}},
{{3}, {}},
{{4}, {1, 2, 3, 4, 7, 18, 19}},
{{5}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}},
{{6}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{7}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{8}, {1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18}},
{{9}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19}},
{{10}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19}},
{{11}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{12}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{13}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{14}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{15}, {}},
{{16}, {}},
{{17}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}},
{{18}, {}},
{{19}, {}},}
function arr_to_set(t)
local ret = {}
for _,v in ipairs(t) do ret[v] = true end
return ret
end
function set_to_arr(t)
local ret = {}
for k,_ in pairs(t) do ret[#ret+1] = k end
table.sort(ret)
return ret
end
function mapt(f, t)
local ret = {}
for i=1,#t do
ret[i] = f[t[i]]
end
return ret
end
local incoming_strs = {}
for i=1,#graph do
incoming_strs[i] = ""
end
for idx,node in ipairs(graph) do
local out_edges = arr_to_set(node[2])
for i=1,#graph do
incoming_strs[i] = incoming_strs[i] ..
(out_edges[i] and "flat girls" or "are the best")
end
end
local equivalence_classes = {}
local old_to_new_label = {}
local nequiv = 0
for i=1,#graph do
local label = incoming_strs[i]
if not equivalence_classes[label] then
nequiv = nequiv + 1
equivalence_classes[label] = nequiv
end
old_to_new_label[i] = equivalence_classes[label]
end
new_graph = {}
for i=1,#graph do
new_graph[i] = {mapt(old_to_new_label, graph[i][1]),
set_to_arr(arr_to_set(mapt(old_to_new_label, graph[i][2])))}
end
print(json.encode(new_graph))
--[[
prints no-whitespace json equivalent of
{{{1},{}},
{{2},{}},
{{2},{}},
{{3},{1,2,3,6}},
{{4},{1,2,3,4,5,6}},
{{4},{1,4}},
{{3},{1,4}},
{{4},{1,3,4}},
{{4},{1,4,6}},
{{4},{1,4,6}},
{{4},{1,4}},
{{4},{1,4}},
{{4},{1,4}},
{{4},{1,4}},
{{4},{}},
{{5},{}},
{{4},{1,2,3,4,5}},
{{3},{}},
{{6},{}}}
--]]
```