Julia: Unique sets of n elements with replacement

Question

Given a vector v = [1,..,n], I try to compute all unique sets of n elements with replacements in julia.

Since I want to do this for larger values of n, I'm looking for an efficient solution, possibly using iterators.

For example, let's consider v = [1, 2, 3]: This should results in [1,1,1], [1,1,2], [1,1,3], [1,2,2], [1,2,3], [1,3,3], [2,2,2], [2,2,3], [2,3,3], [3,3,3]. With unique, I mean that if [1,1,2] is a solution, any of its permutations [1,2,1], [2,1,1] is not.

My current solution is based on the partitions function, but does not allow me to restrict the computation on the elements [1,..,n]

for i in n:n^2
  for j in partitions(i, n)
    ## ignore sets which exceed the range [1,n]
    if maximum(j) <= n
      ## accept as solution
    end
  end
end

Answer 1

I guess, it doesn't get shorter than one-line (using Iterators).

using IterTools
import Combinatorics.combinations
n=3
collect(imap(c -> Int[c[k]-k+1 for k=1:length(c)],combinations(1:(2n-1),n)))

Answer 2

I believe you're looking for the product function from the Iterators package. In your case product(v,v,v) should do what's required.

Answer 3

In julia v0.5.0, combinatorics.jl has a with_replacement_combinations method.

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

Answer 4

Here is a function to calculate the required collection:

function calcset(n=3)
    res = []
    for c in combinations([1:(2n-1)],n-1)
        c3 = [c,2n].-[0,c]
        push!(res,vcat([fill(i,c3[n-i+1]-1) for i=1:n]...))
    end
    return res
end
calcset(3)

There is probably some better way to code this, but this should be enough. Notice the result is generated through repeated push!s, so this is easily turned into an iterator, if necessary.

Answer 5

And in iterator form:

import Base: start, next, done, eltype, length
type ImageTypeIterator
    inneritr::Base.Combinations{Array{Int64,1}}
    n::Int
end
imagetype(n::Int) = ImageTypeIterator(combinations([1:(2n-1)],n-1),n)
eltype(itr::ImageTypeIterator) = Array{Int64,1}
start(itr::ImageTypeIterator) = start(itr.inneritr)
function next(itr::ImageTypeIterator,s)
    (c,s) = next(itr.inneritr,s)
    c3 = [c,2*itr.n].-[0,c]
    (vcat([fill(i,c3[itr.n-i+1]-1) for i=1:itr.n]...),s)
end
done(itr::ImageTypeIterator,s) = done(itr.inneritr,s)
length(itr::ImageTypeIterator) = length(itr.inneritr)
# test with [1,2,3]
for t in imagetype(3) println(t) ; end

The test at the end should print the collection set in the question.

BTW the name ImageTypeIterator is an attempt to characterize the collection as the distinct types of sizes of preimages when looking at a function f : [1:n] -> [1:n]. But a different interpretation might be appropriate. Other names suggestion welcome in comments.

A faster?/clearer? implementation could use:

imagetype(n::Int) = ImageTypeIterator(combinations([1:(2n-1)],n),n)
function next(itr::ImageTypeIterator,s)
    (c,s) = next(itr.inneritr,s)
    v = Array(Int,itr.n)
    j = 1 ; p = 1
    for k=1:itr.n
        while !(j in c) j += 1 ; p += 1 ; end
        v[k] = p
        j += 1
    end
    (v,s)
end

Its the same logic as above, but without too much slicing. The logic takes a subset of 2n-1 and views non-gaps as repeated values and gaps as a trigger to advance to next value.

Answer 6

OK, a simpler version using Iterators.jl:

using Iterators
function ff(c)
    v = Array(Int,length(c))
    j = 1 ; p = 1
    for k=1:length(c)
        while !(j in c) j += 1 ; p += 1 ; end
        v[k] = p
        j += 1
    end
    v
end
# test
n = 3
for t in imap(ff,combinations([1:(2n-1)],n)) println(t) ; end

This is perhaps the simplest version, although equivalent in methods to the other answers.

And in the spirit of brevity:

using Iterators
ff(c) = begin 
    j=1;p=1; [(while !(j in c) j+=1;p+=1 ; end ; j+=1 ; p) for k=1:length(c)] 
end
n = 3 # test
for t in imap(ff,combinations([1:(2n-1)],n)) println(t) ; end