✔ Critique my combinatorial function · helpdesk (published)

Stream: helpdesk (published)

Topic: ✔ Critique my combinatorial function

Peter Goodall (Nov 29 2021 at 02:40):

I wrote this function to give me all selections, with replacement, of size t, from a collection a.
Is there a more compact idiomatic way of writing this? I'd like it to be simple enough to be 'obviously correct'.
It seems to be working, but it makes me unhappy when I look at it. The collect/flattening is a horrible hack. I think I fell between collections and iterators.
Correct functions? Composition? Pipes?

using Combinatorics
using Base.Iterators: flatten
function permutationsWithOrder(a, t)
    c = with_replacement_combinations(a, t)
    c2 = map(permutations, c)
    c3 = (x -> collect.(x))(Set.(c2))
    return collect(Set(flatten(c3)))
end

julia> permutationsWithOrder([true,false], 3)
8-element Vector{Vector{Bool}}:
 [1, 1, 1]
 [0, 0, 0]
 [1, 1, 0]
 [0, 0, 1]
 [0, 1, 1]
 [1, 0, 0]
 [1, 0, 1]
 [0, 1, 0]

julia> permutationsWithOrder([true,false], 1)
2-element Vector{Vector{Bool}}:
 [1]
 [0]

Peter Goodall (Nov 29 2021 at 03:42):

take 99

using Combinatorics
using Base.Iterators: flatten
using Pipe: @pipe

function permutationsWithOrder(a, t)
    @pipe with_replacement_combinations(a, t) |>
          map(permutations, _) |>
          unique(_) |>
          flatten(_) |>
          unique(_) |>
          collect(_) # :-(
end

julia> permutationsWithOrder([true,false], 3)
8-element Vector{Vector{Bool}}:
 [1, 1, 1]
 [1, 1, 0]
 [1, 0, 1]
 [0, 1, 1]
 [1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]
 [0, 0, 0]

julia> permutationsWithOrder([true,false], 1)
2-element Vector{Vector{Bool}}:
 [1]
 [0]

Peter Goodall (Nov 29 2021 at 03:50):

:smile:
The llvm is huge - so I assume must be moving across module boundaries inefficiently.

julia> @code_lowered permutationsWithOrder([true,false], 1)
CodeInfo(
1 ─ %1 = Main.with_replacement_combinations(a, t)
│   %2 = Main.map(Main.permutations, %1)
│   %3 = Main.unique(%2)
│   %4 = Main.flatten(%3)
│   %5 = Main.unique(%4)
│   %6 = Main.collect(%5)
└──      return %6

Peter Goodall (Nov 29 2021 at 06:58):

in How to generate the permutation of a vector with elements selected @Tamas_Papp suggests:

all_perm(xs, n) = vec(map(collect, Iterators.product(ntuple(_ -> xs, n)...)))

I tried putting calls together by increments:

let
    xs = [true, false]
    n = 3
    @pipe ntuple(_ -> xs, n) |> Iterators.product(_...) |> map(collect, _) |> vec(_)
end

My interpretation:

copies = ntuple() is making n copies of xs
p = Iterators.product() is creating the products of the copies
d = map.collect is turning p into an iterable of Arrays
vec turns d into a column vector

I'm happy with that. also several orders of magnitude faster

Notification Bot (Nov 29 2021 at 07:15):

Peter Goodall has marked this topic as resolved.

Last updated: Dec 28 2024 at 04:38 UTC