An issue with sets (and multisets) is that they can have multiple (different) interpretations.
For example, a set could be thought of as being represented by a sequence of unique items. Or, it could be represented by a bitmask. Or, it could be represented as the product of prime factors. Other representations are possible (for example, a string of names), though not necessarily "better". Similarly, a multiset could be thought of as being represented by a sequence of non-unique items. Or, it could be represented by a list of non-negative integers. Or, it could be represented as a single positive integer. Etc. (If these representations aren't immediately obvious to anyone, it might help to note that I've arranged them in parallel to their corresponding set representations.) In the contexts where we're representing either sets or multisets with a sequence of items, there are some operations where it's more convenient to require the items be ordered, and there's other operations where it's more convenient to ignore the order of the items. Now, logically, if we're going to settle on a "sequence of items" implementation (which favors a larger, sparser universe than the other representations I've mentioned), and we don't care about operating costs, the "sorting required" / "sorting ignored" pair of constraints can be easily satisfied by requiring ordering in the representation (as opposed to requiring it only for operations where it matters). Still... costs are only sometimes irrelevant (which is sometimes related to why we might pick different representations in different contexts). Thanks, -- Raul On Tue, Oct 30, 2018 at 5:46 AM R.E. Boss <[email protected]> wrote: > > IMO we should interpret the intersection and the union of two (multi)sets > (sets X with X >:&# ~.X) in the same way as is done by the GCD and the LCM of > two numbers. > So for two numbers N and M with (multi)sets of primefactors A and B, we > should have (N +. M) = */(A IS B) and (N *. M) = */ (A UN B), with > IS=intersection and UN = union of the (multi)sets A and B. > Obviously we require (A IS B) =&(/:~) B IS A and also (A UN B) =&(/:~) B UN > A for all (multi)sets A and B. > E.g. > 1 2 3 3 3 IS 3 3 3 3 3 4 5 6 > 3 3 3 > 1 2 3 3 3 UN 3 3 3 3 3 4 5 6 > 1 2 3 3 3 3 3 4 5 6 > > What are elegant and efficient J-definitions for IS and UN? > > > I have constructed > UN_reb=: ([:(~.@{.#~ {. >.//.{:) |:@,&(({.,#)/.~)) > and > IS_reb=: ([:(~.@{.#~ {. <.//.{:) ([|:@, ],~ 0,.~ -.~&:({."1), > -.&:({."1))&(({. , #)/.~)) > > 1 2 3 3 3 UN_reb 3 3 3 3 3 4 5 6 > 1 2 3 3 3 3 3 4 5 6 > 1 2 3 3 3 IS_reb 3 3 3 3 3 4 5 6 > 3 3 3 > 1 2 3 3 3 UN_reb~ 3 3 3 3 3 4 5 6 > 3 3 3 3 3 4 5 6 1 2 > 1 2 3 3 3 IS_reb~ 3 3 3 3 3 4 5 6 > 3 3 3 > > a=: 1e7?.@#1e6 > ts'a UN_reb a+499999' > 0.76631908 4.6996013e8 > #a UN_reb a+49999 > 12186812 > ts'a IS_reb a+499999' > 0.76073743 3.3554592e8 > #a IS_reb a+49999 > 7813188 > > > R.E. Boss > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
