220 37477 article Path: news.gmane.org!.POSTED!not-for-mail From: =?UTF-8?B?R2HFoXBlciBBxb5tYW4=?= Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding 'apply_permutation' functions to the standard library Date: Mon, 26 Mar 2018 19:42:57 +0100 Lines: 185 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="000000000000b3f0000568552557" X-Trace: blaine.gmane.org 1522089677 4495 195.159.176.226 (26 Mar 2018 18:41:17 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 26 Mar 2018 18:41:17 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDRYVJ6TVYBRBRX64TKQKGQEVWN42TA@isocpp.org Mon Mar 26 20:41:13 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pf0-f197.google.com ([209.85.192.197]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1f0X3Q-00012O-9L for gclcip-std-proposals@m.gmane.org; Mon, 26 Mar 2018 20:41:12 +0200 Original-Received: by mail-pf0-f197.google.com with SMTP id k16sf697635pfi.7 for ; Mon, 26 Mar 2018 11:43:19 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1522089799; cv=pass; d=google.com; s=arc-20160816; b=AjTvJKSZTIM4COFIe4r7BkAcvkG1rPxulbID9B+oP5xyAAyZKGENvm08kJu6NXHHGg NKd8mzAPaPIiD4bJH4j5rAwYvrOEW/qSO8+QnVZrTSpheVJ9I7Vad4QrznfbVUdGfWsn NL/3vnUR4hwIjcQmlKaNnDPhRNafBS0KaJg02IHB5G93St2nW98qDdIMUiLeYB0/MOv8 r8uoEMOFBtB7KcgPJxdcq4XYw4o010ZTRlL3sGWVrs2haxvRDqB9aUhx0HGvzU9pZ8iA siT4OhXPDba+MU20X2UzpD7SkXGiDyY3cXKnAiySPy2YWep7Zc6O+BMZPBZaZQwxwFHH S0wA== 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=31+2e/NSLTlU9tkALpmmAE8q+HLiIhKrJi1f0DEqN+U=; b=SKWmSjHRQE2XWkbH+1PzvRk1oauN+VqGqYR60D9BVui5ksiwcze7duSdIXfhr9sZ2Z KGE4WH3D42ijFvB9wKbE7JkeJXJO5c0riO1NMvrgmZamu65ao12K+ijv5ZjhKlbl9Iuw n7zdEMcCOTpM95lGvEqHmJNWGnC3Sq8SY9lTC8jWsopvdxNI57H1UWZV1K0uDuKL+83e huBfbBY1LR5yiUu5VH99igMTE/RgS8fvKu2rfioYsap4utsJQLAP5SMr+Fw1wb16ilPv B+jdAjnUf97ZwzrZcF4Rhz9G8a6fTuF1vBnO/FDuGCkTGgbqMvVjCC4qbQ+3DD4A5I+u c2pQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=r03Nq8zj; spf=pass (google.com: domain of gasper.azman@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=gasper.azman@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com 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=31+2e/NSLTlU9tkALpmmAE8q+HLiIhKrJi1f0DEqN+U=; b=CCXTzFgyXUziY6iJB63SB8AmJENn/0RtEma72TFEb7pfxgvbDikPf+gGHXo2DPvGv3 T0WCdIa14Avas2ruOg1Zdq5EaDN2xoxxautQMyeirYRxTvzLXVnLmJ9XcT3CUER7o95X LMZDIzZdKQQ+7kYv4ybL/Y4AzGxmUusfilM5n67Gf/Lwb3TF3P2Skjm0mV6quDBIO2R/ izXs0qnKJjuVmoXxm76hcmh0ED5lizt7e/HELrdTFbXPUcS+hoVcg9oOTHG7+OWf425n zjUV+sm7vl+Jrsl1Y/FoUj27DeZIS7537WVV2ZWzSu6ju5U/2HMX1kl/nhQ5ccxFHOe5 C2qg== 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=31+2e/NSLTlU9tkALpmmAE8q+HLiIhKrJi1f0DEqN+U=; b=WHeDdfJCkOqOFCOQxYjDvY5D/ejgrkpXSe5Ca7POt6jPF04QjcUlBmv3kksey85IPO MeCcMxJ1uoAUBvrImeC3F4wI07ToH6CBsTZ+gofyK7fLqIJxkzZhs+aHuSrxGKgksEg3 uktmXUDzHmOdiw61AKB69wniM5NsPGfAR4/7fRSWRwpAKxntWtuq2hoU1d0OlVY4FWj7 5oohizT4YlW8zs0spCmAcjs1nT+InEFQw09qg69irDCIwJGkKLrmdVenJgczdssR0o7Z bZLSAZaLXwslRJgbcaq8NRFaz7wQCh+ZMoVyWIkXMRc4YiBRXEKmxdSm7CcG5zzf4Y6M w6Vw== X-Gm-Message-State: AElRT7ELsQmKvNsMTv9fqMtg1gdCZFCftXd5qlg7kycVQ4fie9z6DF++ GB8dn/CR6Vgh9OgAZNHFqgnRLQ== X-Google-Smtp-Source: AG47ELs5/lFr8qXhZTvYWMY5Jeln6YJMdI/T7QETkcG+avyjA3tqZzqhQHb151TGpTQrt8asp9LTNg== X-Received: by 10.101.67.10 with SMTP id j10mr10978503pgq.168.1522089799051; Mon, 26 Mar 2018 11:43:19 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a17:902:b83:: with SMTP id 3-v6ls6745694plr.9.gmail; Mon, 26 Mar 2018 11:43:17 -0700 (PDT) X-Received: by 2002:a17:902:66e6:: with SMTP id e93-v6mr42148077plk.312.1522089797967; Mon, 26 Mar 2018 11:43:17 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522089797; cv=none; d=google.com; s=arc-20160816; b=r8htoi+Igudtco776ieDtz7uNDWnLEnBqsg/CoCdsdaM1WY0K0oSTqzUluRRf+9rjx +vd8T/8vzTPJkJ56C2FRK00BNS9qW6DHFUm+v2JIKd85uVf2w+wwYn+iVz1wHWk4KY32 N8LkAUsK7tvmTGIbzkJ9we6+pyWX8QF7k7h6vJxcAB2HylvlR2GIfImFu6N3TEBUbFvK YCOTpcWvQfM8PG06YgaDu5GUcIHdaWM/9IMaUuYtxe88PH06vGmflqRStTNoVRrj/OMU zZ9G6NqkuLvs6fSJtaBuyTdmHrmMXf//wACpAcIB14J2cydMJOPmaFnKPMj65+Mh81lN Q20w== 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=8NGPMhN5p59t48yvTXPSmmzh1ecWhdyoWS3yrCr0HV0=; b=OEPJ7WUgDHGT8Zv8oAAsDWIF81aXPN/aI2IU1pCNPHH2dUhLUymT/nytnKUxqkiE3b IkIXJ0wtCgPcbOkAUWjx68BtpFS7HnZ4bcUD03h2lBBcj7yAhVnP9EzKDclBnHb+1HTy rZD+cd2w1JYR+htQzyrFWBeTDYH5mJBd/5TGFQiU1rAgXzN78bpxm34oMUbmN/yrjji2 5Y4rpyWsMXVSqCQMYvGJEFHL3yg2wP/eiYmmAg61PHIF2ye2Vv2U1uOhSmztUFdnX8v+ 3kCI5u0q8djn+d76/5fb3nv5dy3a/WKBUfGUW2xKHrDlbuzepjv+ACLiNLpUWKf95pkG yh5w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=r03Nq8zj; spf=pass (google.com: domain of gasper.azman@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=gasper.azman@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Original-Received: from mail-sor-f41.google.com (mail-sor-f41.google.com. [209.85.220.41]) by mx.google.com with SMTPS id m39-v6sor7627146plg.20.2018.03.26.11.43.17 for (Google Transport Security); Mon, 26 Mar 2018 11:43:17 -0700 (PDT) Received-SPF: pass (google.com: domain of gasper.azman@gmail.com designates 209.85.220.41 as permitted sender) client-ip=209.85.220.41; X-Received: by 2002:a17:902:a60d:: with SMTP id u13-v6mr23207765plq.161.1522089797610; Mon, 26 Mar 2018 11:43:17 -0700 (PDT) Original-Received: by 10.100.151.69 with HTTP; Mon, 26 Mar 2018 11:42:57 -0700 (PDT) In-Reply-To: <9d30f89e-c92f-4c38-9943-b96b199d1ddd@isocpp.org> X-Original-Sender: gasper.azman@gmail.com X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=r03Nq8zj; spf=pass (google.com: domain of gasper.azman@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=gasper.azman@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com 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:37477 Archived-At: --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 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? > > -- > 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 > > . > -- 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
apply_inverse_permutation?

I'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.

G

On Mon, M= ar 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_permut= ation'. In attachments you can find this proposal (in PDF and HTML form= ats). Also you can find them on GitHub:=C2=A0https://github.com/ZaMaZaN4iK/ConfsANDProps/tree/master/P= roposals

What is it?

<= /b>
Shortly, 'apply_permutation' and 'apply_reverse_p= ermutation' are functions for reordering elements in a range in some de= fined order.=C2=A0

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

Brief description

Brief exaplantion is available on Microsoft Developer "Old new thin= g" 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>

--
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-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/9d30= f89e-c92f-4c38-9943-b96b199d1ddd%40isocpp.org.

--
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 https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAANG%3DkVA= i8ow7PBdW68OXK%3DB7RxYyvGZeNOMjJ-cFC9d3N4%2BvA%40mail.gmail.com.
--000000000000b3f0000568552557-- .