# Efficiently iterate over partially permuted array

**URL:** <https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982>\
**Category:** General Usage\
**Created:** [May 22, 2020, 5:37pm UTC](https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982 "2020-05-22T17:37:01Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [May 22, 2020, 5:37pm UTC](https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982/1 "2020-05-22T17:37:01Z")

</div>

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:

```julia
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!

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [May 26, 2020, 7:40pm UTC](https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982/2 "2020-05-26T19:40:19Z")

</div>

One and - I promise - only bump for this!

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [May 26, 2020, 8:09pm UTC](https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982/3 "2020-05-26T20:09:45Z")

</div>

Is this meant to run?

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

```

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [May 26, 2020, 8:25pm UTC](https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982/4 "2020-05-26T20:25:21Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [May 26, 2020, 8:53pm UTC](https://discourse.julialang.org/t/efficiently-iterate-over-partially-permuted-array/39982/5 "2020-05-26T20:53:01Z")

</div>

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.