--000000000000b3f0000568552557
Content-Type: text/plain; charset="UTF-8"

apply_inverse_permutation?

I'm also missing parallel and range-based specifications, since applying a
permutation of the elements is, with O(N) space and N CPUs, an O(1) task,
which means significant parallelism can be exploited.

G

On Mon, Mar 26, 2018 at 6:52 PM, Alexander Zaitsev <zamazan4ik@gmail.com>
wrote:

> Hello,
>
> I am working on proposal about adding two new functions to STL:
> 'apply_permutation' and 'apply_reverse_permutation'. In attachments you can
> find this proposal (in PDF and HTML formats). Also you can find them on
> GitHub: https://github.com/ZaMaZaN4iK/ConfsANDProps/tree/master/Proposals
>
> *What is it?*
>
> Shortly, 'apply_permutation' and 'apply_reverse_permutation' are functions
> for reordering elements in a range in some defined order.
>
> *Description*
>
> The routine `apply_permutation` takes a item sequence and a order
> sequence. It reshuffles item sequence according to order sequence. Every
> value in order sequence means where the item comes from. Order sequence
> needs to be exactly a permutation of the sequence [0, 1, ... , N], where N
> is the biggest index in the item sequence (zero-indexed).
>
> The routine `apply_reverse_permutation` takes a item sequence and a order
> sequence. It will reshuffle item sequence according to order sequence.
> Every value in order sequence means where the item goes to. Order sequence
> needs to be exactly a permutation of the sequence [0, 1, ... , N], where N
> is the biggest index in the item sequence (zero-indexed).
>
> *Brief description*
>
> Brief exaplantion is available on Microsoft Developer "Old new thing"
> blog: 1
> <https://blogs.msdn.microsoft.com/oldnewthing/20170102-00/?p=95095>, 2
> <https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=95105>, 3
> <https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115>, 4
> <https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=95145>, 5
> <https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=95155>, 6
> <https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=95165>
>
>
>
> Implementation is available in Boost.Algorithm library:
> https://github.com/boostorg/algorithm/blob/develop/
> include/boost/algorithm/apply_permutation.hpp
> So you can play with it on wandbox.org
>
> <http://wandbox.org/>
>
> <http://wandbox.org/>
> Open questions: Naming. I think apply_reverese_permutation isn't nice
> name. Can you suggest anything better?
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit https://groups.google.com/a/
> isocpp.org/d/msgid/std-proposals/9d30f89e-c92f-4c38-
> 9943-b96b199d1ddd%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/9d30f89e-c92f-4c38-9943-b96b199d1ddd%40isocpp.org?utm_medium=email&utm_source=footer>
> .
>

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAANG%3DkVAi8ow7PBdW68OXK%3DB7RxYyvGZeNOMjJ-cFC9d3N4%2BvA%40mail.gmail.com.

--000000000000b3f0000568552557
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">apply_inverse_permutation?<div><br></div><div>I&#39;m also=
 missing parallel and range-based specifications, since applying a permutat=
ion of the elements is, with O(N) space and N CPUs, an O(1) task, which mea=
ns significant parallelism can be exploited.</div><div><br></div><div>G</di=
v></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Mon, M=
ar 26, 2018 at 6:52 PM, Alexander Zaitsev <span dir=3D"ltr">&lt;<a href=3D"=
mailto:zamazan4ik@gmail.com" target=3D"_blank">zamazan4ik@gmail.com</a>&gt;=
</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .=
8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hello,<di=
v><div style=3D"overflow:auto"><div style=3D"max-height:10000px"><div dir=
=3D"ltr"><div><br></div><div>I am working on proposal about adding two new =
functions to STL: &#39;apply_permutation&#39; and &#39;apply_reverse_permut=
ation&#39;. In attachments you can find this proposal (in PDF and HTML form=
ats). Also you can find them on GitHub:=C2=A0<a href=3D"https://github.com/=
ZaMaZaN4iK/ConfsANDProps/tree/master/Proposals" rel=3D"nofollow" target=3D"=
_blank">https://github.com/ZaM<wbr>aZaN4iK/ConfsANDProps/tree/mas<wbr>ter/P=
roposals</a></div><div><br></div><div><b>What is it?</b></div><div><b><br><=
/b></div><div>Shortly, &#39;apply_permutation&#39; and &#39;apply_reverse_p=
ermutation&#39; are functions for reordering elements in a range in some de=
fined order.=C2=A0</div><div><br></div><div><b>Description</b></div><div><b=
r></div><div><div>The routine `apply_permutation` takes a item sequence and=
 a order sequence. It reshuffles item sequence according to order sequence.=
 Every value in order sequence means where the item comes from. Order seque=
