Sorting of parts
Sorting of parts
Sort[{{1,0,0,1,1,0},{1,0,0,1},{1,0,1,0,0},{1,0,1,1,1,0},{1,0,1,1},{1,1,1,0},{1}}]
In[]:=
{{1},{1,0,0,1},{1,0,1,1},{1,1,1,0},{1,0,1,0,0},{1,0,0,1,1,0},{1,0,1,1,1,0}}
Out[]=
Smallest Shortest (aka Leftmost Outermost)
Smallest Shortest (aka Leftmost Outermost)
This has the feature that rescanning is equivalent to burrowing/drilldown
Clear[SmallestShortestOrder]
In[]:=
SmallestShortestOrder[{},{}]:=0
In[]:=
SmallestShortestOrder[{},{__}]:=1
In[]:=
SmallestShortestOrder[{__},{}]:=-1
In[]:=
SmallestShortestOrder[{a_,aa___},{a_,bb___}]:=SmallestShortestOrder[{aa},{bb}]
In[]:=
SmallestShortestOrder[{a_,___},{b_,___}]:=Order[a,b]
In[]:=
Sort[{{1,0,0,1,1,0},{1,0,0,1},{1,0,1,0,0},{1,0,1,1,1,0},{1,0,1,1},{1,1,1,0},{1}},SmallestShortestOrder]
In[]:=
{{1},{1,0,0,1},{1,0,0,1,1,0},{1,0,1,0,0},{1,0,1,1},{1,0,1,1,1,0},{1,1,1,0}}
Out[]=
LeafCount/@NestList[SKStep[#,{First[SortBy[#,{Length,Identity}],Nothing]}&]&,s[s][s][s[s]][s][s],50]
In[]:=
{7,8,8,11,11,11,12,17,25,33,41,50,59,87,115,149,187,215,243,272,301,389,417,426,441,450,459,468,483,492,501,529,558,587,675,684,699,708,717,726,741,750,759,768,777,792,817,842,851,860,875}
Out[]=
LeafCount/@NestList[SKStep[#,{First[Sort[#,SmallestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],50]
In[]:=
{7,8,8,11,11,11,12,17,25,33,41,50,59,87,115,149,187,215,243,272,301,389,398,413,422,431,440,450,460,491,533,575,623,697,739,781,824,867,997,1127,1289,1451,1619,1912,2074,2236,2399,2562,3052,3062,3072}
Out[]=
ListStepPlot[LeafCount/@NestList[SKStep[#,{First[Sort[#,SmallestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],200]]
In[]:=
Out[]=
ListStepPlot[Differences[LeafCount/@NestList[SKStep[#,{First[Sort[#,SmallestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],200]],PlotRangeAll]
In[]:=
Out[]=
ListStepPlot[Ratios[LeafCount/@NestList[SKStep[#,{First[Sort[#,SmallestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],200]],PlotRangeAll]
In[]:=
Out[]=
LeafCount/@NestList[SKStep[#,{First[Sort[#,SmallestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],50]
In[]:=
{7,8,8,11,11,11,12,17,25,33,41,50,59,87,115,149,187,215,243,272,301,389,398,413,422,431,440,450,460,491,533,575,623,697,739,781,824,867,997,1127,1289,1451,1619,1912,2074,2236,2399,2562,3052,3062,3072}
Out[]=
SKOuterEvolveList[init_,n_]:=NestList[Module[{i=1},#/.{s[x_][y_][z_]:>x[z][y[z]]/;i++1,k[x_][y_]:>x/;i++1}]&,init,n]
In[]:=
LeafCount/@SKOuterEvolveList[s[s][s][s[s]][s][s],50]
In[]:=
{7,8,8,11,11,11,12,17,25,33,41,50,59,87,115,149,187,215,243,272,301,389,398,413,422,431,440,450,460,491,533,575,623,697,739,781,824,867,997,1127,1289,1451,1619,1912,2074,2236,2399,2562,3052,3062,3072}
Out[]=
LeafCount/@NestList[SKStep[#,{First[Sort[#,SmallestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],300]
In[]:=
{7,8,8,11,11,11,12,17,25,33,41,50,59,87,115,149,187,215,243,272,301,389,398,413,422,431,440,450,460,491,533,575,623,697,739,781,824,867,997,1127,1289,1451,1619,1912,2074,2236,2399,2562,3052,3062,3072,3088,3109,3119,3129,3140,3151,3185,3231,3312,3393,3480,3608,3689,3770,3852,3934,4181,4192,4215,4238,4267,4302,4325,4348,4372,4396,4469,4542,4627,4786,4945,5110,5355,5514,5673,5833,5993,6474,6498,6534,6595,6656,6723,6821,6882,6943,7005,7067,7254,7441,7628,7827,8214,8601,8994,9581,9968,10355,10743,11131,12296,12358,12420,12494,12631,12768,12911,13123,13260,13397,13535,13673,14088,14503,14918,15333,15760,16603,17446,18295,19566,20409,21252,22096,22940,25473,25611,25749,25887,26037,26326,26615,26910,27350,27639,27928,28218,28508,29379,30250,31121,31992,32863,33746,35501,37256,39017,41656,43411,45166,46922,48678,53947,54237,54527,54817,55107,55409,56002,56595,57194,58090,58683,59276,59870,60464,62247,64030,65813,67596,69379,71162,72957,76536,80115,83700,89075,92654,96233,99813,103393,114134,114728,115322,115916,116510,117104,117710,118911,120112,121319,123127,124328,125529,126731,127933,131540,135147,138754,142361,145968,149575,153182,156801,164028,171255,178488,189335,196562,203789,211017,218245,239930,241132,242334,243536,244738,245940,247142,248356,250773,253190,255613,259245,261662,264079,266497,268915,276170,283425,290680,297935,305190,312445,319700,326955,334222,348745,363268,377797,399588,414111,428634,443158,457682,501255,503673,506091,508509,510927,513345,515763,518181,520611,525460,530309,535164,542444,547293,552142,556992,561842,576393,590944,605495,620046,634597,649148,663699,678250,692801,707364,736479,765594,794715,838394,867509,896624,925740,954856,1042205,1047055,1051905,1056755,1061605,1066455,1071305,1076155,1081005,1085867}
Out[]=
Shortest Smallest (aka Outermost Leftmost)
Shortest Smallest (aka Outermost Leftmost)
Sort[{{1,0,0,1,1,0},{1,0,0,1},{1,0,1,0,0},{1,0,1,1,1,0},{1,0,1,1},{1,1,1,0},{1}}]
In[]:=
{{1},{1,0,0,1},{1,0,1,1},{1,1,1,0},{1,0,1,0,0},{1,0,0,1,1,0},{1,0,1,1,1,0}}
Out[]=
Largest Shortest (Rightmost Outermost)
Largest Shortest (Rightmost Outermost)
LargestShortestOrder[{},{}]:=0
In[]:=
LargestShortestOrder[{},{__}]:=1
In[]:=
LargestShortestOrder[{__},{}]:=-1
In[]:=
LargestShortestOrder[{a_,aa___},{a_,bb___}]:=LargestShortestOrder[{aa},{bb}]
In[]:=
LargestShortestOrder[{a_,___},{b_,___}]:=-Order[a,b]
In[]:=
Sort[{{1,0,0,1,1,0},{1,0,0,1},{1,0,1,0,0},{1,0,1,1,1,0},{1,0,1,1},{1,1,1,0},{1}},LargestShortestOrder]
In[]:=
{{1},{1,1,1,0},{1,0,1,1},{1,0,1,1,1,0},{1,0,1,0,0},{1,0,0,1},{1,0,0,1,1,0}}
Out[]=
LeafCount/@NestList[SKStep[#,{First[Sort[#,LargestShortestOrder],Nothing]}&]&,s[s][s][s[s]][s][s],50]
In[]:=
{7,8,8,11,11,11,12,17,25,33,41,50,59,87,96,111,120,129,138,147,157,167,198,240,250,260,276,297,318,356,394,443,453,463,474,485,519,565,646,727,843,1041,1052,1075,1098,1127,1162,1191,1232,1303,1374}
Out[]=
[[[ 8 cases ]]]
[[[ 8 cases ]]]
[ Position vs depth as more important ]
[ Sorting of depth ]
[ Sorting of position ]
[ Sorting of depth ]
[ Sorting of position ]
< We are typically going to use the first case only >
<< Claim: if we do by position before depth, then drilldown is equivalent to rescan >>
SMP case
SMP case
Go innermost for some number of levels, then go outermost [ ?? ]
Go to some tree depth, start evaluating there.
E.g. take the longest for the first 3 elements, then shortest thereafter
Need “generalized SMP case” with a k2 parameter which determines LR vs RL
Need “generalized SMP case” with a k2 parameter which determines LR vs RL
How Many Parts Do You Select at a Time?
How Many Parts Do You Select at a Time?
Other than step number, this doesn’t matter if we sort b
(Redex is the match to the pattern)
Special Cases
Special Cases
Map[ ] traversal order
Map[ ] traversal order
This is smallest longest (leftmost innermost)
/. case
/. case
Outermost for all pieces . i.e. the sinks in this graph:
test whether pref is a prefix in list....
Assignment / evaluation
Assignment / evaluation
leftmost innermost ?
[ Does not matter if it rescans or drills down ]
Evaluation with Hold functions
Evaluation with Hold functions
Assume we turn everything into Application, so everything is held
(Head is not held, so it’s different)
(Head is not held, so it’s different)
This is leftmost outermost