220 37484 article Path: news.gmane.org!.POSTED!not-for-mail From: Richard Smith Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding 'apply_permutation' functions to the standard library Date: Mon, 26 Mar 2018 16:16:23 -0700 Lines: 158 Approved: news@gmane.org Message-ID: References: <9d30f89e-c92f-4c38-9943-b96b199d1ddd@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="f4f5e808e164a0535b056858f766" X-Trace: blaine.gmane.org 1522106089 32568 195.159.176.226 (26 Mar 2018 23:14:49 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 26 Mar 2018 23:14:49 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDVNBJG4YAIBBYP64XKQKGQEBN5TL5A@isocpp.org Tue Mar 27 01:14:45 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-wr0-f198.google.com ([209.85.128.198]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1f0bK6-0008MX-VQ for gclcip-std-proposals@m.gmane.org; Tue, 27 Mar 2018 01:14:43 +0200 Original-Received: by mail-wr0-f198.google.com with SMTP id v11sf4654976wri.13 for ; Mon, 26 Mar 2018 16:16:50 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1522106210; cv=pass; d=google.com; s=arc-20160816; b=NRGyO53o3F0eMwk05DZuV4HOB8cW6PpQlsbP49uUbgBOfJIJ+8rD38tbNho8kEpn9n aRzTnm870l6nFzWgK+wMPy6ZVmv6VhDepy0vOnzOcMYI5Y9XGWoPA54aNegRyZQqjUGm gf9crGXdpwQeGygjtsRyUa+cabJ0NtsMoUZa+g00sFOCD+yoao7f9bFfDDYyvxt1f2bN 6bmJCv8JAJWpHtca9kfNjQ00Wu8AJM39RqWLlozmwQ81rnik4+SYtui2B9mNbYkj5k8U o7voWTJC/Y7rtS/vBgXxU06qIxCEpNai4TxzxSM7IUa+WNoeL61kGiwoGz98ayXpihQk XGBQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:to:subject:message-id:date :from:references:in-reply-to:mime-version:arc-authentication-results :arc-message-signature:dkim-signature:arc-authentication-results; bh=UYzVNUr7X0Rwh0e3BLwSLNyloCn6LvcSN9sPXrqX21k=; b=iRvCfjEnkIuIOny/2xH7f45jMlhSzdeJ20rolH4uE+DiP5wRa6e6tdJop5uUzJTSCg nnNJvX/h9DMUixkfxaskwRZBnCMXrnp2roAwQvJV/2MP96NohDbKQqAOZeG4p8yjQovZ FhmVP52QUpfMxwNkOMViI9FM9La4zXNxXo87hux8wBTn2ZuTIuxu2uzGf6uPZU2DTxWd 27qX8zk/9Wft/I9oxyyVVWIfD2BdO5nHI3RZA4bjXO7e9cxVa/FyNTgEA3D58w+GczGn yFn0Qz9qPpF8l/6/rI8GC/AwChVCpvwqHpvv9+4gg5291FtAmxPHbsQj943okxEs7ixj aJFQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@metafoo.co.uk header.s=default header.b=lwmJWMHP; spf=neutral (google.com: 81.27.85.19 is neither permitted nor denied by best guess record for domain of richard@metafoo.co.uk) smtp.mailfrom=richard@metafoo.co.uk DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=UYzVNUr7X0Rwh0e3BLwSLNyloCn6LvcSN9sPXrqX21k=; b=hLq67/jHgJaKQnoab05Yh8OBaZ5yO08X+uCciYdlERlfA7xVVe4Sc9B7yaRovRQ09X 8soCIEqabkANYYkyAn6yit/xvkk/Zu+LD0sO+EMOl7s7KwNtsSA4YDY0TXnHlGNWoS4M xd5ud9NhPBp7AFuh9bGggrfNYkJMr0P6TTJxCxfiLDFB/NfilGLF7FqQvZTo44hxyhLk vF7UJdlRIBjmFkqL8Uxi5CrKXkjHRWcsLeWlDrpqqYeXrmoiqi1mFv4vx8ZCtUdX9He0 N7uVo3Oy96H0DrWRr5C3mMt3GBSQ6qwZdlJGkJH8SbYMrVi8GFaSEOaB5FHeqamP32gq Ke9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=UYzVNUr7X0Rwh0e3BLwSLNyloCn6LvcSN9sPXrqX21k=; b=mMcr+TxWpk+0T8wtaToG/2IU2QpCRFn3lig2+h0SsxH3C8XD1/fZlBdhl/jF65D7vs Qtde7JeKuO1uoex+cwEuDtaJ7e3huwP+NCNMA1J0z5MjG6R8ebL9OMYL7p/CHbFYF8WS KA084Gynj8he4Jrbtg4pXvv0l+eWenwFoAON/y/ioInG/okcG9F4TpELuLve+K8cVuUw IpjtaG+qmxSwqL+Tyg1BK8pJ/6P02nq4CrS81fflmJDU17ajgkPGdIGA/dci5WBx9fIF 7rJDiJU9uDLkYehJwecQf9JAqnyPXBKN3Pt4KjupeAklLUN1PyvD/APXQZUgFZT31GBY 9/Ww== X-Gm-Message-State: AElRT7Eq0/PwJ11b2mnYCszOL8oKE3kBsOzsImWWud5EYz7EqCd0/5rJ 2aykNQeOEZ4lxaqmdIyzoWFDwg== X-Google-Smtp-Source: AIpwx48xXpuqGP/n2yuM5TGx+2WwlMBiOKFtXRj7hO5//EiRQVoPIwlI1XV+ifW2BNr9BBMe88kqDg== X-Received: by 10.223.180.87 with SMTP id v23mr7721wrd.12.1522106210465; Mon, 26 Mar 2018 16:16:50 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.28.199.141 with SMTP id x135ls1441902wmf.10.gmail; Mon, 26 Mar 2018 16:16:49 -0700 (PDT) X-Received: by 10.28.101.6 with SMTP id z6mr15263153wmb.110.1522106209264; Mon, 26 Mar 2018 16:16:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522106209; cv=none; d=google.com; s=arc-20160816; b=vxXatz66nlCgZXtnsXl1eWHKBxEEdmthL5mJAG9adqKG99kDBYVGZnNN1GhFThr5BG RhHrc05saw1RulKyAMTuK6IszhVldPw282G42Ppe0WdminB5YjG3s433sKvqUOMHaxCY UHJBbwYRP+RcntIaaE4tsXZxSbgyrDu/2y1JUD7HXBz2CjCzP8MzNXaueldEGoJeKBzE r1PjHozzYkPHX4G2Qs/XyLdgqK3ptSwx8dQn+SXG8UFr+cE3BrebtP/FbX6dOvsQd8TZ Q9306KM3e12x84mt+BQRW1NpmasXmPAwMMUjPruEASym5uIU3C+itXtbrLSJJXb7ff4Q lcng== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:references:in-reply-to:mime-version :dkim-signature:arc-authentication-results; bh=upRMGFtuc6ujWjHv0abE9cAutMEbIdjzE3+OCjeusgY=; b=mzDAKY0VbODHJpb/pwmCoSpJwD2ah8C23KV2/G11YY4WyvEivB+5nOryoAMvwUqkk5 LhnIPAWjzeX0bF/SvZgI/rfRBBvk0PMVv3W+RV7/XJtE79dXGhT5ScuLGsKWViNWFdCo kNRM53cdDCId1Yr+zV2KqU0V6Z2mudVdP6VmUyn4GyHELiVvuAWZMQMNAcs7fBnDjJUL Mg5gRH9mqM9Q7WMLxDhGyNVRv40UfOSxgxXNVZcArRMzIApVqI6Jdjz3eb/c4yrXphe5 JWI63n7buGVrvkEMTBCdBF40Ml6K4Qv+NEiz/smy/6W3R4DTFX/L6YBqZQqv8/abyljb wFcQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@metafoo.co.uk header.s=default header.b=lwmJWMHP; spf=neutral (google.com: 81.27.85.19 is neither permitted nor denied by best guess record for domain of richard@metafoo.co.uk) smtp.mailfrom=richard@metafoo.co.uk Original-Received: from uk12.easy-internet.co.uk (uk12.easy-internet.co.uk. [81.27.85.19]) by mx.google.com with ESMTPS id o46si12059748wrf.103.2018.03.26.16.16.49 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 26 Mar 2018 16:16:49 -0700 (PDT) Received-SPF: neutral (google.com: 81.27.85.19 is neither permitted nor denied by best guess record for domain of richard@metafoo.co.uk) client-ip=81.27.85.19; Original-Received: from mail-oi0-f44.google.com ([209.85.218.44]:38577) by uk12.easy-internet.co.uk with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.89_1) (envelope-from ) id 1f0bM4-0000ir-MK for std-proposals@isocpp.org; Tue, 27 Mar 2018 00:16:48 +0100 Original-Received: by mail-oi0-f44.google.com with SMTP id c3-v6so17592274oib.5 for ; Mon, 26 Mar 2018 16:16:45 -0700 (PDT) X-Received: by 10.202.9.15 with SMTP id 15mr3271208oij.36.1522106204441; Mon, 26 Mar 2018 16:16:44 -0700 (PDT) Original-Received: by 10.74.161.35 with HTTP; Mon, 26 Mar 2018 16:16:23 -0700 (PDT) In-Reply-To: <9d30f89e-c92f-4c38-9943-b96b199d1ddd@isocpp.org> X-Gmail-Original-Message-ID: X-OutGoing-Spam-Status: No, score=0.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - uk12.easy-internet.co.uk X-AntiAbuse: Original Domain - isocpp.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - metafoo.co.uk X-Get-Message-Sender-Via: uk12.easy-internet.co.uk: authenticated_id: metafooc/from_h X-Authenticated-Sender: uk12.easy-internet.co.uk: richard@metafoo.co.uk X-Source: X-Source-Args: X-Source-Dir: X-Original-Sender: richard@metafoo.co.uk X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@metafoo.co.uk header.s=default header.b=lwmJWMHP; spf=neutral (google.com: 81.27.85.19 is neither permitted nor denied by best guess record for domain of richard@metafoo.co.uk) smtp.mailfrom=richard@metafoo.co.uk Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:37484 Archived-At: --f4f5e808e164a0535b056858f766 Content-Type: text/plain; charset="UTF-8" On 26 March 2018 at 10:52, Alexander Zaitsev 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 > , 2 > , 3 > , 4 > , 5 > , 6 > > > > > 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 > > > > > 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
On 2= 6 March 2018 at 10:52, Alexander Zaitsev <zamazan4ik@gmail.com><= /span> wrote:
Hello,

I am working on proposal about adding two new fun= ctions to STL: 'apply_permutation' and 'apply_reverse_permutati= on'. In attachments you can find this proposal (in PDF and HTML formats= ). Also you can find them on GitHub:=C2=A0https://github.com/ZaMaZaN4iK/ConfsANDProps/tree/master/Prop= osals

What is it?

=
Shortly, 'apply_permutation' and 'apply_reverse_perm= utation' are functions for reordering elements in a range in some defin= ed order.=C2=A0

Description

<= /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).

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).

Brief description

= Brief exaplantion is available on Microsoft Developer "Old new thing&q= uot; blog: 1, 2, 3, 4, 5, 6
=09 =09 =09



So you can play with it on=C2=A0wandbox.org

Open questions: Naming. I think apply_revere= se_permutation isn't nice name. Can you suggest anything better?
<= /div>

permute and u= npermute?

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'd be eas= y to provide permute_copy / unpermute_copy operations without this limitati= on (although if you don't do the permutation in-place, this becomes suf= ficiently simple that I'm not sure it warrants inclusion in the standar= d library).

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