Re: Dimension of sequences
Igor Kachan wrote:
>
> CChris wrote:
> >
> > Igor Kachan wrote:
> > >
> > > Fernando Bauer wrote:
> > > >
> > > > Igor Kachan wrote:
> > > > >
> > > > > > 'non-rectangular sequence' (NRS) = all sequences that aren't RS.
> > > > > > 'dimension of RS' = maximum depth of the sequence.
> > > > > > 'dimension of NRS' = that is the question!
> > > > >
> > > > > Let's see the refman.doc file now.
> > > > >
> > > > > Robert Craig writes:
> > > > >
> > > > > "Sequences can be nested to any depth, i.e. you can have sequences
> > > > > within
> > > > > sequences within sequences and so on to any depth (until you run out
> > > > > of
> > > > > memory)."
> > > > >
> > > > > I see Rob cares just about *maximum* depth here, so his definition
> > > > > of depht, documented in refman.doc, is strongly equivalent to your
> > > > > definition of 'dimension of RS'.
> > > > > Same thing, you just introduce some new term, synonym.
> > > > >
> > > > > No?
> > > >
> > > > Ok. We can use "depth" as synonym of "dimension" as you prefer. Then my
> > > > question
> > > > is:
> > > > What is the depth of a NRS? How can I obtain it? For now, I only know
> > > > the depth
> > > > of a RS.
> > >
> > > Hello, Fernando!
> > >
> > > OK, let's use just that MaxDepth() function by Ricardo,
> > > it seems to work properly not only on 'simple' sequences,
> > > but on any ones, it is recursive, and gives us that
> > > pure maximum maximorum depth of any sequence.
> > >
> > > See please:
> > > }}}
<eucode>
> > > global function MaxDepth(object o)
> > > integer n, x
> > > if atom(o) then
> > > return 0
> > > else
> > > n = 0
> > > for i = 1 to length(o) do
> > > x = MaxDepth(o[i])
> > > if x > n then
> > > n = x
> > > end if
> > > end for
> > > return n + 1
> > > end if
> > > end function -- it is function by Ricardo Forno, genfunc.e lib
> > >
> > > ? MaxDepth({{{{}}},{},{{},{{{{{{{{{{{{}}}}}}}}}}}}},{{{{{{{{}}}}}}}}})
> > > ?
> > > MaxDepth({{{{1}}},{1},{{1},{{{{{{{{{{{{1}}}}}}}}}}}}},{{{{{{{{1}}}}}}}}})
> > > </eucode>
{{{
> > > The maximum depth is 14, all right.
> > > Count please the '{' signs, opening the deepest sequence,
> > > to be sure.
> > > It seems to be a good parameter for description of a sequence.
> > > Now a sequence has its own second dimension, and may be
> > > considered as some 2-dimensional object, which can contain
> > > description of any-dimentional real and unreal objects -
> > > vectors, matrixes, tensors, lists, arrays, trees, books,
> > > images ... etc, etc.
> > > Sequence itself really has two own dimensions - length and depth,
> > > I think now. So attempts to give it some *single* dimension
> > > may be not very productive.
> > >
> > > > > Then, I do not think now that the 'rectangular' word is very
> > > > > good for your purpose, maybe, 'regular', as some short
> > > > > for 'regularly nested', is better.
> > > > >
> > > > Ok. But I think "rectangular" is sligthly more precise than "regular",
> > > > since
> > > > I could think that the following sequence is regular:
> > > > repeat({1,{1,1}},n) where n is any integer number. And that sequence is
> > > > NRS.
> > > > Well, this is only a definition problem.
> > >
> > > Ricardo names these sequences as 'simple sequences'.
> > >
> > > > > > > So what? What will we do with all these new terms, with
> > > > > > > all these new notions, with all these new concepts?
> > > > > >
> > > > > > First of all, they facilitate our communication, since we don't have
> > > > > > to
> say</font></i>
> > > > > > that whole definition phrase.
> > > > > > Second, the terms RS and NRS can represent types in Euphoria, like
> > > > > > vector
> > or</font></i>
> > > > > > matrix, and so can be checked.
> > > > > > Some algorithms can function with one and not with other type, etc..
> > > > >
> > > > > Ok, but for now I do not see some real place for the 'dimension' word
> > > > > here. Length & Depth. These old good words are very clear in
> > > > > the specific EU context.
> > > >
> > > > Ok. But the Depth concept is not so clear as it seems, since nobody
> > > > defined
> > > > what it is for NRS yet.
> > >
> > > OK, now we can calculate that Depth (good, let's name the maximum depth
> > > as Depth) with Ricardo's function.
> > >
> > > Regards,
> > > Igor Kachan
> > > kinz at peterlink.ru
> >
> > Eu sequences model trees with atomic labels allowed, and mandatory, only on
> > leaf nodes.
> > For instance, {1,{2,3},4} is the same as
> > root -> node1, node2, node3
> > node1: 1
> > node2 -> node4, node5
> > node3: 4
> > node4: 2
> > node5: 3
> >
> > with hopefully obvious meaning of such a description of a tree.
> >
> > Now google for some litterature on trees. You'lll see that most specific
> > form
> > of trees define their own dimension, depth or height.
> > Concepts that can be defined always include:
> > * the depth of a tree, which is the height of its root;
>
> OK, I like this theory very much as math at all, some good
> thing to get crazy, if you do not have or do not like vodka, sorry. 
>
> Why do they need these topsyturvy trees, Cris?
>
They are the most common objects in decision theory (think of a chess computer
program) or in searching/retrieval problems (remember the contest Derek had
hosted a couple years ago?). And many others, but hese may be the most obvious.
> I can understand depth of a root and height of a tree,
> but not on the contrary.
>
This has to do with our habit to read a sheet of paper from top to bottom, which
is why the root is usually on top
> > * the depth of a node in a tree, which is its distance to the root (ie the
> > number
> > of edges to go from the node to the root);
> > * the height of a node, which is the length of the longest path from the
> > node
> > to a leaf node in its subtree.
>
> Same thing, very-very demonstrative concept.
>
> > The length of a sequence is simply the number of children of the root. This
> > has not much importance in tree theory, but is essential for _some_ sorts of
> > them, namely strings of arbitrary things, among which trees. It has been
> > chosen
> > to build this special notion in the language, and to leave out the more
> > general
> > ones. Other trees will have their own notion of depth or somsuch, which
> > depends
> > on the speifics of the layout an uses of the given family of trees.
> > So yes, sequences don't have a single dimension, although some sorts of
> > sequences
> > do have a more intinsic kind of dimension. Strings are an example, for which
> > the length is the "natural" dimension.
>
> OK, but depth of a string exists and is 1. So sequence seems to be
> some 2-dimensional object anyway and always.
>
2,3,27,... depending on the exact notion of dimension you need. A sequence
whose elements may freely be atoms or not has dimension 1, and strings are
special cases of them. Otherwise, as I said, the concept is not uniquely defined,
and the value for the dimension is always 2 or more.
CChris
> Regards,
> Igor Kachan
> kinz at peterlink.ru
|
Not Categorized, Please Help
|
|
