# Julia: Unique n-item sets with replacement

Given a vector `v = [1,..,n]`

, I am trying to compute all unique sets of n elements with replacements in julia.

Since I want to do this for large n values, I am looking for an efficient solution, perhaps using iterators.

For example, consider `v = [1, 2, 3]`

: this should result 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]`

. By unique, I mean that if it `[1,1,2]`

is a solution, any permutation of `[1,2,1], [2,1,1]`

it is not.

My current solution is function based `partitions`

but does not allow me to restrict the computation on 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
```

source to share

Here is the 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 a better way to code this, but that should be enough. Note that the result is generated through repeated `push!`

s, so it easily turns into an iterator if needed.

source to share

And in the form of an iterator:

```
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 question.

By the way, the name ImageTypeIterator is an attempt to characterize the collection as different types of preimage sizes when looking at the function f: [1: n] β [1: n]. But there may be a different interpretation. Other name suggestions are welcome in the comments.

Faster? / Clearer? the implementation can 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 unnecessary cutting. The logic takes a subset of 2n-1 and treats non-whitespaces as duplicate values ββand whitespaces as a trigger to move to the next value.

source to share

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 it is equivalent to the methods of the other answers.

And in a 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
```

source to share

As of julia v0.5.0 it `combinatorics.jl`

has a method `with_replacement_combinations`

.

```
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]
```

source to share