Opened 7 years ago

Closed 7 years ago

#14140 closed enhancement (fixed)

Reorganization of set partitions

Reported by: stumpc5 Owned by: sage-combinat
Priority: major Milestone: sage-5.9
Component: combinatorics Keywords: set partitions
Cc: VivianePons, hivert, chapoton, chrisjamesberg, saliola, ghseeli Merged in: sage-5.9.beta3
Authors: Travis Scrimshaw Reviewers: Chris Berg
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13605, #12415 Stopgaps:

Description

Set partitions need to be completely reorganized. In particular, there is no element class, and it is not possible to construct a set partition

sage: SetPartition([[1,3],[2,4]])

It would be great to have in order to provide statistics on set partitions.

Attachments (1)

trac_14140-remove_cc_set_partitions-ts.patch (78.9 KB) - added by tscrim 7 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 7 years ago by chrisjamesberg

Also, right now there are 9 different classes of set partitions, hopefully this could all be merged into a single class.

comment:2 Changed 7 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Milestone changed from sage-wishlist to sage-5.8

I don't know how possible it will be to get it into 1 class, but maybe 2: one for ordered, one for unordered. I'll see what I can do since I also want to remove instances of CombinatorialClass.

comment:3 Changed 7 years ago by chrisjamesberg

  • Cc saliola added

I'm cc'ing Franco on this too because he implemented NCSYM and must have come across this problem at some point. Perhaps he already has his own nice implementation for set partitions.

comment:4 Changed 7 years ago by saliola

Here are the relevant patches on the sage-combinat queue:

  • set-partition-fs.patch (currently guarded)
  • hopf_algebra_of_supercharacters-fs.patch
  • scha-cleanup-fs.patch

Feel free to extract whatever you find useful!

comment:5 Changed 7 years ago by ghseeli

  • Cc ghseeli added

comment:6 follow-up: Changed 7 years ago by tscrim

  • Status changed from new to needs_review

comment:7 in reply to: ↑ 6 Changed 7 years ago by stumpc5

Replying to tscrim:

The patch has several nontrivial rejects, please check!

comment:8 Changed 7 years ago by chrisjamesberg

Looks like it just needs rebasing.

comment:9 Changed 7 years ago by tscrim

  • Dependencies set to #13605

The partition options patch touches this, added that to the dependencies.

comment:10 Changed 7 years ago by chrisjamesberg

Looks like the patch has many doctest errors. If you fix these, I will review it.

comment:11 Changed 7 years ago by chrisjamesberg

Also, I'd like to see some of the trivial doctests, such as:

sage: SetPartition([])
{}

etc...

comment:12 Changed 7 years ago by chrisjamesberg

Also, I would like to see a method like to_partition which takes a set partition to the underlying partition. Ideally this method would have the decorator @combinatorial_map.

comment:13 Changed 7 years ago by ghseeli

I have been doing some work on diagram / partition algebras, which make extensive use of SetPartitions in their implementation. I think these modifications are definitely helpful. I would like to point out though that there is actually already a method within Sage to convert a list to a set partition, contained under sage.combinat.partition_algebra called "to_set_partition." That being said, this reorganization is definitely needed because the current SetPartitions class is a pain to work with when you only want specific ones.

Also, Chris, what are the 9 different classes of set partitions currently in Sage? Are all of these encompassed by this patch, or do they need more work? I am almost done with some code that would implement structures such as "SetPartitionsAk" as an algebra, since they are better understood and used that way.

comment:14 Changed 7 years ago by tscrim

Right now this just groups OrderedSetPartitions and SetPartitions under one abstract base class (with common code factored out). There are different classes depending upon what type of input since they iterate differently and some have cardinality shortcuts. There are two big things this patch does, first is remove CombinatorialClass, the second is a proper element is implemented for each of these parent objects.

I'm going to look into partition_algebra next chance I get since there are currently multiple doctest failures in there. Is there anything in particular besides a to_partition() method that you'd want from this?

comment:15 Changed 7 years ago by chrisjamesberg

I'm naive as to why there are so many of them, but when I tab complete SetPartition I get:

SetPartitions     
SetPartitionsIk   
SetPartitionsRk   
SetPartitionsAk   
SetPartitionsPRk  
SetPartitionsSk   
SetPartitionsBk   
SetPartitionsPk   
SetPartitionsTk

comment:16 Changed 7 years ago by ghseeli

Travis, I have been working on some code to refine partition_algebra since Sage Days 38 last summer. I have just posted it to trac so that you can view it (#14234). There is still some work to be done (doctests are not perfect, although it did pass when I ran it today.) My code, however, would be refined greatly by some of your implementations in this patch.

Chris, all the SetPartitions? with a letter and k after them are from partition_algebra. It seems to me that these structures, while represented by set partitions, are better understood as algebras, as explained in the ticket.

comment:17 Changed 7 years ago by tscrim

I've uploaded the new version of the patch which fixes partition_algebra.py and the other misc doctests. I also made to_partition an alias for shape and added the combinatorial map decorators.

I would like to have the classes SetPartitionsXk removed from the global namespace and instead created through one unified interface/UniqueFactory (if even necessary) such as in CartanType. However I don't feel like taking care of that here.

comment:18 Changed 7 years ago by chrisjamesberg

SetPartition({{1,3}, {2}}) returns an error. You should be able to use the _repr_ to recreate the object, no?

Last edited 7 years ago by chrisjamesberg (previous) (diff)

comment:19 Changed 7 years ago by tscrim

I've fixed the last doctests. As for the {{1,3},{2}}, that is a shortcoming of python and what you would need is a change to the sage preparser. There's also many instances in sage in which the repr is not something you can feed it back in (ex. any parent or particular roots).

comment:20 Changed 7 years ago by stumpc5

I would appreciate if we could make the string representation of a set that is totally ordered to be ordered the same way. This is, each part is ordered increasingly, as are the sets by their first element:

Currently, I get

sage: SetPartition([[1,2,4],[3,5]])    
{{3, 5}, {1, 2, 4}}

but I would prefer to get

{{1, 2, 4}, {3, 5}}

Does that sound reasonable?

comment:21 Changed 7 years ago by tscrim

Should be fixed now.

comment:22 follow-up: Changed 7 years ago by tscrim

Fixed failing doctests.

comment:23 in reply to: ↑ 22 Changed 7 years ago by stumpc5

Replying to tscrim:

Fixed failing doctests.

This is a long patch, thanks Travis! I'd prefer if someone else could review it -- but I could also give it a quick review and let further complaints be solved in other tickets...

comment:24 Changed 7 years ago by chrisjamesberg

  • Reviewers set to Chris Berg
  • Status changed from needs_review to positive_review

comment:25 Changed 7 years ago by jdemeyer

  • Dependencies changed from #13605 to #13605, #12415
  • Status changed from positive_review to needs_work

This should be rebased to #12415.

comment:26 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

Rebased.

comment:27 Changed 7 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:28 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.9.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.