Canonical Rule Signature [EdP]
Parameters of enumeration
Parameters of enumeration
◼
Number of distinct symbols (s)
◼
Total number of relations (σ)
◼
(Number of rules (k))
◼
(Distribution of number of relations on LHS and RHS of rules)
A typical instance of (with ) might be:
2
2
3
2
σ
k
{{1,1},{2,1}}{{2,1},{2,2},{2,2}}
The ordering inside the outer list doesn’t matter.
The ordering within each sublist does matter.
The names of the symbols don’t matter.
Formulas for the total counts would be nice, but are not essential.
The ordering within each sublist does matter.
The names of the symbols don’t matter.
Formulas for the total counts would be nice, but are not essential.
Examples of RuleSignatures and Rules
Examples of RuleSignatures and Rules
Initialization
Initialization
Tupling[{σ_,k_},s_]:=Tuples[Tuples[Range[s],{k}],{σ}];
CanonRule[rule_,s_]:=First[Sort[Sort[(rule/.#)]&/@(Thread[Range[s]#]&/@Permutations[Range[s]])]];
PutInStandardOrder[rule_Rule]:=Module[{alphabet,s,t,convertedrule,parts},alphabet=Union[Flatten[Table[rule[[n]],{n,1,Length[rule]}]]];s=Length[alphabet];convertedrule=rule/.Thread[alphabetRange[s]];parts=Table[SortBy[convertedrule[[n]],{-Length[#],-PadRight[Length/@Split[#],Length[#]],#}&],{n,1,2}];convertedrule=convertedrule/.Thread[DeleteDuplicates[Flatten[parts]]Range[s]];parts=Table[SortBy[convertedrule[[n]],{-Length[#],#}&],{n,1,2}];Rule@@parts]
CanonRule[rule_Rule]:=Module[{standard,r,s,partR,orderstart,ordering,parts},standard=PutInStandardOrder[rule];{r,s}=Table[Max[Flatten[standard[[n]]]],{n,1,Length[standard]}];If[s<r,s=r];partR=First[Sort[{SortBy[(standard[[1]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[r]#]&/@Permutations[Range[r]])]];orderstart=partR[[2]];ordering=Switch[s-r,0,orderstart,1,Append[orderstart,s],_,Last[First[Sort[{SortBy[(standard[[2]]/.#),{-Length[#],#}&],Last/@#}&/@(Thread[Range[s]Join[orderstart,#]]&/@Permutations[Range[r+1,s]])]]]];parts=Table[SortBy[standard[[n]]/.Thread[Range[s]ordering],{-Length[#],#}&],{n,1,2}];Rule@@parts];
RuleSignatureRandom[rulesignature_Rule,s_Integer]:=CanonRule[Rule@@Table[Flatten[RandomInteger[{1,s},#]&/@rulesignature[[n]],1],{n,1,Length[rulesignature]}]];
StandardOrderCount[len_,s_]:=Sum[StirlingS2[len,j],{j,1,s}];
GrowStandardOrder[order_]:=Module[{max},max=Max[order];Append[order,#]&/@Range[max+1]];
SupportSizeEstimate[samples_,distincts_]:=N(samplesdistincts)distinctsProductLog-+samples;
samplesExp[-samples/distincts]
distincts
Initialization Examples
Initialization Examples
Union[CanonRule[#,2]&/@Tupling[{2,2},2]]
{{{1,1},{1,1}},{{1,1},{1,2}},{{1,1},{2,1}},{{1,1},{2,2}},{{1,2},{1,2}},{{1,2},{2,1}}}
PutInStandardOrder[{{a,e,d},{d,c},{c,b},{b,a}}{{a,b}}]
{{1,2,3},{3,5},{4,1},{5,4}}{{1,4}}
CanonRule[{{a,e,d},{d,c},{c,b},{b,a}}{{}}]
{{1,2,3},{3,4},{4,5},{5,1}}{{}}
CanonRule[{{2,4},{4,5,1},{1,3},{3,2}}{{}}]
{{1,2,3},{3,4},{4,5},{5,1}}{{}}
PutInStandardOrder[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}}]
{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}
CanonRule[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}}]
{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}
CanonRule[{{2,3,3}}{{3,2,2},{2,1,1}}]
{{1,2,2}}{{1,3,3},{2,1,1}}
CanonRule[{{2,2,1},{2,2,2}}{{1,1,3},{1,1,1},{2,1,2},{3,3,2}}]
{{1,1,1},{1,1,2}}{{1,2,1},{2,2,2},{2,2,3},{3,3,1}}
CanonRule[{{0,1},{0,2},{0,3}}{{4,5},{5,4},{4,6},{6,4},{5,6},{6,5},{4,1},{5,2},{6,3},{1,6},{3,4}}]
{{1,2},{1,3},{1,4}}{{2,5},{4,6},{5,4},{5,6},{5,7},{6,2},{6,5},{6,7},{7,3},{7,5},{7,6}}
CanonRule[{{2,5},{5,2},{2,3,1},{5,6,4}}{{7,11},{8,9},{9,8},{10,14},{11,7},{12,13},{13,12},{14,10},{1,8,7},{4,12,11},{9,10,3},{13,14,6}}]
{{1,2,3},{4,5,6},{1,4},{4,1}}{{3,7,8},{6,9,10},{11,12,2},{13,14,5},{7,11},{8,10},{9,13},{10,8},{11,7},{12,14},{13,9},{14,12}}
Table[RuleSignatureRandom[{{2,3},{2,2}}{{4,3},{8,2}},12],{10}]
Table[RuleSignatureRandom[{{2,3}}{{3,2}},2],{12}]
Table[RuleSignatureRandom[{{2,3}}{{3,2}},4],{12}]
Sample a hundred thousand rules of a complex type and count the distinct canonicalizations.
Length[Union[Table[RuleSignatureRandom[{{3,3}}{{3,3}},3],{100000}]]]
97658
Based on sample size and distinct values, estimate the total number of canonical rules.
Ceiling[SupportSizeEstimate[100000,97658]]
2101463
Calculate the number of birthdays for Saturn but keep the number secret:
saturnbirthdays=Ceiling;
Count the number of distinct results in 50000 random birthdays on Saturn:
Length[Union[RandomInteger[{1,saturnbirthdays},{50000}]]]
21265
With sample size 50000 and 21265 distinct results estimate how many days per year there are on Saturn:
Bell Numbers -- First Part of the Rule
Bell Numbers -- First Part of the Rule
There might be some method for indexing.
LexicographicIndex
LexicographicIndex
IndexedSubset
IndexedSubset
Give the index of a subset or return the subset with that index
The following 3-subset ordering can be extended to infinity:
The function returns the same subsets in the same order:
The function can return subsets of a large index:
Applying the function to a subset returns the index:
Any strictly increasing list of integers can be considered as a subset with a unique index:
The index above generates a unique 10-subset:
The structure of 3-subsets in 3D:
Find the trillionth number with binary weight eight:
Find the index of an eight term subset:
IndexedOrderedTuple
IndexedOrderedTuple
The following ordered 3-tuple sequence can be extended to infinity:
The same sequence of ordered 3-tuples can be obtained from ordered subsets:
The function returns the same ordered tuples in the same sequence:
The function can return ordered tuples of a large index:
Applying the function to an ordered tuple returns the index:
Any increasing list of integers can be considered as a ordered tuple with a unique index:
The index above generates a unique ordered 10-tuple:
Here are some ordered 2-tuples with their indices to show their stucture:
The structure of ordered 3-tuples in 3D:
IndexedTuple (not solved)
IndexedTuple (not solved)
This sort of ordering could be applied to Tuples
Old Canonical Parts
Old Canonical Parts
Binary
Binary
Ternary
Ternary
4-ary
4-ary