nce needs to be exactly a permutation of the sequence [0, 1, ... , N], wher=
e N is the biggest index in the item sequence (zero-indexed).</div><div><br=
></div><div>The routine `apply_reverse_permutation` takes a item sequence a=
nd a order sequence. It will reshuffle item sequence according to order seq=
uence. Every value in order sequence means where the item goes to. Order se=
quence needs to be exactly a permutation of the sequence [0, 1, ... , N], w=
here N is the biggest index in the item sequence (zero-indexed).</div></div=
><div><br></div><div><b>Brief description</b></div><div><b><br></b></div><d=
iv>Brief exaplantion is available on Microsoft Developer &quot;Old new thin=
g&quot; blog: <a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170=
102-00/?p=3D95095" target=3D"_blank">1</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=3D95=
105" target=3D"_blank">2</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=3D95=
115" target=3D"_blank">3</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=3D95=
145" target=3D"_blank">4</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=3D95=
155" target=3D"_blank">5</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=3D95=
165" target=3D"_blank">6</a></div>
=09
=09
=09


<div><b><br></b></div><div><b><br></b></div><div><br></div><div>Implementat=
ion is available in Boost.Algorithm library: <font color=3D"#1155cc"><a hre=
f=3D"https://github.com/boostorg/algorithm/blob/develop/include/boost/algor=
ithm/apply_permutation.hpp" target=3D"_blank">https://github.com/boostorg/<=
wbr>algorithm/blob/develop/<wbr>include/boost/algorithm/apply_<wbr>permutat=
ion.hpp</a></font></div><div>So you can play with it on=C2=A0<a href=3D"htt=
p://wandbox.org/" rel=3D"nofollow" target=3D"_blank">wandbox.org<br></a></d=
iv><div><a href=3D"http://wandbox.org/" rel=3D"nofollow" target=3D"_blank">=
<br></a></div><div><a href=3D"http://wandbox.org/" rel=3D"nofollow" target=
=3D"_blank"><br></a></div><div>Open questions: Naming. I think apply_revere=
se_permutation isn&#39;t nice name. Can you suggest anything better?</div><=
/div></div></div></div></div><span class=3D"HOEnZb"><font color=3D"#888888"=
>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@<wbr>isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/9d30f89e-c92f-4c38-9943-b96b199d1ddd%=
40isocpp.org?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/<wbr>isocpp.org/d/msgid/std-<wbr>proposals/9d30=
f89e-c92f-4c38-<wbr>9943-b96b199d1ddd%40isocpp.org</a><wbr>.<br>
</font></span></blockquote></div><br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAANG%3DkVAi8ow7PBdW68OXK%3DB7RxYyvGZ=
eNOMjJ-cFC9d3N4%2BvA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfoote=
r">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAANG%3DkVA=
i8ow7PBdW68OXK%3DB7RxYyvGZeNOMjJ-cFC9d3N4%2BvA%40mail.gmail.com</a>.<br />

--000000000000b3f0000568552557--

.

--f4f5e808e164a0535b056858f766
Content-Type: text/plain; charset="UTF-8"

On 26 March 2018 at 10:52, Alexander Zaitsev <zamazan4ik@gmail.com> wrote:

> Hello,
>
> I am working on proposal about adding two new functions to STL:
> 'apply_permutation' and 'apply_reverse_permutation'. In attachments you can
> find this proposal (in PDF and HTML formats). Also you can find them on
> GitHub: https://github.com/ZaMaZaN4iK/ConfsANDProps/tree/master/Proposals
>
> *What is it?*
>
> Shortly, 'apply_permutation' and 'apply_reverse_permutation' are functions
> for reordering elements in a range in some defined order.
>
> *Description*
>
> The routine `apply_permutation` takes a item sequence and a order
> sequence. It reshuffles item sequence according to order sequence. Every
> value in order sequence means where the item comes from. Order sequence
> needs to be exactly a permutation of the sequence [0, 1, ... , N], where N
> is the biggest index in the item sequence (zero-indexed).
>
> The routine `apply_reverse_permutation` takes a item sequence and a order
> sequence. It will reshuffle item sequence according to order sequence.
> Every value in order sequence means where the item goes to. Order sequence
> needs to be exactly a permutation of the sequence [0, 1, ... , N], where N
> is the biggest index in the item sequence (zero-indexed).
>
> *Brief description*
>
> Brief exaplantion is available on Microsoft Developer "Old new thing"
> blog: 1
> <https://blogs.msdn.microsoft.com/oldnewthing/20170102-00/?p=95095>, 2
> <https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=95105>, 3
> <https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115>, 4
> <https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=95145>, 5
> <https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=95155>, 6
> <https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=95165>
>
>
>
> Implementation is available in Boost.Algorithm library:
> https://github.com/boostorg/algorithm/blob/develop/
> include/boost/algorithm/apply_permutation.hpp
> So you can play with it on wandbox.org
>
> <http://wandbox.org/>
>
> <http://wandbox.org/>
> Open questions: Naming. I think apply_reverese_permutation isn't nice
> name. Can you suggest anything better?
>

permute and unpermute?

