faster permutations, based on what rdeits suggested

[natemcintosh]

I finally learned how to make a pull request, based on this issue

Here I copied in the code that rdeits originally wrote here

I also updated the tests to use testsets, which provides a slightly nicer user interface when testing.

I also ran the Julia formatter on the files I edited, which made some whitespace changes. Unfortunately github's differ isn't the best at figuring out what whitespace changed, so it might look a little confusing

[codecov[bot]]

Codecov Report

Base: 96.85% // Head: 96.97% // Increases project coverage by +0.12% :tada:

Coverage data is based on head (8852542) compared to base (d1b633b). Patch coverage: 100.00% of modified lines in pull request are covered.

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #122      +/-   ##
==========================================
+ Coverage   96.85%   96.97%   +0.12%     
==========================================
  Files           7        7              
  Lines         700      728      +28     
==========================================
+ Hits          678      706      +28     
  Misses         22       22              

Impacted Files	Coverage Δ
src/permutations.jl	100.00% <100.00%> (ø)

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

[natemcintosh]

Before

@benchmark foreach(identity, Combinatorics.permutations(1:2000, 2))
BenchmarkTools.Trial: 1 sample with 1 evaluation.
 Single result which took 10.268 s (30.58% GC) to evaluate,
 with a memory estimate of 60.47 GiB, over 11994001 allocations.

and after

@benchmark foreach(identity, Combinatorics.permutations(1:2000, 2))
BenchmarkTools.Trial: 39 samples with 1 evaluation.
 Range (min … max):  128.003 ms … 132.626 ms  ┊ GC (min … max): 8.80% … 9.58%
 Time  (median):     130.014 ms               ┊ GC (median):    9.60%
 Time  (mean ± σ):   130.239 ms ±   1.225 ms  ┊ GC (mean ± σ):  9.38% ± 0.41%

  █              █▃█   ▃  ▃  ▃              █   █                
  █▁▁▁▁▁▇▁▁▁▁▁▁▁▁███▁▇▁█▁▇█▇▇█▁▁▇▁▁▁▇▁▁▇▁▁▁▇█▇▁▁█▇▇▁▇▁▇▁▁▇▁▁▁▁▇ ▁
  128 ms           Histogram: frequency by time          133 ms <

 Memory estimate: 427.03 MiB, allocs estimate: 7996001.

[bkamins]

CC @mschauer @rdeits

[natemcintosh]

Hitting an issue with @inferred on Julia 1.0. I tried using juliaup to download 1.0 on my computer and run it, but couldn't get it to download. Does anyone know of a place I can more run 1.0 to check out what's happening?

EDIT: looks like I'm hitting this issue

[bkamins]

Does anyone know of a place I can more run 1.0 to check out what's happening?

I normally just download binaries from https://julialang.org/downloads/oldreleases/ and install it manually when needed.

[bkamins]

OK - looks good. Now someone not involved in development of the code should review it. (thank you in advance)

[natemcintosh]

Would it be worth posting on discourse to find someone willing to review? I can definitely do that

[mschauer]

Often it is also helpful if you go on record and state if you think yourself that this is ready to be merged and let loose on the world.

[natemcintosh]

Hi @mschauer, good idea. I have made a thorough review of it (now over a month since I last looked at it), as well as spent more time playing around with the new version. I believe the new version is reliable, much faster (the reason for this pull request), and ready for public use.

[bkamins]

@mschauer - can you please review it? I was involved in the implementation so a second set of eyes is required. (or who else from JuliaMath could be recommended?)

[ararslan]

Why change the name of the type from Permutations to PermutationIterator? The new name is inconsistent with how other types in this package are named, e.g. Combinations and MultiSetCombinations. Also, though not exported under the old name, other packages may be defining methods for that type.

[natemcintosh]

Why change the name of the type from Permutations to PermutationIterator? The new name is inconsistent with how other types in this package are named, e.g. Combinations and MultiSetCombinations. Also, though not exported under the old name, other packages may be defining methods for that type.

Good point. I'll fix that