Disjoint Sets --> iter

[elixyre]

Hi,

I want append a simple shortcut for iter elements of the class : DisjointSet?.

[elixyre]

shortcut DisjointSet?.iter

[tscrim]

A few things I would like to see:

• Reference the ticket number in the commit message
• Use double quotes instead of single quotes for consistency
• Since dictionaries are non-deterministic in their ordering, could you change the last test to something like

  sage: L = [s for s in d]
  sage: len(L)
  3
  

Also you probably could just return self.root_to_elements_dict().itervalues() since it is an iterator object (it avoids a level of indirection).

Thanks,
Travis

PS - I'm assuming this was suppose to be set to needs_review. Sorry if it wasn't.

[elixyre]

I made a new version. It's ok with that?

Furthermore, I added a new method _getitem_ which return the set associated to the argument:

sage: d =  DisjointSet(range(4))
sage: d.union(1,2); d
{{0}, {1,2}, {3}}
sage: d[2]
[1,2]

(My opinion is when we write d.find(2) we expect [1,2] and not 1 (that means nothing for user) but I don't want reimplement all so... what is your opinion about that?)

Thanks,

Jean-Baptiste

[tscrim]

From the ​wikipedia page, find() returns the representative of the subset, not the entire subset. As such, to be consistent with find() and the expected behavior of DisjointSet, I think __getitem__() should return the representative as well.

Thanks,
Travis

[slabbe]

(My opinion is when we write d.find(2) we expect [1,2] and not 1 (that means nothing for user) but I don't want reimplement all so... what is your opinion about that?)

The data structure is made so that knowing if two elements a and b are in the same subset is optimal in time complexity : d.find(a) == d.find(b). Returning the whole subset containing the element 2 is another question and its time complexity is very different (you need to call find on every elements...).

Are you sure you need the union-find data structure for your problem?

[elixyre]

No i'm okay with that. So I modify my patch to be consistent.

[tscrim]

I still think __getitem__ should be the same as find(). In particular, I'd just set

__getitem__ = find

and add a doctest to the class/module doc. If you want a method to return the full subset, you should call it something like get_subset(). Also could you make the first line of your comment message be a short description of the patch.

Thanks,
Travis

[elixyre]

Hi,

Last time I answered little bit quickly (and my code is false). For me, a disjoint union is roughly a list of list (set of disjoint sets) with two particular method union and find. It seems natural (and consistent with the representation), if there is a _getitem_ method that returns one of these lists. It will be disturbing and irrelevant to have

__getitem__ = find

And if you are agree with that my question is : what's the input? An element in the union of the sets or an indice? I think it could be interesting to have an element. (I imagine a disjoint sets on all permutations of size k, it seems cool and agradable to visualize easily the class of a particular permutation)

Thanks,

Jean-Baptiste

[tscrim]

You're forgetting that this is not a dijoint union as a mathematical object but a specific data structure of DisjointSet which is not a list of lists. In some sense, there is less structure as DisjointSet is better described as a map from elements to a representative (in particular the subsets are not ordered). Thus the most logical behavior to me is that __getitem__() should match find().

Actually considering that, the iterator should the representatives (i.e. the iterkeys()) and not the subsets.

To reiterate, this is a tool (class) used to solve problems efficiently, not to represent a mathematical structure. The mathematical structure you're after would either be DisjointUnionEnumeratedSets or SetPartitions. If you really want to return the whole subset from an element, this should get its own specialized method.

Best,
Travis

[slabbe]

I suggest to close this ticket as a duplicate of #20057.

[embray]

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).