juliamath / combinatorics.jl Goto Github PK

I believe it would be useful to add a method to generate permutations with repetitions, so that, for example

julia> collect(with_replacement_permutations(1:2, 2))
4-element Vector{Vector{Int64}}:
 [1, 1]
 [1, 2]
 [2, 1]
 [2, 2]

A possible implementation could be the following

struct WithReplacementPermutations{T}
    a::T
    t::Int
end

Base.eltype(::Type{WithReplacementPermutations{T}}) where {T} = Vector{eltype(T)}

Base.length(p::WithReplacementPermutations) = length(p.a)^p.t

"""
    with_replacement_permutations(a, t)

Generate all permutations with replacement of size `t` from an array `a`.
"""
with_replacement_permutations(elements::T, len::Integer) where {T} =
    WithReplacementPermutations{T}(unique(elements), len)

function Base.iterate(p::WithReplacementPermutations, s = ones(Int, p.t))
    (!isempty(s) && s[end] > length(p.a) || (isempty(s) && p.t > 0)) && return
    nextpermutationwithreplacement(p.a, p.t, s)
end

function nextpermutationwithreplacement(a, t, state)
    cur = a[state]
    n = length(state)
    state[1] += 1
    local i = 1
    while i < n && state[i] > length(a)
        state[i] = 1
        state[i+1] += 1
        i += 1
    end
    return cur, state
end

It might be worthwhile to combine the combinations and with_replacement_combinations functions. I could see a potential API as

combinations(x, n)               # No replacement
combinations(x, n, replace=true) # With replacement

Having separate functions was probably worthwhile in The Olden Days, when keyword arguments were a performance killer and value-based dispatch with Val didn't exist.

The partitions iteration does not seem to be type stable. One way of seeing this:

julia> collect(partitions(1:3))
5-element Array{Any,1}:
 Array{Int64,1}[[1,2,3]]    
 Array{Int64,1}[[1,2],[3]]  
 Array{Int64,1}[[1,3],[2]]  
 Array{Int64,1}[[1],[2,3]]  
 Array{Int64,1}[[1],[2],[3]]

I would have expected a result of type Array{Array{Int64,1},1}.

Another way to see the instability:

using Combinatorics

function main()
    for ptn in partitions(1:3)
    end
end

@code_warntype main()

returns (in part)

Variables:
  #self#::#main
  #temp#::Tuple{Array{T,1},Array{T,1},Int64,Any}
  ptn::Any
  n::Int64

As the title suggests:

julia> first(permutations(first(combinations(1:2,0))))
0-element Array{Any,1}

the following error is raised:

julia> Pkg.add("Combinatorics")
WARNING: fetch: GitError(Code:ERROR, Class:Net, SSL error: error:140E0114:SSL routines:SSL_shutdown:uninitialized)
ERROR: Base.Pkg.PkgError("Combinatorics can't be installed because it has no versions that support 0.5.0-dev+1190 of julia. You may need to update METADATA by running Pkg.update()")
in resolve at ./pkg/entry.jl:420
in edit at pkg/entry.jl:414
in anonymous at task.jl:447
in sync_end at ./task.jl:413
[inlined code] from task.jl:422
in add at pkg/entry.jl:57
in add at pkg/entry.jl:78
in anonymous at pkg/dir.jl:31
in cd at file.jl:22
in cd at pkg/dir.jl:31
[inlined code] from pkg/dir.jl:25
in add at pkg.jl:26
in eval at ./boot.jl:264

My julia version:
_
_ _ ()_ | A fresh approach to technical computing
() | () () | Documentation: http://docs.julialang.org
_ _ | | __ _ | Type "?help" for help.
| | | | | | |/ ` | |
| | || | | | (| | | Version 0.5.0-dev+1188 (2015-11-08 18:30 UTC)
/ |_'|||__'| | Commit e9af3f6 (0 days old master)
|__/ | x86_64-linux-gnu

function f()
           idx = 1
           p = zeros(2^3)
           for iter in combinations(1:3,3)
               p[idx] = sum(iter)
               idx+=1
           end
           p
       end
f (generic function with 1 method)

julia> f()
8-element Array{Float64,1}:
 6.0
 0.0
 0.0
 0.0
 0.0
 0.0
 0.0
 0.0

vs.

julia> function g()
           idx = 1
           p = zeros(2^3)
           for iter in (x for x in 1:3)
               p[idx] = sum(iter)
               idx+=1
           end
           p
       end
g (generic function with 1 method)

julia> g()
8-element Array{Float64,1}:
 1.0
 2.0
 3.0
 0.0
 0.0
 0.0
 0.0
 0.0

Just loading the Combinatorics package on 0.4 throws a huge number of warnings, which leads to pretty poor user experience:

julia> using Combinatorics
WARNING: Method definition levicivita(AbstractArray{#T<:Integer, 1}) in module Base at combinatorics.jl:611 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/permutations.jl:188.
WARNING: Method definition partitions(Integer) in module Base at combinatorics.jl:252 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/partitions.jl:26.
WARNING: Method definition partitions(Integer, Integer) in module Base at combinatorics.jl:318 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/partitions.jl:93.
WARNING: Method definition partitions(AbstractArray{T<:Any, 1}) in module Base at combinatorics.jl:380 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/partitions.jl:158.
WARNING: Method definition partitions(AbstractArray{T<:Any, 1}, Int64) in module Base at combinatorics.jl:447 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/partitions.jl:228.
WARNING: Method definition permutations(Any) in module Base at combinatorics.jl:219 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/permutations.jl:24.
WARNING: Method definition nthperm!(AbstractArray{T<:Any, 1}, Integer) in module Base at combinatorics.jl:70 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/permutations.jl:136.
WARNING: Method definition prevprod(Array{Int64, 1}, Any) in module Base at combinatorics.jl:565 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/partitions.jl:354.
WARNING: Method definition combinations(Any, Integer) in module Base at combinatorics.jl:182 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/combinations.jl:42.
WARNING: Method definition nthperm(AbstractArray{#T<:Integer, 1}) in module Base at combinatorics.jl:92 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/permutations.jl:161.
WARNING: Method definition nthperm(AbstractArray{T<:Any, 1}, Integer) in module Base at combinatorics.jl:89 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/permutations.jl:157.
WARNING: Method definition factorial(#T<:Integer, #T<:Integer) in module Base at combinatorics.jl:56 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/factorials.jl:18.
WARNING: Method definition factorial(Integer, Integer) in module Base at combinatorics.jl:66 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/factorials.jl:28.
WARNING: Method definition parity(AbstractArray{#T<:Integer, 1}) in module Base at combinatorics.jl:642 overwritten in module Combinatorics at /Users/tamasnagy/.julia/v0.4/Combinatorics/src/permutations.jl:221.

I know that this was fixed in Base by JuliaLang/julia#16125, but 0.4 is still the official release.

If you change the type of the dict to Dict{BigInt,BigInt} in this line

https://github.com/JuliaMath/Combinatorics.jl/blob/master/src/partitions.jl#L58

then length(partitions(n)) returns correct results for larger values of n. The largest
result that can be represented by Int64 is for n=405. If we have two routines and
test whether n>405, and use either a big int or machine int Dict, then the results are faster for n<405, but not type stable. If we just always use a big int dict, then the function is typestable, but a bit slower for n<405.

Hey there,
I was recently looking for an efficient way to enumerate permutations in-place, and I had to look in the source files to find nthperm!(a, k). Are there more super-useful but undocumented functions like this? Which ones should be added to the README?

EDIT: slightly simplified

using Combinatorics
dim = 3
deg = 5
for i in 1:deg
	for m = 1:dim, alpha in partitions(i, m)
         append!(alpha, zeros(Int64, dim - length(alpha)))
      @show alpha
   end
end

Fails with ERROR: UndefVarError: j not defined. Replacing it with

using Combinatorics
dim = 3
deg = 5
for i in 1:deg
	for m = 1:dim, alpha in partitions(i, m)
         append!(alpha, zeros(Int64, dim - length(alpha)))
      @show alpha
   end
end

works ok. Funny that . . .

(this happens on both v0.5.0 and master)

Would be nice to clear up all the warnings that are currently caused by the released version on Julia 0.4.

partitions(-1) should produce an error when it is constructed:

# error here
julia> partitions(-1)
Combinatorics.IntegerPartitions(-1)

julia> partitions(-1)|>collect
ERROR: ArgumentError: destination has fewer elements than required
Stacktrace:
 [1] copyto!(::Array{Any,1}, ::Combinatorics.IntegerPartitions) at ./abstractarray.jl:669
 [2] _collect at ./array.jl:550 [inlined]
 [3] collect at ./array.jl:544 [inlined]
 [4] |>(::Combinatorics.IntegerPartitions, ::typeof(collect)) at ./operators.jl:813
 [5] top-level scope at none:0

Noticed by Harmen Stoppels.

I have the following code that calculates the hooklength of a partition. I'll put in a PR when I get time:

function hooklength(σ::Vector{Int})
    ret = 1
    m = length(σ)
    for k = 1:m, j=1:σ[k]
        ret_2 = 0
        ret_2 += σ[k]-j
        for p = k:m
            σ[p] < j && break
            ret_2 += 1
        end
        ret *= ret_2
    end
    factorial(sum(σ)) ÷ ret
end

surprising that the empty combination is not included
also surprising it's not called "subsets"

permutations() seems slower than it should be. Below is the example I discovered this with.

I have an array of strings, of length ~2,000. I would like to produce all permutations of lengths 1 to n (n in my application will always be less than or equal to 2).

My attempt is

import Combinatorics

"Return all permutations of sizes 1:`max_length`"
function power_permutations(iterable, max_length)    
    Iterators.flatten(Combinatorics.permutations(iterable, r) for r in 1:max_length)
end

and simply running through it we get

using BenchmarkTools

@benchmark foreach(identity, power_permutations(collect(1:2_000), 2))

BenchmarkTools.Trial: 
  memory estimate:  60.80 GiB
  allocs estimate:  20000015
  --------------
  minimum time:     17.592 s (36.62% GC)
  median time:      17.592 s (36.62% GC)
  mean time:        17.592 s (36.62% GC)
  maximum time:     17.592 s (36.62% GC)
  --------------
  samples:          1
  evals/sample:     1

Woah, that is a lot of memory.

Comparing to a similar version in Python.

import itertools

def power_permutations(iterable, max_length):
    "Return all permutations of sizes 1:`max_length`"
    for r in range(max_length + 1):
        yield from itertools.permutations(iterable, r)

%timeit len(list(power_permutations(list(range(2000)), 2)))                                                                                       
484 ms ± 8.73 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

A good deal faster than the Julia version.

With arrays of strings. In Julia:

@benchmark foreach(identity, power_permutations(collect(Iterators.repeated("hello",2_000)), 2))
BenchmarkTools.Trial: 
  memory estimate:  60.80 GiB
  allocs estimate:  20000015
  --------------
  minimum time:     17.404 s (36.79% GC)
  median time:      17.404 s (36.79% GC)
  mean time:        17.404 s (36.79% GC)
  maximum time:     17.404 s (36.79% GC)
  --------------
  samples:          1
  evals/sample:     1

And in Python:

%timeit len(list(power_permutations(["hello"]*2000, 2)))                                                                                          
473 ms ± 3.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

We see more or less the same performance.

multinomial internally uses binomial. While the latter check for overflow, the whole computation of multinomial is not checked for overflow, leading to :

multinomial(150, 150, 150, 150) --> error overflow reported by binomial
multinomial(15, 15, 15, 15) --> no error reported

See also this thread on Discourse.

Stirling numbers of the second kind are always nonnegative and yet:

julia> stirlings2(26,10)
-5247188700862703611

The same issue plagues stirlings1. We have

julia> stirlings1(26,10)
9107464261356742080

but the correct value is 196928100451110820242880.

The documentation for multiset_permutations does not seem to be auto-consistent:

multiset_permutations(m, f, t)

Generate all permutations of size t from an array a with possibly duplicated elements.

Is it ok to precompile a package that depends on Combinatorics.jl? All my dependencies have the option enabled, except this one.

while working with combinations() i noticed considerable performance difference between the runtime on python vs julia 0.5 and was wondering if I am doing something wrong?

runtime for walking over a subset of 3 items from a list for python 3.5 is 0.5022 seconds and similar code for julia takes 3 times more 1.55 seconds

Below is the sample code to reproduce the test

Python Code

import requests
import itertools
import time


def get_data(url):
  req = requests.get(url)
  lines = req.text.split("\n")
  return lines


def subsets(lst, num):
    for sub in itertools.combinations(lst, num):
        tmp=sub

if __name__ == "__main__":
    url = "https://raw.githubusercontent.com/spacefinity/sparespace/master/tools/city-list.txt"
    lst = get_data(url)

    st_time = time.clock()
    subsets(lst, 3)
    print("Elapsed time %2.4f seconds" % (time.clock()-st_time))

Elapsed time 0.5022 seconds

Julia Code

import Requests: get
import Combinatorics: combinations

function get_data(url)
  req = get(url)
  dat = readstring(IOBuffer(req.data))
  dat = split(dat, '\n')
end

function subsets(lst, num)
  for sub in combinations(lst, num)
    tmp=sub
  end
end

lst=get_data("https://raw.githubusercontent.com/spacefinity/sparespace/master/tools/city-list.txt");
@time subsets(lst, 3)

1.558682 seconds (56.66 M allocations: 2.814 GB, 15.34% gc time)

powerset(::Set) works, but returns Iterator.

julia> s
Set{Char} with 3 elements:
  'a'
  'c'
  'b'

julia> collect(powerset(s))
ERROR: MethodError: no method matching getindex(::Set{Char}, ::Int64)

collect(powerset(collect(s))) works as expected though.

I think it'd be nice to be able to work with set theory without syntactic issues like this, particularly for pedagogic purposes.

edit: sorry accidentally pressed enter and it made the issue.

see here:
JuliaLang/julia#13917

should be based on combinations

julia> ncpartitions(3)
ERROR: MethodError: `isless` has no method matching isless(::Array{Int64,1}, ::Array{Int64,1})
 in > at operators.jl:34
 in ncpart at /Users/dpsanders/.julia/v0.4/Combinatorics/src/partitions.jl:81
 in ncpart at /Users/dpsanders/.julia/v0.4/Combinatorics/src/partitions.jl:93
 in ncpartitions at /Users/dpsanders/.julia/v0.4/Combinatorics/src/partitions.jl:73

but works on 0.5:

julia> ncpartitions(3)
5-element Array{Array{Array{Int64,1},1},1}:
 [[1],[2],[3]]
 [[1],[2,3]]
 [[1,2],[3]]
 [[1,3],[2]]
 [[1,2,3]]

Could you please tag a new version of the package for the latest functionality?

For instance if I run

stirlings1(5,2)

it gives -10

While python's sympy and wikipedia says it's 50.

(@jiahao - edit for typo and code block formatting)

The function character(l, m) gives wrong results, e.g. the dimensions of representations (i.e. values at [1,1,...,1]):

N = 4
for λ in partitions(N)
    println("λ = $(rpad(λ,10))\t χ_λ($(ones(Int,N))) = ", character(λ, ones(Int,N)))
end

λ = [4] χ_λ([1,1,1,1]) = 1
λ = [3,1] χ_λ([1,1,1,1]) = 2
λ = [2,2] χ_λ([1,1,1,1]) = 2
λ = [2,1,1] χ_λ([1,1,1,1]) = 4
λ = [1,1,1,1] χ_λ([1,1,1,1]) = 1
are incorrect; these should be
λ = [4] χ_λ([1,1,1,1]) = 1 # sign repr
λ = [3,1] χ_λ([1,1,1,1]) = 3 # regular repr
λ = [2,2] χ_λ([1,1,1,1]) = 2 # repr via epimorphism to S₃
λ = [2,1,1] χ_λ([1,1,1,1]) = 3 # sign ⊗ regular
λ = [1,1,1,1] χ_λ([1,1,1,1]) = 1 # trivial

The results are incorrect for N≥4. For N≤3 the characters are correct. I think this is related to an incorrect dictionary key of

Moreover character([2,2,2,2], [8]) will result in BoundsError: attempt to access 6-element Array{Int64,1} at index [7]. This is due to the fact that MN1inner does not check if μ[t] (the length of the requested rim-hooks) is smaller than length(R). It should, and should return 0 otherwise (i.e. if no hooks of the requested length are found).

I originally proposed in JuliaLang/julia/#13767. It was suggested that Combinatorics.jl would make a better home.

I'd like to suggest that Combinatorics.jl import Base.combinations and define a new combination method that generates combinations of all orders. The implementation would have essentially the same behavior as the following:

using Iterators
Base.combinations(a) = chain([Base.combinations(a,k) for k=1:length(a)]...)

which allows for things like

julia>collect(combinations("abc"))
['a']        
 ['b']        
 ['c']        
 ['a','b']    
 ['a','c']    
 ['b','c']    
 ['a','b','c']

This pattern would be analogous to the partitions(m)/partitions(m,n) behavior that already exists in Base. This is a pattern that I have used in Julia recently and have implemented perhaps half a dozen times in various languages over the years. With the problem of iterating over orders being widespread in both theoretical calculations and experimental design, I suspect I am not the only one to use something like this.

Ref: https://discourse.julialang.org/t/package-compatibility-caps/15301

Would you be interested in having this implementation of multinomial exponents or something similar into Combinatorics.jl? https://github.com/juliohm/GeoStats.jl/blob/master/src/utils.jl#L38-L82

I depend on the package already, so I'd be happy to port the code. Please let me know if there is interest.

nthperm has moved to Combinatorics.jl yet I don't see it listed in the README. Could you please update the list?

Thank you.

┌ Warning: The start/next/done iteration protocol is deprecated. Implement `iterate(::Combinatorics.WithReplacementCombinations{Base.OneTo{Int64}})`.
│   caller = ip:0x0
└ @ Core :-1

got this while building my documentation. I assume it came from calling with_replacement_combinations

A user on stack overflow asked about whether Julia's partitions function could compute multisets. It can't, and shouldn't.

But a multisets(n, k) iterator might actually be useful in some cases. A naive, eager implementation would be:

multisets(n, k) = map(A -> [sum(A .== i) for i in 1:n],
                      with_replacement_combinations(1:n, k))

julia> multisets(2, 1)
2-element Array{Array{Int64,1},1}:
 [1,0]
 [0,1]

julia> multisets(3, 5)
21-element Array{Array{Int64,1},1}:
 [5,0,0]
 [4,1,0]
 [4,0,1]
 [3,2,0]
 [3,1,1]
 [3,0,2]
 [2,3,0]
 [2,2,1]
 [2,1,2]
 [2,0,3]
 ⋮      
 [1,2,2]
 [1,1,3]
 [1,0,4]
 [0,5,0]
 [0,4,1]
 [0,3,2]
 [0,2,3]
 [0,1,4]
 [0,0,5]

which is not so bad to write but horrible memory-wise. It'd probably be fine if map were lazy, but I couldn't find a decent lazy map implementation that did not make everything linked lists (and hence even worse).

Would there be room for such a function in this library? Alternatively, might we (or some other library) provide a fast lazy map, so that efficient versions of these functions can be written? I can prepare a pull request if there is demand.

(As an aside, I think multiset_combinations is named incorrectly: it means combinations_of_multisets. The current with_replacement_combinations is more akin to the multiset combinations (multichoose) operation.)

The readme doesn't list all the functionality, e.g. partitions isn't listed (and many more when i check the list of exported symbols). It's actually a bit hard to know they exist.

I can't find any API documentation site either. The functions are documented, so it should be straight forward to generate such sites, no? (I haven't had time to learn about API documentation generators in julia yet myself, I just assume it's straight forward)

While working on my own code for YoungDiagrams I encountered this:

λ = [5,3,2,2,1]
μ = [2,2,1]

m, n = length(λ), length(μ)
l = maximum(λ)
youngdiagram=zeros(Int, m, l)
for i=1:n
    youngdiagram[i, μ[i]+1:λ[i]]=1
end
for i=n+1:m
    youngdiagram[i, 1:λ[i]]=1
end
youngdiagram

produces

5×5 Array{Int64,2}:
 0  0  1  1  1
 0  0  1  0  0
 0  1  0  0  0
 1  1  0  0  0
 1  0  0  0  0

which is clearly not a rimhook (it's disconnected). however Combinatorics.isrimhook((λ, μ)) returns true.

Am I missing something obvious?

We are missing https://en.wikipedia.org/wiki/Composition_(combinatorics)
I think equivalent to unique(permutations(partitions(n))

For the compositions with bounded terms the total number is given by Fibonacci sequences: https://math.stackexchange.com/questions/3055314/number-of-compositions-of-n-such-that-each-term-is-less-than-equal-to-k

integer_partitions(n) should be deprecated in favour of partitions(n::Integer).

Additionally, partitions is not documented in the readme.

These functions currently do not behave the same:
In the 0 case, both are broken, the partitions case discussed in #79 :

julia> integer_partitions(0)
0-element Array{Array{Int64,1},1}

julia> partitions(0)|>collect
1-element Array{Array{Int64,1},1}:
 #undef

but should return [[]]

For n>0 the results of integer_partitions is sorted opposite to partitions:

julia> collect(partitions(3))
3-element Array{Array{Int64,1},1}:
 [3]
 [2, 1]
 [1, 1, 1]

julia> integer_partitions(3)
3-element Array{Array{Int64,1},1}:
 [1, 1, 1]
 [2, 1]
 [3]

Combinatorics appears to load correctly, but Julia can't find any of the package functions.

Julia 0.5.0, Ubuntu 16.04

julia> Pkg.add("Combinatorics")
INFO: No packages to install, update or remove
INFO: Package database updated

julia> Pkg.update()
INFO: Updating METADATA...
INFO: Updating cache of DataFrames...
INFO: Updating cache of DataFrames...
INFO: Updating Combinatorics master...
INFO: Computing changes...
INFO: No packages to install, update or remove

julia> Pkg.status()
7 required packages:
 - Atom                          0.5.8
 - Combinatorics                 0.3.2+             master

julia> Pkg.free("Combinatorics")
INFO: Freeing Combinatorics
INFO: No packages to install, update or remove

julia> Pkg.update()
INFO: Updating METADATA...
INFO: Updating cache of DataFrames...
INFO: Updating cache of DataFrames...
INFO: Computing changes...
INFO: No packages to install, update or remove

julia> Pkg.status()
7 required packages:
 - Atom                          0.5.8
 - Combinatorics                 0.3.2

julia> fibonacci(4)
ERROR: UndefVarError: fibonacci not defined

help?> fibonacci
search:

Couldn't find fibonacci
Perhaps you meant finally
  No documentation found.

  Binding fibonacci does not exist.

julia> combinations( [1,2] )
ERROR: combinations([1,2],) has been moved to the package Combinatorics.jl.
Run Pkg.add("Combinatorics") to install Combinatorics on Julia v0.5-
 in combinations(::Array{Int64,1}, ::Vararg{Array{Int64,1},N}) at ./deprecated.jl:200

cc @ViralBShah @tkelman

Hi,

I forgot to check whether anyone had implemented integer partitions in Julia and so implemented my own using an adaptation of http://jeromekelleher.net/generating-integer-partitions.html. For me, it's a lot quicker than your implementation here -

I haven't yet wrapped my head around iterators, and I needed all the partitions, so I stripped all that functionality out.

import Combinatorics
function partitions(n::Integer)
    a = zeros(Integer,n+1)
    k = 1
    y = n - 1
    ans = []
    while k != 0
        x = a[k] + 1
        k -= 1
        while 2x ≤ y
            a[k+1] = x
            y -= x
            k += 1
        end
        l = k + 1
        while x ≤ y
            a[k+1] = x
            a[l+1] = y
            push!(ans,a[1:k+2])
            x += 1
            y -= 1
        end
        a[k+1] = x + y
        y += x - 1
        push!(ans,a[1:k+1])
    end
    return ans
end

@time a = partitions(50);
0.358846 seconds (204.25 k allocations: 41.444 MiB, 3.88% gc time)

@time b = Combinatorics.integer_partitions(50);
5.859395 seconds (54.64 M allocations: 2.037 GiB, 18.58% gc time)

If I tidy up the code and make it into an iterator, would you be interested in a pull request?

The following error may be averted, or such functionality made possible with an additional method:

An example of how ‼︎ can be extended to the signed integers is found on Wikipedia at Ellipse § Circumference:

where $n‼︎$ is the double factorial (extended to negative odd integers 
by the recurrence relation $(2n-1)‼︎ = (2n+1)‼︎ / (2n+1)$, for $n ≤ 0$).

Would this be a useful addition to the library? Alternatively, if there are multiple distinct analytical continuations of ‼︎ for the negative integers, could I have a lead for how to implement it in Julia? Would this issue be a better fit for the SpecialFunctions library?

I am not sure why this error is occurring, I tried removing the cache folders in ~/.julia/.cache for Combinatorics and Iterators, but the error persists:

julia> using Combinatorics
INFO: Recompiling stale cache file /home/juliohm/.julia/lib/v0.6/Combinatorics.ji for module Combinatorics.
WARNING: The call to compilecache failed to create a usable precompiled cache file for module Combinatorics. Got:
WARNING: Module Iterators uuid did not match cache file.
ERROR: LoadError: Declaring __precompile__(true) is only allowed in module files being imported.
Stacktrace:
 [1] __precompile__(::Bool) at ./loading.jl:335
 [2] include_from_node1(::String) at ./loading.jl:569
 [3] eval(::Module, ::Any) at ./boot.jl:235
 [4] _require(::Symbol) at ./loading.jl:483
 [5] require(::Symbol) at ./loading.jl:398
while loading /home/juliohm/.julia/v0.6/Combinatorics/src/Combinatorics.jl, in expression starting on line 1

I was looking for a Julia implementation of this known combinatorics problem: Stars and bars

I have some struggle to use multiset_combinations and multiset_permutations and I didn't find any good documentation on it.

I wanted to compute/enumerate a multiset number using this method. However, It seems that multiset_combinations is performing a combination on multisets, which is something very different. I'm still new to Julia so I might be wrong.

Also, If you can point me to a workaround for this problem, I'll be glad to hear it!

Hi there!

For one of my projects I wrote a small implementation of Heap's algorithm, which iterates through all permutations of an array by shuffling its elements in-place. It does so in a way that minimizes the number of moves.

I think this would deserve a place in Combinatorics.jl, but I can't figure out how to provide a useful generic implementation. Enumerating permutations in-place is only good if you do something at each step, so I'm not sure a standard iterator is the right choice. Right now, I'm leaning towards accepting a function as argument, which would be applied after each move. What do you think?

Please take a look at the functionality in QuantEcon.jl. We are trying to make the package thinner and want to find a good place to port out code. A lot of the implementations could be hosted here.

Currently

julia> partitions(0)|>collect
1-element Array{Any,1}:
 #undef

This is unexpected because the partition of the empty set is the empty set so I would expect

patitions(0)|>collect == [[]]

This results in unexpected behviour here:

julia> [length(b) for b in partitions(1)]
1-element Array{Int64,1}:
 1

julia> [length(b) for b in partitions(0)]
1-element Array{Int64,1}:
 4492284592

# I expect this
julia> [length(b) for b in [[]]]
1-element Array{Int64,1}:
 0

It looks like there has been some change to how produce() works in Julia now, resulting in a logic error in the enumeration of noncrossing partitions. As a result, ncpart(4) hangs.

Hi, execellent library, just what I needed. I improved your Bellnum code. Same algorithm but much faster implementation. Also requires far less memory.

function bellnum(n::Integer)
if n < 0
throw(DomainError())
end
list = Array(BigInt, n)
list[1] = 1
for i = 2:n
list[i] = list[1]
for j = 1:i - 1
list[i - j] += list[i - j + 1]
end
end
return list[1]
end

The value of the hyperfactorial function for both 0 and of 1 is 1. Should be easy to add these as special cases.

julia> hyperfactorial(0)
ERROR: ArgumentError: reducing over an empty collection is not allowed

julia> hyperfactorial(1)
ERROR: ArgumentError: reducing over an empty collection is not allowed

This call should not throw an error:

julia> nthperm(1:5,1)
ERROR: indexing not defined for UnitRange{Int64}
Stacktrace:
 [1] setindex! at ./abstractarray.jl:967 [inlined]
 [2] nthperm!(::UnitRange{Int64}, ::Int64) at /Users/solver/.julia/v0.6/Combinatorics/src/permutations.jl:151
 [3] nthperm(::UnitRange{Int64}, ::Int64) at /Users/solver/.julia/v0.6/Combinatorics/src/permutations.jl:157