CODEWITHSUNDEEP
juliacombinatorics
Arnfinn
Arnfinn

Reputation: 121

Re. partitions()

Why is

julia> collect(partitions(1,2))
0-element Array{Any,1}

returned instead of

2-element Array{Any,1}:
 [0,1]
 [1,0]

and do I really have to

x = collect(partitions(n,m));
y = Array(Int64,length(x),length(x[1]));
for i in 1:length(x)
    for j in 1:length(x[1])
        y[i,j] = x[i][j];
    end
end

to convert the result to a two-dimensional array?

Upvotes: 1

Views: 1019

Answers (4)

Arnfinn
Arnfinn

Reputation: 121

The MATLAB script from http://www.mathworks.com/matlabcentral/fileexchange/28340-nsumk actually behaves the way I need, and is what I though that partitions() would do from the description given. The Julia version is

# k - sum, n - number of non-negative integers
function nsumk(k,n)
  m = binomial(k+n-1,n-1);
  d1 = zeros(Int16,m,1);
  d2 = collect(combinations(collect((1:(k+n-1))),n-1));
  d2 = convert(Array{Int16,2},hcat(d2...)');
  d3 = ones(Int16,m,1)*(k+n);
  dividers = [d1 d2 d3];
  return diff(dividers,2)-1;
end

julia> nsumk(3,2)
4x2 Array{Int16,2}:
 0  3
 1  2
 2  1
 3  0

using daycaster's lovely hcat(x...) tidbit :) I still wish there would be a more compact way of doing this.

The the first mention of this approach seem to be https://au.mathworks.com/matlabcentral/newsreader/view_thread/52610, and as far as I can understand it is based on the "stars and bars" method https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Upvotes: 1

Reza Afzalan
Reza Afzalan

Reputation: 5756

one robust solution can be achieved using lexicographic premutations generation algorithm, originally By Donald Knuth plus classic partitions(n).
that is lexicographic premutations generator:

function lpremutations{T}(a::T)
  b=Vector{T}()
  sort!(a)
  n=length(a)
  while(true)
    push!(b,copy(a))    
    j=n-1
    while(a[j]>=a[j+1])
      j-=1
      j==0 && return(b)
    end
    l=n
    while(a[j]>=a[l])
      l-=1
    end
    tmp=a[l]
    a[l]=a[j]
    a[j]=tmp
    k=j+1
    l=n
    while(k<l)
      tmp=a[k]
      a[k]=a[l]
      a[l]=tmp
      k+=1
      l-=1
    end
  end
end

The above algorithm will generates all possible unique combinations of an array elements with repetition:

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

Then we will generate all integer arrays that sum to n using partitions(n) (forget the length of desired arrays m), and resize them to the lenght m using resize_!

function resize_!(x,m)
  [x;zeros(Int,m-length(x))]
end

And main function looks like:

function lpartitions(n,m)
  result=[]
  for i in partitions(n)
    append!(result,lpremutations(resize_!(i, m)))
  end
  result
end

Check it

julia> lpartitions(3,4)
20-element Array{Any,1}:
 [0,0,0,3]
 [0,0,3,0]
 [0,3,0,0]
 [3,0,0,0]
 [0,0,1,2]
 [0,0,2,1]
 [0,1,0,2]
 [0,1,2,0]
 [0,2,0,1]
 [0,2,1,0]
 [1,0,0,2]
 [1,0,2,0]
 [1,2,0,0]
 [2,0,0,1]
 [2,0,1,0]
 [2,1,0,0]
 [0,1,1,1]
 [1,0,1,1]
 [1,1,0,1]
 [1,1,1,0]

Upvotes: 2

Fengyang Wang
Fengyang Wang

Reputation: 12051

Here's another approach to your problem that I think is a little simpler, using the Combinatorics.jl library:

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

This allocates a bunch of memory, but I think your current approach does too. Maybe it would be useful to make a first-class version and add it to Combinatorics.jl.

Examples:

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]

The argument order is backwards from yours to match mathematical convention. If you prefer the other way, that can easily be changed.

Upvotes: 3

daycaster
daycaster

Reputation: 2707

From the wikipedia:

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers.

For array conversion, try:

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

or

julia> x = partitions(5,3)
Base.FixedPartitions(5,3)

then

julia> hcat(x...)
3x2 Array{Int64,2}:
 3  2
 1  2
 1  1

Upvotes: 3

Related Questions