Rule Enumeration Code
Rule Enumeration Code
Parameters of enumeration (assuming binary relations)
Parameters of enumeration (assuming binary relations)
◼
Total number of relations (σ)
◼
Number of distinct symbols (s)
◼
(Number of rules (k))
◼
(Distribution of number of relations on LHS and RHS of rules)
This gives all possible “shapes” for σ relations:
In[]:=
allshapes[σ_]:=DeleteDuplicates[Sort/@(Partition[#,2]&/@Flatten[Permutations/@IntegerPartitions[σ,{0,σ,2}],1])]
Given a shape, we have to actually “spray symbols” in all possible ways:
In[]:=
rcases[lr:{_,_},s_Integer]:=Apply[Rule,(Partition[#,2]&/@TakeList[#,2lr])&/@Tuples[Range[s],2Total[lr]],{1}]
Find the minimal representative based on relabeling symbols and permuting relations:
In[]:=
mincase[rule_,s_Integer]:=First[Sort[Map[Sort,(rule/.#)&/@(Thread[Range[s]#]&/@Permutations[Range[s]]),{2}]]]
For a given rule shape, find all minimal cases:
In[]:=
RuleShapeToCases[lr:{_,_},s_Integer]:=Union[mincase[#,s]&/@rcases[lr,s]]
In[]:=
RuleShapeListToCases[llr_List,s_Integer]:=DeleteDuplicates[Map[Sort,Flatten[Apply[Outer[List,##,2]&,RuleShapeToCases[#,s]&/@llr],1],{2}]]
Note: there may be cases where an identical rule is repeated in a single ruleset.
In[]:=
RuleShapeListToCases[{{1,2},{2,1}},2]
Out[]=
In[]:=
allshapes[2]
Out[]=
{{{1,1}}}
In[]:=
allshapes[4]
Out[]=
{{{3,1}},{{1,3}},{{2,2}},{{1,1},{1,1}}}
In[]:=
RuleShapeListToCases[{{3,1}},2]
Out[]=
In[]:=
EnumerateRules[σ_Integer,s_Integer]:=Flatten[RuleShapeListToCases[#,s]&/@allshapes[σ],1]