That said, I find it very surprising that this operation mutates the
permutation as well as the sequence being permuted; that seems very likely
to lead to bugs. It seems like it'd be easy to provide permute_copy /
unpermute_copy operations without this limitation (although if you don't do
the permutation in-place, this becomes sufficiently simple that I'm not
sure it warrants inclusion in the standard library).

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmXRRssuztELOmn53AHmH5zRMoW4F1iMXjkT7vXDLjBLA%40mail.gmail.com.

--f4f5e808e164a0535b056858f766
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On 2=
6 March 2018 at 10:52, Alexander Zaitsev <span dir=3D"ltr">&lt;<a href=3D"m=
ailto:zamazan4ik@gmail.com" target=3D"_blank">zamazan4ik@gmail.com</a>&gt;<=
/span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hello,<div=
><div style=3D"overflow:auto"><div style=3D"max-height:10000px"><div dir=3D=
"ltr"><div><br></div><div>I am working on proposal about adding two new fun=
ctions to STL: &#39;apply_permutation&#39; and &#39;apply_reverse_permutati=
on&#39;. In attachments you can find this proposal (in PDF and HTML formats=
). Also you can find them on GitHub:=C2=A0<a href=3D"https://github.com/ZaM=
aZaN4iK/ConfsANDProps/tree/master/Proposals" rel=3D"nofollow" target=3D"_bl=
ank">https://github.com/ZaM<wbr>aZaN4iK/ConfsANDProps/tree/mas<wbr>ter/Prop=
osals</a></div><div><br></div><div><b>What is it?</b></div><div><b><br></b>=
</div><div>Shortly, &#39;apply_permutation&#39; and &#39;apply_reverse_perm=
utation&#39; are functions for reordering elements in a range in some defin=
ed order.=C2=A0</div><div><br></div><div><b>Description</b></div><div><br><=
/div><div><div>The routine `apply_permutation` takes a item sequence and a =
order sequence. It reshuffles item sequence according to order sequence. Ev=
ery value in order sequence means where the item comes from. Order sequence=
 needs to be exactly a permutation of the sequence [0, 1, ... , N], where N=
 is the biggest index in the item sequence (zero-indexed).</div><div><br></=
div><div>The routine `apply_reverse_permutation` takes a item sequence and =
a order sequence. It will reshuffle item sequence according to order sequen=
ce. Every value in order sequence means where the item goes to. Order seque=
nce needs to be exactly a permutation of the sequence [0, 1, ... , N], wher=
e N is the biggest index in the item sequence (zero-indexed).</div></div><d=
iv><br></div><div><b>Brief description</b></div><div><b><br></b></div><div>=
Brief exaplantion is available on Microsoft Developer &quot;Old new thing&q=
uot; blog: <a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170102=
-00/?p=3D95095" target=3D"_blank">1</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=3D95=
105" target=3D"_blank">2</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=3D95=
115" target=3D"_blank">3</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=3D95=
145" target=3D"_blank">4</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=3D95=
155" target=3D"_blank">5</a>,
<a href=3D"https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=3D95=
165" target=3D"_blank">6</a></div>
=09
=09
=09


<div><b><br></b></div><div><b><br></b></div><div><br></div><div>Implementat=
ion is available in Boost.Algorithm library: <font color=3D"#1155cc"><a hre=
f=3D"https://github.com/boostorg/algorithm/blob/develop/include/boost/algor=
ithm/apply_permutation.hpp" target=3D"_blank">https://github.com/boostorg/<=
wbr>algorithm/blob/develop/<wbr>include/boost/algorithm/apply_<wbr>permutat=
ion.hpp</a></font></div><div>So you can play with it on=C2=A0<a href=3D"htt=
p://wandbox.org/" rel=3D"nofollow" target=3D"_blank">wandbox.org<br></a></d=
iv><div><a href=3D"http://wandbox.org/" rel=3D"nofollow" target=3D"_blank">=
<br></a></div><div><a href=3D"http://wandbox.org/" rel=3D"nofollow" target=
=3D"_blank"><br></a></div><div>Open questions: Naming. I think apply_revere=
se_permutation isn&#39;t nice name. Can you suggest anything better?</div><=
/div></div></div></div></div></blockquote><div><br></div><div>permute and u=
npermute?</div><div><br></div><div>That said, I find it very surprising tha=
t this operation mutates the permutation as well as the sequence being perm=
uted; that seems very likely to lead to bugs. It seems like it&#39;d be eas=
y to provide permute_copy / unpermute_copy operations without this limitati=
on (although if you don&#39;t do the permutation in-place, this becomes suf=
ficiently simple that I&#39;m not sure it warrants inclusion in the standar=
d library).</div></div></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmXRRssuztELOmn53AHmH5zRMoW4F1i=
MXjkT7vXDLjBLA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmXRRssuztE=
LOmn53AHmH5zRMoW4F1iMXjkT7vXDLjBLA%40mail.gmail.com</a>.<br />

--f4f5e808e164a0535b056858f766--

.