reduce ( -- ) that eliminates copies of members in sorted sets in z;
zdup zdrop zover zswap znip ztuck and zrot manipulates bundles in z;
cardinality ( -- n | s -- ) that counts the number of elements in sets or components vectors;
foreach ( -- n 0 | s -- z1...zn ) that "appends" a set and prepare for a do loop for each element;
zet. ( s -- ) that prints the set/vector on z;
subset zet= member that examines sets and vectors on z;
union intersection diff powerset cartprod etc that works on z;
set-sort ( -- | m1...mk -- n1---nk )
zmerge ( s s' -- s" )
The other two stacks, x and y, are help stacks that compensate the lack of variables. Some operations working on x and y are:
setdup ( ad -- | obj -- obj obj )
setdrop ( ad -- | obj -- )
setover ( ad -- | obj1 obj2 -- obj1 obj2 obj1
setmove ( ad1 ad2 -- )
setcopy ( ad1 ad2 -- )
_fence ( ad -- | obj -- {obj} )
_split ( ad -- | s -- s' obj ) ad=yst,zst
xzmerge ( s -- ) takes set from z and merge so set in x
yzcopy1 ( -- s ) copy set from top y to z
yzcopy2 ( -- s ) copy set from next after top y to z
There are two main methods to penetrate a set, to use foreach or to use zsplit (or ysplit). When all elements are to be penetrated foreach is handy, but no objects under the top set on z can be reached under the penetration. When using zsplit, that splits a set in the top element and the rest of the set, the sets under can be reached, and the penetration can be abrupt without stack problems.
The facility with | in
{ 1 100 | prime } cr zet.{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97} ok
does only work in interpretation mode and can't be compiled.
1 value num
: coprime \ n -- flag
num ugcd 1 = ;
{ 1 30 dup to num | coprime } zet. {1,7,11,13,17,19,23,29} ok
17 num invmod . 23 ok
17 23 num u*mod . 1 ok
About adding all numbers in two sets:
: setint+ \ n -- | s -- s'
0 >xst \ empty set on x
foreach \ for each number in s
?do zst> over + >zst \ element to datastack and back
zfence xzmerge \ merge {x+y} to the set on x
loop drop xst zst setmove ; \ drop n and move the set to z
: set+ \ s s' -- s"
0 >xst
zst yst setmove
foreach
?do zst> \ element to data stack
yzcopy1 setint+ \ add element to all elements in s'
xzmergered \ merge this set to the set on x
loop yst setdrop
xst zst setmove ;
{ 3 100 | prime } zdup set+ cr zet.
{6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,176,178,180,186,194} ok
Hmm..! Goldbach seems to be right...
The first failure is 174.
{ 3 200 | prime } zdup set+ cr zet.
{6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,256,258,260,262,264,266,268,270,272,274,276,278,280,282,284,286,288,290,292,294,296,298,300,302,304,306,308,310,312,314,316,318,320,322,324,326,328,330,332,334,336,338,340,342,344,346,348,350,352,354,356,358,360,362,364,366,370,372,374,376,378,380,382,384,386,388,390,392,394,396,398} ok
First failure at 368.
{ 3 300 | prime } zdup set+ cr zet.
{6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,256,258,260,262,264,266,268,270,272,274,276,278,280,282,284,286,288,290,292,294,296,298,300,302,304,306,308,310,312,314,316,318,320,322,324,326,328,330,332,334,336,338,340,342,344,346,348,350,352,354,356,358,360,362,364,366,368,370,372,374,376,378,380,382,384,386,388,390,392,394,396,398,400,402,404,406,408,410,412,414,416,418,420,422,424,426,428,430,432,434,436,438,440,442,444,446,448,450,452,454,456,458,460,462,464,466,468,470,472,474,476,478,480,482,484,486,488,490,492,494,496,498,500,502,504,506,508,510,512,514,516,518,520,522,524,526,528,532,534,538,540,542,544,546,548,550,552,554,556,558,560,562,564,566,570,574,576,586} ok
Fail(300)=530. The first failure is a kind of measure of the probability of Goldbachs conjecture to be true.
Additional words for permutation groups:
\ Is s a permutation subgroup of s'?
: psub? \ -- flag | s s' --
zover zswap subset 0=
if zdrop false exit
then permgroup? ;
\ Is s a normal permutation subgroup of s'?
: pnsub? \ -- flag | s s' --
zover zover psub? 0=
if zdrop zdrop false exit then
zswap zst yst setmove
begin zst@
while zsplit yzcopy1 zover prcoset
zswap yzcopy1 plcoset zet= 0= \ false
if zdrop yst setdrop false exit then
repeat zdrop \ dropping the empty set left in z
yst setdrop true ;
\ s' is the set of normal subgroups of s
: pnsubgroups \ s -- s'
zst yst setcopy
psubgroups
0 >xst
begin zst@
while zsplit zdup yzcopy1 pnsub?
if zfence xzmerge else zdrop then
repeat zdrop yst setdrop xst zst setmove ;
{ ( 4 1 2 3 ) ( 2 1 3 4 ) } generate zdup cardinality . 24 ok
pnsubgroups cr zet.
{{(2,1,3,4),(3,4,2,1),(3,1,4,2),(2,3,4,1),(1,4,2,3),(1,3,4,2),(1,2,3,4),(4,2,3,1),(4,1,2,3),(3,2,1,4),(4,1,3,2),(4,2,1,3),(4,3,1,2),(2,1,4,3),(2,3,1,4),(2,4,1,3),(3,1,2,4),(3,4,1,2),(3,2,4,1),(4,3,2,1),(2,4,3,1),(1,2,4,3),(1,3,2,4),(1,4,3,2)},{(4,3,2,1),(1,3,4,2),(1,2,3,4),(4,2,1,3),(3,1,2,4),(2,3,1,4),(2,4,3,1),(3,2,4,1),(1,4,2,3),(4,1,3,2),(2,1,4,3),(3,4,1,2)},{(4,3,2,1),(1,2,3,4),(3,4,1,2),(2,1,4,3)},{(1,2,3,4)}} ok
No comments:
Post a Comment