Rule Enumeration Code

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]