Efficiently iterate over partially permuted array

General Usage
1

I need to iterate over all multi-set permutations of parts of an array, and get the value of a function which depends on the order of elements in the array. What’s the most efficient way to do this?

Only a subset of the array is permuted, however the results of the function depend on the value of every element in the array.

I’ve come up with:

using Combinatorics, Statistics

my_array = rand('a':'d', 40)

# Example function, my function is about as trivial in terms of runtime
my_func(x, y) = mean(cumsum(x .== y))

function get_all_results(arr)
    # Only permute part of the array, e.g. here all a's and c's in the array
    ps = multiset_permutations(arr[in(['a', 'c']).(arr)], sum(in(['a', 'c']).(arr)))

    result = zeros(length(ps))

    for (i, p) ∈ enumerate(ps)
        # Replace the a's and c's with the permuted a's and c's
        # This is the bit that feels suboptimal?
        arr[in(['a', 'c']).(arr)] = p
        result[i] = my_func(arr, 'c')
    end

    return result
end

But I wonder whether there’s a better way to “shuffle around” the elements in the existing array?

Furthermore, it seems to me that the way I’m doing it currently is not threadsafe/parallelizable, as different threads would try to shuffle the elements in my_array, so if there’s a way around this as well that’d be great!

2

One and - I promise - only bump for this!

3

Is this meant to run?

julia> get_all_results(my_array)
ERROR: UndefVarError: multiset_permutations not defined
4

Ah my apologies, made an MWE in a long running session… multiset_permutations is defined in Combinatorics, and I also used mean from Statistics, have edited the example above

5

ok! So first(ps) == filter(in(('a','c')), arr), and later p values are permutations of that. Which get copied into the original array before calling my_func(arr, 'c').

You could look at how Combinatorics.MultiSetPermutations works in the hope of doing whatever it does directly on the arr each time, instead of making p? If you want to thread this, you could make a copy of arr per thread?

You can also avoid working out the indices each time via is = findall(in(('a', 'c')), arr), but no idea if it matters much.

1 Like