Set reorders elements
Alex Ghitza
This is a bit disconcerting:
sage: Set(['a', 'b', 'c'])
{'a', 'c', 'b'}
sage: Set(['a', 'b', 'c', 'd'])
{'a', 'c', 'b', 'd'}
sage: Set(['a', 'b', 'c', 'd', 'e'])
{'a', 'c', 'b', 'e', 'd'}
Bug? It doesn't seem to happen with lists of numbers.
Best,
Alex
--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/
Nick Alexander
On 7-Nov-09, at 8:29 PM, Alex Ghitza wrote:
>
>
> This is a bit disconcerting:
>
> sage: Set(['a', 'b', 'c'])
> {'a', 'c', 'b'}
> sage: Set(['a', 'b', 'c', 'd'])
> {'a', 'c', 'b', 'd'}
> sage: Set(['a', 'b', 'c', 'd', 'e'])
> {'a', 'c', 'b', 'e', 'd'}
>
> Bug? It doesn't seem to happen with lists of numbers.
Sets are unordered. Why does the display order changing worry you?
Nick
Alex Ghitza
>
>
> Sets are unordered. Why does the display order changing worry you?
>
Of course they are. So mathematically speaking everything is fine.
However, unless there's a good reason for Set(['a', 'b', 'c']) to
result in {'a', 'c', 'b'}, I would prefer to not be kept on my toes
like this.
Questions that come to mind when I see this:
1. Can the display order change between different sessions of Sage on
the same machine?
2. Is the display order machine-dependent in any way?
In fact, the reason this is bothering me right now is that I'm writing
code for working with free groups on sets, and I end up with something
like
sage: G.<a, b, c> = FreeGroup()
sage: G
Free Group on the Set {a, c, b}
sage: b
c
This is probably due more to crappy programming on my part rather than
the Set issue, but the latter did confuse me.
Alex Ghitza
>
> In fact, the reason this is bothering me right now is that I'm writing
> code for working with free groups on sets, and I end up with something
> like
>
> sage: G.<a, b, c> = FreeGroup()
> sage: G
> Free Group on the Set {a, c, b}
> sage: b
> c
And another example, where I (would like to) follow the example of the
constructor for multivariate polynomials:
sage: FreeGroup('x', 10)
Expected:
Free Group on the Set {x0, x1, x2, x3, x4, x5, x6, x7, x8, x9}
Got:
Free Group on the Set {x8, x9, x2, x3, x0, x1, x6, x7, x4, x5}
William Stein
>
>
> This is a bit disconcerting:
>
> sage: Set(['a', 'b', 'c'])
> {'a', 'c', 'b'}
> sage: Set(['a', 'b', 'c', 'd'])
> {'a', 'c', 'b', 'd'}
> sage: Set(['a', 'b', 'c', 'd', 'e'])
> {'a', 'c', 'b', 'e', 'd'}
>
> Bug? It doesn't seem to happen with lists of numbers.
Just a quick remark. In Sage there is set (the builton Python type)
and Set (the Sage type, which wraps the builtin one):
sage: set(['a','b','c'])
set(['a', 'b', 'c'])
sage: Set(['a','b','c'])
{'a', 'c', 'b'}
My intention in introducting Set in addition to set, was to make
something that would have much more mathematical printing and
semantics than Python sets, in addition to allowing for infinite sets,
etc. The underlying data structure for finite enumerated sets is just
a normal Python set:
sage: type(x._Set_object__object)
<type 'frozenset'>
I think it would be reasonable to change the _repr_ method to output
the elements in some natural order *if possible*. Right now, it just
does this:
def _repr_(self):
r"""
Return the string representation of ``self``.
EXAMPLES::
sage: S = EnumeratedSet(GF(2))
sage: S
{0, 1}
"""
s = repr(self.set())
return "{" + s[5:-2] + "}"
This is in sage/sets/set.py
I think I would be OK with you changing this function to do something more like
s = repr(sorted(list(self.set())))
or something like that. Obviously, there will be sets where elements
can't be compared, so sorting will raise an error -- this needs to be
caught. There will also be a performance penalty, but we pay this
only for printing.
William
Nick Alexander
> sage: G
> Free Group on the Set {a, c, b}
> sage: b
> c
>
> This is probably due more to crappy programming on my part rather than
> the Set issue, but the latter did confuse me.
I think this is due to a poor definition: the decision was made that
variables are named and order matters. So G.<a,b,c> = FreeGroup() and
G.<a,c,b> = FreeGroup() are different objects -- the lists of
generators have different names, and that makes them distinct. So
printing the "Free Group on the Set {a, b, c}" is misleading because
the current convention is that "FG on a, b" and "FG on b, a" are
distinct.
Nick
Florent Hivert
> And another example, where I (would like to) follow the example of the
> constructor for multivariate polynomials:
>
> sage: FreeGroup('x', 10)
> Expected:
> Free Group on the Set {x0, x1, x2, x3, x4, x5, x6, x7, x8, x9}
> Got:
> Free Group on the Set {x8, x9, x2, x3, x0, x1, x6, x7, x4, x5}
I think what is needed is the notion of what we call in combinatorics
EnumeratedSets (see below). This is currently not the same think than sage
EnumeratedSet class...
With the integration of categories, I'm currently working on Sets... I'll
shortly adapt sage Set to the category system and along the way put sage
EnumeratedSet not in the category Sets but in the Category EnumeratedSets
which is in my opinion what you need. Here is an excerpt of the doc:
The category of enumerated sets
An *enumerated set* is a *finite* or *countable* set or multiset `S`
together with a canonical enumeration of its elements;
conceptually, this is very similar to an immutable list. The main
difference lies in the names and the return type of the methods,
and of course the fact that the list of element is not supposed to
be expanded in memory. Whenever possible one should use one of the
two sub-categories :class:`FiniteEnumeratedSets` or
:class:`InfiniteEnumeratedSets`.
Of course this is still not in Sage but should (I'd rather say will :-) be in
4.3. Right now the only sage sets which are EnumeratedSets are Primes and the
NonNegative Integers. Note That I have already a class FiniteEnumeratedSet
which needs to be merged with sage EnumeratedSet:
A class for finite enumerated set.
Returns the finite enumerated set with elements in ``elements``
where ``element`` is any (finite) iterable object.
The main purpose is to provide a variant of ``list`` or ``tuple``,
which is a parent with an interface consistent with
``EnumeratedSets`` and has unique representation.
The list of the elements is expanded in memory.
There are some design questions which prevented me to do it at first. Let's
start with the simple one:
- on mathematical sets we have the notion of intersection, union, symmetric
difference. When dealing with EnumeratedSets, does someone have any opinion on
the order of enumeration of the result ? Or should the result be only in the
category Sets ?
Here is a much more complicated one:
- If a parent is in a sub category of EnumeratedSets or Sets (say e.g.:
FiniteGroup), Currently the forgetful functor is implemented by Set
sage: S = Set(SymmetricGroup(3))
sage: S
{(2,3), (1,3), (1,2), (1,3,2), (), (1,2,3)}
Compare with:
sage: list(SymmetricGroup(3))
[(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
sage: FiniteEnumeratedSet(SymmetricGroup(3))
{(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)}
But SymmetricGroup(3) is already in the category Sets
sage: SymmetricGroup(3) in Sets()
True
So there should be no need to call explicitely the forgetful functor.
In particular I don't see the point of creating another sage object for those
case. Otherwise said, I only see the reason to create a new sage object for
building a Set, when the object is not a sage Parent in the category Sets, eg:
python list, set, frozenset ...
Any comment or suggestion is mostly welcome.
Cheers,
Florent
Florent Hivert
By the way, I think this is a good moment to advertise for a very good idea
Nicolas had a few years ago, that is to implement and use the very common and
basic notion of family:
A Family is an associative container which models a family
`(f_i)_{i in I}`. Then, f[i] returns the element of the family
indexed by i. Whenever available, set and EnumeratedSets
operations (counting, iteration, listing) on the family are induced
from those of the index set.
> And another example, where I (would like to) follow the example of the
> constructor for multivariate polynomials:
>
> sage: FreeGroup('x', 10)
> Expected:
> Free Group on the Set {x0, x1, x2, x3, x4, x5, x6, x7, x8, x9}
> Got:
> Free Group on the Set {x8, x9, x2, x3, x0, x1, x6, x7, x4, x5}
Here is my point: Take a random group with a set of generators:
sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
Now I want to construct the free group on those generators. Let try to do it
only with FreeMonoid since FreeFroup in not already implemented ;-)
sage: F = FreeMonoid(2, S3.gens())
...
ValueError: variable names must be alphanumeric, but one is '(1,2,3)' which is not.
I currently have to do:
sage: (gs123, gs12) = S3.gens()
sage: F = FreeMonoid(2, ['gf123', 'gf12'])
sage: gf123, gf12 = F.gens()
And to handle the association gf123 <-> gs123 and gf12 <-> gs12 by hand.
Here comes the family. Right now:
sage: F.gens()
(gf123, gf12)
But I'd rather F.gens() returns the following Fgens object:
sage: Fgens = Family({gs123 : gf123, gs12 : gf12})
sage: Fgens
Finite family {(1,2,3): gf123, (1,2): gf12}
sage: tuple(Fgens) # equivalent to F.gens()
(gf123, gf12)
Fgens behave has a f.gens() with respect to iteration:
sage: for g in Fgens: print(g, g.parent())
....:
(gf123, Free monoid on 2 generators (gf123, gf12))
(gf12, Free monoid on 2 generators (gf123, gf12))
sage: len(Fgens)
2
Now I can write:
sage: Fgens[S3((1,2,3))]
gf123
That is the generator of F are naturally indexed. Note that if you don't know
by what you want to index them Family index automatically the generator by
0, 1,2,... That is the following FgensBis behave as a list:
sage: FgensBis = Family([gf123, gf12])
sage: FgensBis
Family (gf123, gf12)
sage: FgensBis[0]
gf123
sage: len(FgensBis)
2
We already use It extensively when building the basis in our
CombinatorialFreeModule and I think this should be used everywhere when
building a free object.
Comments and suggestions welcome !
Cheers,
Florent
javier
On Nov 8, 9:36 am, Florent Hivert <florent.hiv...@univ-rouen.fr>
wrote:
> start with the simple one:
>
> - on mathematical sets we have the notion of intersection, union, symmetric
> difference. When dealing with EnumeratedSets, does someone have any opinion on
> the order of enumeration of the result ? Or should the result be only in the
> category Sets ?
enumerated sets" is not real "category" from the mathematical point of
view, although you can embed it inside the category of totally ordered
sets with the "enumeration order", that point of view might solve some
of your design questions.
Concerning the union of sets, in general you have to canonical way of
assigning an enumeration, one can decide to enumerate first all the
elements of A and then all the elements of B. This works without much
trouble for finite sets. If you want a method that works also for
infinite ones, you can use the standard Hilbert Hotel tricks: To add a
finite set A to an infinite set B you shift all the elements of B the
needed places and put the elements of A at the beginning, and to unite
two infinite sets you put A[n] inside X[2n] and B[n] inside X[2n-1].
All these methods have the issue that as enumerated sets A.union(B)
would be different from B.union(A). Plus the fact that the enumeration
choice is arbitrary.
Another direction could be to allow to specify an "ambient" enumerated
set X that contains both A and B, and endow the union with the
enumeration inherited from the ambient set (this would work well with
things such as conjugacy classes of groups, where all elements belong
to a common set). For this to make any (mathematical) sense, it would
be necessary that the enumeration of A and B also come from the
enumeration of X, which bring us to the problem of the intersection.
If A={a1,a2,a3,a4,a5} and B={a2,a3,a5,a7,a11} (as enumerated sets) it
makes sense to consider the intersection as the enumerated set
{a2,a3,a5}, but if B={a11,a7,a5,a3,a2} then no enumeration will make
sense. So my proposal would be to enumerate only when one has a common
parent of A and B that is enumerated.
>
> Here is a much more complicated one:
>
> - If a parent is in a sub category of EnumeratedSets or Sets (say e.g.:
> FiniteGroup), Currently the forgetful functor is implemented by Set
> sage: S = Set(SymmetricGroup(3))
> sage: S
> {(2,3), (1,3), (1,2), (1,3,2), (), (1,2,3)}
> Compare with:
> sage: list(SymmetricGroup(3))
> [(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
> sage: FiniteEnumeratedSet(SymmetricGroup(3))
> {(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)}
> But SymmetricGroup(3) is already in the category Sets
> sage: SymmetricGroup(3) in Sets()
> True
> So there should be no need to call explicitely the forgetful functor.
> In particular I don't see the point of creating another sage object for those
> case. Otherwise said, I only see the reason to create a new sage object for
> building a Set, when the object is not a sage Parent in the category Sets, eg:
> python list, set, frozenset ...
to group homomorphisms), but just the "underlying set" of a group. As
of why we might need to call it, one can think of the same underlying
set {a,b,c,d} having two different group structures (isomorphic to ZZ/
2ZZ x ZZ/2ZZ or Dihedral(4)) as groups, these would be different (even
non-isomorphic), but as sets they are the same (i.e. the forgetful
functor is not injective on objects). This, mathematically. As of the
implementation within sage, I agree one would think that the quickest
way to apply it is just not to use the extra structure that has been
previously defined, but I don't know the details on the implementation
well enough to say anything intelligent about this.
Cheers
Javier
Gonzalo Tornaria
>
>
> This is a bit disconcerting:
>
> sage: Set(['a', 'b', 'c'])
> {'a', 'c', 'b'}
I am surprised by the following:
sage: s = set(['a', 'b', 'c'])
sage: repr(s)
"set(['a', 'c', 'b'])"
sage: str(s)
"set(['a', 'c', 'b'])"
so far so good, however:
sage: s
set(['a', 'b', 'c'])
???
This behaviour happens in 4.2, but NOT in 3.4.1
This doesn't happen in "sage -python", but it does happen in "sage
-ipython", so I guess is ipython related. However, both versions seem
to be using ipython 9.1...
Gonzalo
Carlo Hamalainen
<torn...@math.utexas.edu> wrote:
> This doesn't happen in "sage -python", but it does happen in "sage
> -ipython", so I guess is ipython related. However, both versions seem
> to be using ipython 9.1...
This is the pprint (pretty print) module. From ipython's man page:
-[no]pprint
IPython can optionally use the pprint (pretty printer) module for
displaying results. pprint tends to give a nicer display of nested
data structures. If you like it, you can turn it on permanently in
your config file (default off).
$ ipython -nopprint
In [1]: s = set(['a', 'b', 'c'])
In [2]: s
Out[2]: set(['a', 'c', 'b'])
--
Carlo Hamalainen
http://carlo-hamalainen.net
Florent Hivert
> I think the design problem comes from the fact the "category of
> enumerated sets" is not real "category" from the mathematical point of
> view, although you can embed it inside the category of totally ordered
> sets with the "enumeration order", that point of view might solve some
> of your design questions.
Yes it is ! If you decide that maps are one to one bijection which are
compatible with the enumeration order. That's the base of the theory of
Linear-Species (defined as Functor : EnumSet -> Set).
> Concerning the union of sets, in general you have to canonical way of
> assigning an enumeration, one can decide to enumerate first all the
> elements of A and then all the elements of B. This works without much
> trouble for finite sets.
It's clear if sets are disjoints. That's already implemented in
DisjointUnionEnumeratedSet... You can even play with infinite union:
sage: S = DisjointUnionEnumeratedSets(Family(NonNegativeIntegers(), Permutations))
sage: S
Disjoint union of Lazy family (Permutations(i))_{i in Non negative integers}
sage: S = DisjointUnionEnumeratedSets(Family(NonNegativeIntegers(), Permutations))
sage: S
Disjoint union of Lazy family (Permutations(i))_{i in Non negative integers}
sage: import itertools
sage: itertools.islice(S, 0, 10)
<itertools.islice object at 0x4793208>
sage: list(itertools.islice(S, 0, 10))
[[],
[1],
[1, 2],
[2, 1],
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]]
sage: S.cardinality()
+Infinity
sage: Permutation([3,1,2]) in S
/usr/local/sage/sage-4.1.2/local/lib/python2.6/site-packages/sage/sets/disjoint_union_enumerated_sets.py:246: UserWarning: Disjoint union of Lazy family (Permutations(i))_{i in Non negative integers} is an infinite union
The default implementation of __contains__ can loop forever. Please overload it.
True
It's less clear if A and B are not disjoint.
> All these methods have the issue that as enumerated sets A.union(B)
> would be different from B.union(A). Plus the fact that the enumeration
> choice is arbitrary.
That's the problem... The question was more if someone has some practical
application.
> Another direction could be to allow to specify an "ambient" enumerated
> set X that contains both A and B, and endow the union with the
> enumeration inherited from the ambient set (this would work well with
> things such as conjugacy classes of groups, where all elements belong
> to a common set). For this to make any (mathematical) sense, it would
> be necessary that the enumeration of A and B also come from the
> enumeration of X, which bring us to the problem of the intersection.
> If A={a1,a2,a3,a4,a5} and B={a2,a3,a5,a7,a11} (as enumerated sets) it
> makes sense to consider the intersection as the enumerated set
> {a2,a3,a5}, but if B={a11,a7,a5,a3,a2} then no enumeration will make
> sense. So my proposal would be to enumerate only when one has a common
> parent of A and B that is enumerated.
That's a good idea... I'll try it.
> > Here is a much more complicated one:
> >
> > - If a parent is in a sub category of EnumeratedSets or Sets (say e.g.:
> > FiniteGroup), Currently the forgetful functor is implemented by Set
> > sage: S = Set(SymmetricGroup(3))
> > sage: S
> > {(2,3), (1,3), (1,2), (1,3,2), (), (1,2,3)}
> > Compare with:
> > sage: list(SymmetricGroup(3))
> > [(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
> > sage: FiniteEnumeratedSet(SymmetricGroup(3))
> > {(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)}
> > But SymmetricGroup(3) is already in the category Sets
> > sage: SymmetricGroup(3) in Sets()
> > True
> > So there should be no need to call explicitely the forgetful functor.
> > In particular I don't see the point of creating another sage object for those
> > case. Otherwise said, I only see the reason to create a new sage object for
> > building a Set, when the object is not a sage Parent in the category Sets, eg:
> > python list, set, frozenset ...
>
> As far as I know "Set" is not (yet) a functor (unless we can apply it
> to group homomorphisms), but just the "underlying set" of a group.
That the point. As far As I know in sage + Nicolas category implantation any group
homomorphism is accepted as a Set homomorphism. So there it no need to apply
any function to compute the functor: Here is an example from the doc:
sage: from sage.categories.morphism import SetMorphism
sage: X.<x> = ZZ[]
sage: Y = ZZ
sage: Z = QQ
sage: phi_xy = SetMorphism(Hom(X, Y, Rings()), lambda p: p[0])
sage: phi_yz = SetMorphism(Hom(Y, Z, CommutativeAdditiveMonoids()), lambda
y: QQ(y)/2)
sage: bla = phi_yz._composition(phi_xy); bla
Composite map:
From: Univariate Polynomial Ring in x over Integer Ring
To: Rational Field
Defn: Generic morphism:
From: Univariate Polynomial Ring in x over Integer Ring
To: Integer Ring
then
Generic morphism:
From: Integer Ring
To: Rational Field
sage: bla.category_for()
Category of commutative additive monoids
So if you compose a Rings()-morphism and a CommutativeAdditiveMonoids()-morphism
you get a CommutativeAdditiveMonoids()-morphism.
> As
> of why we might need to call it, one can think of the same underlying
> set {a,b,c,d} having two different group structures (isomorphic to ZZ/
> 2ZZ x ZZ/2ZZ or Dihedral(4)) as groups, these would be different (even
> non-isomorphic), but as sets they are the same (i.e. the forgetful
> functor is not injective on objects).
That a mathematical way to *think* about it. It is not at all implementable in
sage, since a,b,c,d can't have both Z2Z2 := ZZ/2ZZ x ZZ/2ZZ and Dihedral(4) as
parent. So you must have different objects for a,b,c,d in Z2Z2 and a,b,c,d in
Dihedral(4). You can trick equal to answer that the first a is equal to the
second one but it's to me just a trick.
The usual way (at least to people coming from MuPAD-Combinat) to deal with
this kind of problem is to have two different parents ZZ/2ZZ x ZZ/2ZZ and
Dihedral(4) with different elements together with an isomorphism in the
category of Sets. That's the usual problem that very often in mathematical we
use to call equal things that actually are only isomorphic.
> This, mathematically. As of the
> implementation within sage, I agree one would think that the quickest
> way to apply it is just not to use the extra structure that has been
> previously defined, but I don't know the details on the implementation
> well enough to say anything intelligent about this.
So I'm waiting if someone else has an idea.
Cheers,
Florent