I managed to adapt Fraser's sortSet to my model, so now a set is merely a list
of boxes ending in <i.0 0, an element is the open of a box in the curtail,
duplicate elements are allowed, and the curtail does not have to be sorted.
My main motives are a desire to have a unique empty set (as in set theory) and
not to allow sets which are elements of themselves (they lead to a famous
paradox in set theory, and might lead to infinite loops in J -- I'm not sure of
that).
Sets are created by M =: element;element;...;element;E where E is the unique
empty set ,<i.0 0 . The way Link ; handles right arguments ensures the tail of
M
will be <i.0 0 . As a small bonus for always having tail <i.0 0 , when you
create sets as shown you do not have to remember to box the rightmost element
if
it is boxed.
]M =: 'b';'a';'b';2 2 3 1;(5 4;('d';'c';'c';E);E);E
+-+-+-+-------+---------------++
|b|a|b|2 2 3 1|+---+--------++||
| | | | ||5 4|+-+-+-++||||
| | | | || ||d|c|c||||||
| | | | || |+-+-+-++||||
| | | | |+---+--------++||
+-+-+-+-------+---------------++
]N =: (|....@}: , {:) M
+---------------+-------+-+-+-++
|+---+--------++|2 2 3 1|b|a|b||
||5 4|+-+-+-++||| | | | ||
|| ||d|c|c||||| | | | ||
|| |+-+-+-++||| | | | ||
|+---+--------++| | | | ||
+---------------+-------+-+-+-++
M equalset N
1
equalset
-:&realset
realset M
+-------+-+-+-------------++
|2 2 3 1|a|b|+---+------++||
| | | ||5 4|+-+-++||||
| | | || ||c|d||||||
| | | || |+-+-++||||
| | | |+---+------++||
+-------+-+-+-------------++
realset N
+-------+-+-+-------------++
|2 2 3 1|a|b|+---+------++||
| | | ||5 4|+-+-++||||
| | | || ||c|d||||||
| | | || |+-+-++||||
| | | |+---+------++||
+-------+-+-+-------------++
pwrSet 0;1;E NB. power set of "{0,1}" ; I modified Raul's powSet
+--+----+----+------++
|++|+-++|+-++|+-+-++||
|++||1||||0||||0|1||||
| |+-++|+-++|+-+-++||
+--+----+----+------++
The order in last result is "numerical" order of masks 0 0 , 0 1 , 1 0 , 1 1
used in (mask # 0;1) in pwrSet. Verb realset provides standard "lexical" order:
realset pwrset 0;1;E
+------+----+----+--++
|+-+-++|+-++|+-++|++||
||0|1||||0||||1|||++||
|+-+-++|+-++|+-++| ||
+------+----+----+--++
For details and credits to Fraser and Raul, see below. I didn't know how to
handle unions, differences, and intersections of sets with duplicate elements,
so I punted to realset, as you will see. How would you do them?
Kip
Details:
NB. Revised 10 July 2009
NB. Proposal: A "set" is a list of boxes with tail <i.0 0 .
NB. An "element" is the open of a box in the curtail.
NB. A "set" may have duplicate elements and
NB. the curtail is not required to be sorted.
NB. M =: element;element;...;element;E creates a set.
NB. E is ,<i.0 0 -- the empty set. Because of the way Link ;
NB. treats right arguments, the tail of M will be <i.0 0 .
NB. The tail <i.0 0 identifies the list as a set, permits
NB. the list ,<i.0 0 to be the unique empty set, and makes
NB. it easier to create sets with Link ; -- you don't have
NB. to remember to box the rightmost element if it is boxed.
isset =: (1 = #...@$) *. (0 < L.) *.( (<i.0 0) -: {: )
NB. list of boxes with tail <i.0 0
isrealset =: -: realset NB. see verb realset below
Empty =: , < i.0 0 NB. empty set
E =: Empty
sortnub =: (] : [:)`(( /:~...@~.@}: , {: ) : [:)@.isset f.
NB. If argument is a set, sortnub returns a new set with curtail
NB. the sorted nub of argument's curtail; returns nonsets unchanged.
realset =: 3 : 0 NB. recursive sortnub; almost Fraser's sortSet
s =. y
for_k. i. >: L. y do. s =. sortnub L:k s end.
)
NB. usage realset set produces an equivalent "real set":
NB. no duplicate elements and recursively "sortnubbed"
NB. for easy comparison with other "real sets".
sortSet =: 3 : 0 NB. Fraser's; the source of realset
s =. y
for_k. i. >: L. y do. s =. Set L:k s end.
)
equalset =: -:&realset NB. i.e., equal as sets
eqs =: equalset
iselementof =: <@[ e. }:@]
in =: iselementof
countset =: #...@}:
count =: countset
countrealset =: #...@}:@realset
countreal =: countrealset
index =: }:@[ i. <@] NB. find index of element
indexof =: index
get =: [:`({:: }:)@.(1 > l...@[) NB. retrieve element
u =: (-. , ])&realset NB. union?
less =: (Empty ,~ -.)&realset NB. difference?
n =: ([ less less)&realset NB. intersection?
issubsetof =: [ eqs n
part =: issubsetof
isemptyset =: -: Empty"_
pwrset =: 3 : 0 NB. adapted from Fraser's explicit version
if.
isemptyset y
do.
Empty;Empty NB. set whose only element is Empty
else.
Empty ,~ (#&y) &.> ( <"1 ] 1 ,~"1 (#: i.2^<:#y) )
end.
)
NB. pwrSet below is adapted from Raul's powSet. Sort /:~ removed.
pwrSet =: (<i.0 0) ,~ ] (<@#~) 1 (,~"1) 2 (#"1~ {:)@#:@i...@^ #...@}:
NB. powSet=: /:~@:(<@#~) 2 (#"1~ {:)@#:@i...@^ # NB. Raul's; the source of
pwrSet
NB. Don't use Raul's powSet on my sets!
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
