CODEWITHSUNDEEP
typesjulia
Martin Scheffel
Martin Scheffel

Reputation: 1

Recursion in Julia gives answer in Array of Array form and Any type instead of Matrix form and Int64 type

I am new to Julia and I would like to understand the following problem.

I try to write a program that computes all permutations of length k with elements drawn from the vector 1:n with replacement, such that the sum of each permutation is equal to a target number n.

While the code basically succeeds, I still run into the problem that my result is an Array of Array in Anny type instead of a Matrix in Int64 type. I understand that I can solve the problem at the end with some transfomations, but I would like to understand why I cannot enforce this output immediately.

the code is

    function find_permutations_with_replacement(arr::Array{Int64,1}, n::Int64, k::Int64;     current_sum::Int64=0, path=[], res=[])
    # Check if we have the correct number of elements and if their sum is exactly n
    if length(path) == k
        if current_sum == n
            push!(res,copy(path))
        end
        return
    end

    # Early exit if the current sum already exceeds the target sum
    if current_sum > n
        return
    end

    # Recursively explore each element in the array, allowing for repetition
    for i in 1:length(arr)
        push!(path, arr[i])
        find_permutations_with_replacement(arr, n, k; current_sum=arr[i] + current_sum, path=path, res=res)
        pop!(path)
    end

    return res    
    end

    # model parameters
    d = 3;       # dimension
    maxl = 4;    # maximimum level

    levs = collect(1:maxl);
    finres=[];
    for trgt in d:maxl+d-1
        permutations = find_permutations_with_replacement(levs, trgt, d);    
        push!(finres,permutations);
    end

Upvotes: 0

Views: 45

Answers (1)

Bill
Bill

Reputation: 6086

When specifying array variables in Julia, it is best to be as specific as possible about its type at the time the array is CREATED. However, when specifying the name of an array as a function argument, it is better to leave out the type, since the compiler can decide that from the passed argument's type.

In addition, since you ultimately, after recursion, plan to use a return value from your function, it's best to always return a value of some kind, which you don't in your earliest return statements in the function. It's cleaner to just return once at the end, and use if/else for code flow until then.

What you return from the function is a vector of vectors. This is the correct design for your use, because you are adding to the vector during the function calls. If you had a Matrix of Int64 with the solutions as rows, you would have to re-allocate the matrix each time you add a row, which wastes allocations and memory.

You can stack the permutations later, though I would keep the various sum-permutation-classes separate in a vector of matrices, as below.

function find_permutations_with_replacement(arr, n, k; current_sum = 0, path = Int64[], res = Vector{Int64}[])
    # Check if we have the correct number of elements and if their sum is exactly n
    if length(path) == k
        if current_sum == n
            push!(res, copy(path))
        end
    elseif current_sum <= n
        # Recursively explore each element in the array, allowing for repetition
        for i in arr
            push!(path, i)
            find_permutations_with_replacement(arr, n, k; current_sum = arr[i] + current_sum, path = path, res = res)
            pop!(path)
        end
    end
    return res
end


# model parameters
function test_find_perms(dimension = 3, maximum_level = 4)::Vector{Matrix{Int64}}
    levs = collect(1:maximum_level)
    finres = Matrix{Int64}[]
    for trgt in dimension : dimension + maximum_level - 1
        permutations = find_permutations_with_replacement(levs, trgt, dimension)
        stacked = stack(permutations, dims = 1)
        push!(finres, stacked)
    end
    return finres
end

println(test_find_perms())

Upvotes: 1

Related Questions