People who do combinatorics (like me) are often faced with the following problem:
For a list of combinatorial objects (vectors, permutations graphs,etc.), we know what multi-set of values it generates under some unknown map we wish to explore.
For example: perhaps we know that the four vectors $\{123,213,231,312\}$ generates the list $\{1,2,0,2\}$, but we don't know which permutation give rise to which value. However, if we have several such subset-relations, one can sometimes deduce exactly what value an object gives. Perhaps we also know $\{123, 321 \}$ gives $\{3,0\}$. Since $123$ are common elements in both, and $0$ is the only common statistic, we know that $123$ is responsible for the $0$.
Sometimes, it is not possible to deduce such relations uniquely, but if we have the multiset correspondences $S_1 \to M_1$ and $S_2 \to M_2$, and $S_1 \subseteq S_2$, then we have the refined correspondence $S_1 \cap S_2 \to M_1 \setminus M_2$ as multisets.
Question: Given a list of such multi-set correspondences, produce a new list of maximally refined multiset relations. We also wish to make this minimal, in the sense that if $S_1 \to M_1$ and $S_2 \to M_2$ is in the list, then $S_1 \cup S_2 \to M_1 \cup M_2$ is not in the output, since this is an implicit weaker relation.
There can of course be a contradiction in the input, and then the program should stop and alert about this.
EDIT: Below is my implementation so far, but I suspect it can be improved a lot.
The basic idea is to store the multiset of associated values as a sparse vector, since this makes some operation easier to perform.
MultiSetToSparseArray[ms_List, dim_] :=
SparseArray[#1 -> #2 & @@@ Tally[ms], {dim}];
SparseArrayToMultiSet[spA_] :=
Join @@ Table[
ConstantArray[r[[1, 1]], r[[2]]], {r, Most[ArrayRules[spA]]}];
RefineSubsetsRelations[subsetRelations_List] :=
Module[{i, j, s1, s2, m1, m2, int, com,
newRel, foundNew = True, relations = subsetRelations, sa, dim},
(* Maximal possible statistic. *)
dim = Max[Last /@ relations];
(* Sort input subsets. *)
relations = {Sort@#1, MultiSetToSparseArray[#2, dim]} & @@@
relations;
While[ foundNew == True,
foundNew = False;
(* Sort by size. *)
relations = Select[relations, Length[#1] > 0 &];
relations = SortBy[Union@relations, Length[#[[1]]] &];
Do[
If[relations[[i]] === relations[[j]] ,
Continue[]
];
{s1, m1} = relations[[i]];
{s2, m2} = relations[[j]];
int = Intersection[s1, s2];
If[ Length[s1] == 0 || Length[s2] == 0,
Continue[]
];
If[ Length[int] == Length[s1],
If[Min[m2 - m1] < 0,
Print["Contradicion in RefineSubsetsRelations",
Complement[s2, s1], ArrayRules[m2 - m1]];
Abort[];
];
(* Replace the more general rule with a specific one. *)
relations[[j]] = {Complement[s2, s1], m2 - m1};
foundNew = True;
Continue[]
];
(* Only one common value,
this means that the intersection only takes this value. *)
com = Intersection[SparseArrayToMultiSet[m1],
SparseArrayToMultiSet[m2]];
If[ Length[com] == 1 && Length[int] > 0,
com = First[com];
sa = SparseArray[com -> Length[int], dim];
newRel = {int, sa};
relations[[i]] = {Complement[s1, int], m1 - sa};
relations[[j]] = {Complement[s2, int], m2 - sa};
foundNew = True;
Continue[]
];
, {i, Length@relations}, {j, i + 1, Length@relations}];
];
{#1, SparseArrayToMultiSet[#2]} & @@@ relations
];
EDIT 2: As for motivation, and lots of examples, see the web site findstat.org This is used to look in a database for combinatorial maps that appear in literature. My example above is borrowed for the number of inversions of a permutation. However, in order to use findstat.org, we need to know which value to assign to each combinatorial object. However, in many research problems, we can only obtain data as above. A famous example is the Kostka-Foulkes polynoials, which basically encodes exactly such a mapping from a subset of combinatorial objects (semi-standard Young tableaux) to a multiset of non-negative integers. By some trickery and extra assumptions, one can get several such intersecting subsets. Once one have some singletons, it is possible to start making conjectures of what the map actually is.
EXAMPLE INPUT
Here are 10 equations, where each subset is of size 3, (objects are permutations, or plain vectors if you like), and the multi-set of values is given as the second entry in the pair {setOfPermutations,multiSetOfvalues}.
{
{{{{3, 1, 2}, {1, 3, 2}, {2, 1, 3}}, {1, 1, 2}}},
{{{{3, 2, 1}, {3, 1, 2}, {1, 3, 2}}, {1, 2, 3}}},
{{{{1, 3, 2}, {3, 1, 2}, {2, 3, 1}}, {1, 2, 2}}},
{{{{3, 2, 1}, {2, 3, 1}, {1, 3, 2}}, {1, 2, 3}}},
{{{{1, 3, 2}, {3, 2, 1}, {1, 2, 3}}, {0, 1, 3}}},
{{{{3, 2, 1}, {1, 3, 2}, {2, 1, 3}}, {1, 1, 3}}},
{{{{1, 3, 2}, {3, 2, 1}, {3, 1, 2}}, {1, 2, 3}}},
{{{{2, 3, 1}, {2, 1, 3}, {1, 2, 3}}, {0, 1, 2}}},
{{{{3, 2, 1}, {2, 3, 1}, {3, 1, 2}}, {2, 2, 3}}},
{{{{1, 3, 2}, {2, 3, 1}, {3, 1, 2}}, {1, 2, 2}}}
}
