Move most combinatorics code out of Base

[jiahao]

This PR extracts all combinatorics functions from Julia's Base library, except for:

• binomial,
• factorial, and
• gamma
• edit: and basic functions for permutations: isperm, invperm, permute!, ipermute!
• and nextprod which is used in Base.DSP

All other functions are to be migrated to https://github.com/JuliaLang/Combinatorics.jl

See: JuliaMath/Combinatorics.jl#8

Ref: #5155

[tkelman]

these should throw specific errors saying they're now in Combinatorics.jl

the permutation functions like invperm that work on vectors of ints might be small and generally useful enough to leave in for now, but the special types should move.

[jiahao]

How should we handle the deprecations? The easiest thing I can think of is to add catchall methods like combinations(args...) = error("You need Combinatorics.jl now.") to deprecated.jl.

[JeffBezanson]

Agree; I would keep isperm, invperm, permute!, and ipermute!. I could go either way on factorial and gamma. Unfortunately the DSP code uses nextprod. Not sure what to do about that.

[jakebolewski]

Put the DSP code in a package?

[tkelman]

I like the phrasing that was done for the PkgDev moves

julia/base/pkg.jl

Line 63 in ce2500e

register(args...) =

Though since these were exported, want to make sure Combinatorics.jl can extend them properly.

[jiahao]

Looks like rudimentary support for permutations is needed in Base, so I'll plan to put back

• isperm
• invperm
• permute!/!!
• ipermute!/!!

I'll also leave nextprod in with a note about its removal when DSP is removed.

[jiahao]

Should be ready for review

[KristofferC]

Should there be a news entry for this?

[tkelman]

Yes.

[tkelman]

These need to be manually removed from the rst docs. Again, keeping them in sync at the same time is a much clearer way to go right now.

[sbromberger]

This introduces a problem: in 0.4 0.5, when using Combinatorics is included (for combinations()), there's an error since there's now a name conflict with Base. I guess this is unavoidable?

[yuyichao]

No it doesn't introduce any problem on 0.4. Combinators 0.3.0 requires julia 0.5+ and you shouldn't use it with julia 0.4.

[sbromberger]

I misspoke - it's actually nightly builds that are affected:

WARNING: both Combinatorics and Base export "combinations"; uses of it in module LightGraphs must be qualified
...
ERROR: LoadError: LoadError: UndefVarError: combinations not defined

See https://travis-ci.org/JuliaGraphs/LightGraphs.jl/jobs/90627799 for details.

[jiahao]

Yes, you will have to bear with the warning until the nightly builds are updated. A temporary workaround is to qualify the usage as the warning suggests:

import Combinatorics: combinations

I do this in the Combinatorics tests on master.

[tkelman]

The nightly in that run was from today. I think Combinatorics.jl should be checking if isdefined(Base, :combinations) and if so importing it to extend it with new methods.

[sbromberger]

Warnings I can handle, but it's followed by an error (see edited comment). It stinks because the "failed build" badge shows up on the project's home page as a result, and integration tests for PRs are all failing. I'm fully qualifying it now.

[jiahao]

Oh good point. I'll have to import all these functions from Base for the entire 0.5 cycle since there will still be the methods left that throw the errors.

[tkelman]

Yes, though it'll be a little more future-proof if you use isdefined or a try-catch rather than version number comparisons.

[sbromberger]

Thanks for the quick response. Let me know if/how I can help.

[jiahao]

I'm not going to write isdefined(:...) for 8 different functions.

[tkelman]

Please don't use a version number comparison, do a feature check. Otherwise the versions of the package you write now are guaranteed to break as soon as the deprecations get removed.

edit: hrm, maybe I spoke too soon, importing something nonexistent is only a warning? Did not expect that. Still, version number checks are just generally brittle and bad practice, and don't work when you do a NO_GIT build.

[jiahao]

I've included an isdefined check on Base.combinations, on the premise that we will excise all 8 deprecation errors at once.

[sbromberger]

OK, I'm a bit confused here. How is one supposed to write code that uses combinations() that works on 0.4 and 0.5? I can't put Combinatorics.jl in REQUIRE, since trying to Pkg.add() it causes a 0.4 failure ("ERROR: Combinatorics can't be installed because it has no versions that support 0.4.2-pre+3 of julia."), and omitting it in 0.5 throws the error about having combinations() now in Combinatorics.

Advice greatly appreciated. Thanks.

[jpfairbanks]

Could you tag a version of Combinatorics.jl that only supports 0.4.X and just re-exports the functions from Base?

[yuyichao]

There shouldn't be any problems. Combinatorics 0.2.0 should work fine on 0.4.0.

Tested on JuliaBox

julia> Pkg.update()                                                              
INFO: Initializing package repository /home/juser/.julia/v0.4
INFO: Cloning METADATA from git://github.com/JuliaLang/METADATA.jl
INFO: Updating METADATA...
INFO: Computing changes...
INFO: No packages to install, update or remove

julia> Pkg.add("Combinatorics")                                                  
INFO: Cloning cache of Combinatorics from git://github.com/JuliaLang/Combinatoric
s.jl.git
INFO: Updating cache of Compat...
INFO: Cloning cache of Iterators from git://github.com/JuliaLang/Iterators.jl.git
INFO: Cloning cache of Polynomials from git://github.com/Keno/Polynomials.jl.git
INFO: Installing Combinatorics v0.2.0
INFO: Installing Compat v0.7.7
INFO: Installing Iterators v0.1.9
INFO: Installing Polynomials v0.0.4
INFO: Package database updated

Note that you shouldn't require Combinatorics 0.3.0 or higher.

[sbromberger]

Ah, that's likely the issue - I had 0.3.1 specified in REQUIRE. Let's see what happens when I remove the version.

[tkelman]

The issue is that Combinatorics 0.2.0 only supports releases of 0.4 JuliaLang/METADATA.jl@b7b955a, and Combinatorics 0.1.2 and earlier require Polynomial which is deprecated on 0.4. @sbromberger can you safely upgrade from an rc to release 0.4.1?

[sbromberger]

@tkelman I can, but what about the users of the package? I'd hate to leave folks out in the cold.

ETA: and I'm on 0.4.2-pre+3, so I'm a bit puzzled.

[yuyichao]

@tkelman It's 0.4.2-pre not 0.4.0-rc2

[tkelman]

Actually Polynomial should only be deprecated for releases of 0.4, so my mistake, the issue was the version number of Combinatorics you were trying to require. Pkg resolution failures don't always give the most informative errors right now, there are one or two issues on this.

[sbromberger]

Thanks for the prompt responses (as usual!) - testing LG now without version numbers in Combinatorics.

There are lots of moving parts these days, and trying to keep the packages testing cleanly on both 0.4 and 0.5 is taxing work.

ETA: ok, removing the version number fixes the problems on 0.4 and 0.5. (now to figure out the other failures.) Thanks again.

[coveralls]

Coverage decreased (-20.8%) to 61.053% when pulling 93911dd on cjh/rm-combi into 94f31d1 on master.