Tasks and collect

New to Julia
1

I decided to write an iterator to give me all permutations of distinct elements (yes I know that there is nthperm in the Combinatorics.jl package).
Generators (Tasks) seem to be natural choice, so here is the code:

# Steinhaus–Johnson–Trotter algorithm
function all_permutations(n::Int)
    elts = collect(1:n)
    direction = -1*ones(Int,n)
    direction[1] = 0
    chosen = n
    search = false
    
    function _it()
        produce(elts)
        for _ in 1:factorial(n)-1
            greater_chosen = find(x->x>elts[chosen], elts)
            direction[[i for i in greater_chosen if i < chosen]] .= 1
            direction[[i for i in greater_chosen if i > chosen]] .= -1

            d = direction[chosen]
            for arr in [elts, direction]
                arr[chosen], arr[chosen+d] = arr[chosen+d], arr[chosen]
            end

            #changing directions
            if chosen+d == 1 || chosen+d == n || elts[chosen+2d] > elts[chosen+d]
                direction[chosen+d] = 0
                search = true
            end

            if search == true
                max = 0
                chosen = 0
                for i in 1:n
                    if elts[i] > max && direction[i] ≠ 0
                        max = elts[i]
                        chosen = i
                    end
                end
            else
                chosen += d
            end
            produce(elts)
        end
    end
    
    return Task(_it)
end

Code in action:

for i in all_permutations(3)
    print(i)
end
[1,2,3][1,3,2][3,1,2][3,2,1][2,3,1][2,1,3]

This seems a trivial question, but why does collect(all_permutations(3)) returns 6-element array of identical element ([2,1,3])? (a similar application of collect(fibtask(10), as described Slender Means, works as supposed (array of 10 consecutive Fibonacci numbers).

2

You are returning the same array elts at every iteration, and modifying that same array inside the generator. Collecting the generator just results in the exact same array object 6 times. You can check this with:

julia> y = collect(all_permutations(3));

julia> y[1] === y[2]
true

where === checks if two variables point to the exact same object.

You can fix this by copying elts before you modify it or by doing produce(copy(elts)).

1 Like
3

Silly of me :wink: thanks!