IntegerVectors_nk.rank() specialization

[fph]

Currently IntegerVectors_nk inherits the generic rank() implementation for its parent; it's a very generic method that generates all its members and checks for equality. I needed a faster implementation in my code, so I wrote a specialized version that uses an ad-hoc algorithm (nothing fancy, essentially it's just adding up a bunch of binomials).

I plan to upload the code using git and the standard dev tools. I'm a new contributor, so it could take me a while to set everything up and commit code -- I am currently in the process of building a dev version for the first time.

CC: @nathanncohen

Component: combinatorics

Keywords: integervectors, rank

Author: Federico Poloni

Branch/Commit: u/f.poloni/ticket/15609 @ 06856f6

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/15609

[fph]

Attachment: integer_vector_ranking.patch.gz

[fph]

Branch: u/f.poloni/ticket/15609

[fph]

Author: Federico Poloni

[fph]

Commit: f616301

[fph]

comment:3

Committed using git and the dev-tools the code in the attached patch, after many difficulties setting up the environment as a first-time contributor. :(

---

New commits:

f616301

Implemented IntegerVectors_nk.rank(). Fixes #15609

[nathanncohen]

comment:4

Hellooooooooooooooo Federico !

Well, I don't know what you went through, but the patch looks nice in the end ;-)

It's a cool improvement, and it is well documented and tested. I have only one thing to add :

sage: IV = IntegerVectors(4,5) 
sage: IV.rank((0,0,4,0,0)) 
55
sage: IV.rank((0,1,-1,4,0))
55

That's because you check manually whether the given vector belongs to IV instead of using the __contains__ method, i.e. x in self.

The problem with this x in self is that it also computes the sum of the vector, and that you will compute it a second time in your function because you need it too. But that may not be soooo troublesome anyway, it's not that costly. Especially compared with the current implementation.

Could you fix that ? Also, could you replace
- ``x`` - any sequence with sum(x) == n and len(x) == k i
n the docstring with that ?
- ``x`` - any sequence with ``sum(x) == n`` and ``len(x) == k``

This way it will all appear properly in the html documentation. Which you can obtain with sage -b && sage -docbuild reference/combinat html

Thanks !

Nathann

[fph]

comment:5

Thanks for taking a look at the patch. You are correct about the negative entries, good catch; I'll fix it.

Actually there is another point I was considering. The members of IntegerVectors are lists; what should we do when another sequence type such a tuple is passed to rank()?

The implementation in the current patch returns the same result for any sequence type, however using __contains__ would require them to be lists or else it would throw an error.

Combinations.rank() throws TypeError when passed a tuple; Derangements.rank() returns nothing (no error thrown).

This is an issue of strict type correctness vs. user convenience. For instance, you inadvertently used a tuple in your example in the previous comment. :)
It is ultimately a developer decision; please let me know what I should return in case a tuple is entered and I shall code it.

[nathanncohen]

comment:6

Hellooooooooooooooo !!!

Thanks for taking a look at the patch. You are correct about the negative entries, good catch; I'll fix it.

Actually there is another point I was considering. The members of IntegerVectors are lists; what should we do when another sequence type such a tuple is passed to rank()?

Hmmmmmmm....

The implementation in the current patch returns the same result for any sequence type, however using __contains__ would require them to be lists or else it would throw an error.

Well, I think that it would make sense anyway to only return the rank of objects on which __contains__ return True. But indeed tuples make sense too. Well, why don't we also allow tuples in __contains__ ? It doesn't look that crazy :-)

Combinations.rank() throws TypeError when passed a tuple; Derangements.rank() returns nothing (no error thrown).

I hate this code. This has to be FIXED. I will create a ticket for that and add you in Cc (it should only take a couple of seconds to review).

What has to be known about this code is that it is inconsistent in many places, and that we should never feel forced to respect what is done elsewhere, for I learned it was mistakes most of the time :-P

I think rank should throw a ValueError when __contains__ returns False on the input. What's your opinion ? Returning nothing is just plain bad programming.

This is an issue of strict type correctness vs. user convenience. For instance, you inadvertently used a tuple in your example in the previous comment. :)
It is ultimately a developer decision; please let me know what I should return in case a tuple is entered and I shall code it.

Well, I really feel that what should be called there is __contains__, and that we should play with what __contains__ allow if it is not convenient. But let's be consistent with ourselves for a start.

Please code it this way only if it makes sense to you. Otherwise let's talk about it. And I will write this quick patch for the other problem you found.

Have fuuuuuuuuuuuuun !

Nathann

[nathanncohen]

comment:7

I asked a question on sage-combinat-devel about this .rank function that returns nothing.

https://groups.google.com/forum/#!topic/sage-combinat-devel/YUEVBIUzOv4

Turns out it is a deliberate choice.

Nathann

[sagetrac-git]

Changed commit from f616301 to 06856f6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

06856f6

test for membership with `x in self`; minor doc formatting change

[fph]

comment:9

I agree with you on all respects (except maybe that I think that for most sequences the generic inherited rank implementation is still better than no implementation, but that's a minor unrelated issue).
"Return NULL or raise an exception on failure" is an old programming style debate, but I agree that it should be more Pythonic to raise an exception.

As for the choice of sequences, also in my view it would be good not to force a specific one on the user, at least in methods that take them as inputs, but that's a different and broader issue.

Anyway, I have applied your suggested changes (testing for membership with x in self, and that formatting correction in the docs).

---

New commits:

06856f6

test for membership with `x in self`; minor doc formatting change

[nathanncohen]

comment:10

Okayyyyyyyyyyyyyyyyyyyy ! Then it can go. Thanks for that patch ! ;-)

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:13

Wow. From created to merged in 5 days. That was fast :-P

Nathann

[vbraun]

comment:14

See #15639 for a bug that was most likely introduced here.

[nathanncohen]

comment:15

Weird O_o

Nathann