-
Notifications
You must be signed in to change notification settings - Fork 29
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add product/permutations/combinations from Python itertools #138
Comments
I'm currently working on the products feature and I have a rough implementation that produces the correct output for the example For example, the code in How might be a good way to reduce code duplication here? I was thinking of extracting common functionality to a shared base class (similar to how |
Hi @isaacy2012,
Thanks a lot for working on this.
Yes, I think moving as much as possible up to a shared base class sounds like a good approach :)
Tristan |
Hi Tristan, Thanks for the feedback, I've moved the majority of the code shared between The code sharing between However, because
See main...isaacy2012:flux:feat/products
See main...isaacy2012:flux:feat/products-default-read-traits I don't like 1. because of the repeated
What are your thoughts on those approaches, or what might be a better way of expressing the orthogonal functionality of Many thanks, |
We already have
This seems like a nice way of doing it 👍
(FYI, I've been intending to rename But yeah, I can see the difficulty: we have four adaptor classes that do fairly similar things and we'd like to make sure we reuse code sensibly between the implementations. Of the two approaches you show, I think I'd lean towards the second one -- like you, I'm not too keen on the using directives. But I wonder if we could simplify the inheritance hierarchy a little by getting rid of the sequence_traits<cartesian_product_adaptor<...>>
: cartesian_read_traits<...> // "mixin" to add read_at(), read_at_unchecked() returning a tuple
: cartesian_traits_base<...> // provides inc(), is_last() etc etc
sequence_traits<cartesian_product_map_adaptor<...>>
: cartesian_map_traits<...> // "mixin" to add read_at() which invokes a function
cartesian_traits_base<...> // provides inc(), is_last() etc
sequence_traits<cartesian_power_adaptor<...>>
: cartesian_read_traits<...>
: cartesian_traits_base<...>
sequence_traits<cartesian_power_map_adaptor<...>>
: cartesian_map_traits<...>
: cartesian_traits_base<...> This might involve a small amount of code duplication (e.g the But I have to stress that I haven't actually tried it so I might be completely wrong...! Tristan |
Something else that has just occurred to me: for the "power" versions, the cursor type could be |
EDIT: Never mind, I came up with a better way of doing it -- see below |
Hi again @isaacy2012, sorry for bombarding you with messages! I've been thinking about this some more and I think I have a cleaner approach. Rather than using different base classes to encode the different policies -- product/power and map/tuple -- we can instead use just a single traits class that contains everything, and uses a pair of enums to select which code paths to use. The various adaptor classes (four of them) then specify which policies they want for their sequence_traits. I've coded up a proof of concept here: https://flux.godbolt.org/z/8jexzcreb |
Hi @tcbrindle
Yep, I think that's much better than the repeated tuple, though I've kept the repeated tuple type for the Regarding the switching between product/power and map/tuple, I think I actually preferred your mixin idea rather than the Thanks! |
No, the element type (the thing returned by
Yeah, from a pure design perspective bundling everything into one big class that contains every code path is certainly not the recommended way! But practically speaking I think it would probably end up being easier to understand and maintain in this case than using several different base classes with CRTP. I could be wrong though :)
Yeah, the idea was to use a requires clause, e.g. template <typename Self>
static constexpr auto move_at(Self& self, cursor_t<Self> const& cur) -> decltype(auto)
requires (ReadKind = read_kind::tuple)
{
return do_read(flux::move_at, self, cur);
} We could actually do this for all the functions -- e.g. provide two versions of |
Hi @tcbrindle
I see, thanks for the insight, yeah I think it is definitely easier to understand.
Great, I've done this, the only snag was that neither main...isaacy2012:flux:feat/cartesian-product-and-with I was also wondering for I probably won't get around to implementing |
So I think that actually we can get away with not defining a
I'm quite happy for you to do the rename of
We actually already use this concept in flux/include/flux/op/adjacent.hpp Lines 179 to 190 in f31a1c8
You could rename this to
Yeah, let's not worry about Thanks! |
Yep, I've got this to work :)
I've kept
Which means that the
It's a small change but I don't like having the |
I moved it to |
There's |
We currently have
cartestian_product(seq1, seq2, ...)
which takes a pack of N sequences and yields N-tuples of all the possible combinations of elements from those sequences. This is equivalent to a set of N nestedfor
loops, and to one form of the Python itertoolsproduct
operation.It's pretty common however to want to use the same sequence repeatedly with
cartesian_product
. Itertools provides a second form ofproduct
for this, using arepeat
argument. It would be good if we provided an equivalent too.We'd need it to have a different name, and we'd probably want to take
N
as a template parameter to avoid having to allocate. So we could have something likeproducts<3>(seq)
, which would be equivalent tocartestian_product(seq, seq, seq)
except that we wouldn't have to store multiple references to/copies of the sequence. The size of the resulting sequence would besize(seq)^N
.Itertools also provides the
permutations
operation, which would also be nice to have. This yields (in lexicographical order) all the length-N permutations of the elements of the input sequence. This is a strict subset of the elements ofproducts<N>
, skipping those tuples which contain repeated elements from the underlying sequence. IfS
is the size of the original sequence, the size ofpermutations<N>
isS!/(S - N)!
.Finally, Itertools has two slightly different
combinations
operations. The first gives a strict subset ofpermutations
, skipping tuples in which the elements are not in "sorted" order (according to their position in the initial sequence), and has sizeS!/N!(S-N)!
The second, the slightly oddly named (to me)
combinations.with_replacement
. This does the same ascombinations
except that it additionally allows individual elements to be repeated -- meaning the resulting elements are a subset ofproduct<N>
, but notpermutations<N>
. The number of elements is(S+N-1)!/N!(S-1)!
.To make this a bit more concrete, imagine an input sequence
seq = [a, b, c, d]
. Then the various operations give:products<3>(seq)
: (4^3 = 64 elements)permutations<3>(seq)
: (4!/(4-3!) = 24 elements)combinations<3>(seq)
: (4!/3!*(4-3)! = 24/6 = 4 elements)combinations_with_replacement<3>(seq)
: ((4+3-1)!/3!(4-1)! = 6!/3!3! = 720/36 = 20 elements)The text was updated successfully, but these errors were encountered: