From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c42dbf68f5320193 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-10 19:54:03 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!fr.usenet-edu.net!usenet-edu.net!enst!enst.fr!not-for-mail From: "Steven Deller" Newsgroups: comp.lang.ada Subject: RE: Generation of permutations Date: Fri, 10 May 2002 21:52:29 -0400 Organization: ENST, France Sender: comp.lang.ada-admin@ada.eu.org Message-ID: Reply-To: comp.lang.ada@ada.eu.org NNTP-Posting-Host: marvin.enst.fr Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0050_01C1F86C.FC97AE80" X-Trace: avanie.enst.fr 1021085643 83814 137.194.161.2 (11 May 2002 02:54:02 GMT) X-Complaints-To: usenet@enst.fr NNTP-Posting-Date: Sat, 11 May 2002 02:54:02 +0000 (UTC) Return-Path: X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal In-Reply-To: <3CCEB2E0.7050701@mail.com> X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org X-Mailman-Version: 2.0.8 Precedence: bulk X-Reply-To: List-Help: List-Post: List-Subscribe: , List-Id: comp.lang.ada mail<->news gateway List-Unsubscribe: , Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org Xref: archiver1.google.com comp.lang.ada:23879 Date: 2002-05-10T21:52:29-04:00 This is a multi-part message in MIME format. ------=_NextPart_000_0050_01C1F86C.FC97AE80 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Write one way back when starting Ada 83 (1984). Based on Djkstra's algoritm in A Discipline of Programming. Is this what you want. (Sorry for the long delay -- I only get to read CLA once every few weeks when flying on a plane). It only does a next perumutation, but a "previous" permutation is pretty simple to devise. Use WP's to even prove it :-). Regards, Steve Deller > -----Original Message----- > From: comp.lang.ada-admin@ada.eu.org > [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Hyman Rosen > Sent: Tuesday, April 30, 2002 11:06 AM > To: comp.lang.ada@ada.eu.org > Subject: Re: Generation of permutations > > > Ted Dennison wrote: > > Reinert Korsnes wrote in message > > news:... > > > >>Are there any good (Ada95) packages for generation of permutations > >>(of elements in array) ? > > > > Sadly, that doesn't come up much...outside of homework assignments. > > ;-) Are you writing a bogosort? > > Whether or not it comes up much, in fact the algorithms > next_permutation and prev_permutation are part of the C++ > standard library. You can find them online in . It should not be too difficult for the OP to translate them to Ada. _______________________________________________ comp.lang.ada mailing list comp.lang.ada@ada.eu.org http://ada.eu.org/mailman/listinfo/comp.lang.ada ------=_NextPart_000_0050_01C1F86C.FC97AE80 Content-Type: application/octet-stream; name="permuting.a" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="permuting.a" -------------------------------------------------------------------------= -----=0A= -- package PERMUTING =0A= -- Provides a Permute generic package. The generic parameters are an = element=0A= -- of any type, an index of discrete type, and an ordering function. = The =0A= -- package defines a list data type and procedure. The procedure takes = a=0A= -- single argument of list type, and rearranges it to the next lexical =0A= -- permutation. The exception "no_more_permutations" is raised when the=0A= -- input list is lexically the last permutation.=0A= -- The algorithm is derived from that presented in Dijkstra's "A = Discipline of =0A= -- Programming".=0A= -------------------------------------------------------------------------= -----=0A= =0A= package Permuting is=0A= =0A= generic=0A= type Element is private;=0A= type Index is (<>);=0A= with function "<=3D" ( left, right: Element ) return Boolean is <>;=0A= package Permute is=0A= type List is array (Index range <>) of Element;=0A= procedure Permute ( L: in out List );=0A= No_more_permutations : exception ;=0A= end Permute ;=0A= pragma Share_Body ( Permute , False ) ;=0A= =0A= end Permuting ;=0A= ------=_NextPart_000_0050_01C1F86C.FC97AE80 Content-Type: application/octet-stream; name="permutingB.a" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="permutingB.a" -------------------------------------------------------------------------= -----=0A= -- package body PERMUTING =0A= -------------------------------------------------------------------------= -----=0A= =0A= package body Permuting is=0A= =0A= package body Permute is=0A= =0A= procedure Exchange ( I, J: in out Element ) is=0A= Temp: Element;=0A= begin=0A= Temp :=3D I;=0A= I :=3D J;=0A= J :=3D Temp;=0A= end Exchange;=0A= pragma Inline ( Exchange );=0A= =0A= procedure Permute ( L: in out List ) is=0A= =0A= I, J : Index ;=0A= =0A= begin -- procedure Permute=0A= =0A= -- Find the list tail, the largest end sequence that is all in order.=0A= -- Find I, the last list position (largest i) where L(I) < L(I+1)=0A= -- and the list tail is then all elements from L(I+1) on.=0A= =0A= I :=3D Index'pred( L'last ) ;=0A= while ( I >=3D L'first and then L(Index'succ(I)) <=3D L(I) ) loop=0A= I :=3D Index'pred(I) ;=0A= end loop ;=0A= =0A= if -- no such I exists (complete list is monotonically decreasing)=0A= ( I < L'first ) =0A= then=0A= raise No_more_permutations ; -- because list is already lexically last=0A= end if ;=0A= =0A= -- Find J in the tail, such that L(J) is the smallest value =0A= -- for which L(J) > L(I).=0A= -- Note that L(I+1) > L(I) so at least one tail value is =0A= -- larger than L(I), though there are usually more.=0A= -- Note also that the tail is in decreasing order, so we need only =0A= -- search from the end backwards until we find a value that is = larger.=0A= =0A= J :=3D L'last ;=0A= while ( L(J) <=3D L(I) ) loop=0A= J :=3D Index'pred(J) ;=0A= end loop ;=0A= =0A= Exchange( L(I), L(j) ) ;=0A= =0A= -- Put values in the tail into monotonically increasing order.=0A= -- Note that the tail is monotonically decreasing, so we need only=0A= -- reverse the order of values in the tail.=0A= =0A= I :=3D Index'succ(I) ;=0A= J :=3D L'last ;=0A= while ( I < J ) loop =0A= Exchange( L(I), L(J) ) ;=0A= I :=3D Index'succ(I) ;=0A= J :=3D Index'pred(J) ;=0A= end loop ;=0A= =0A= -- List now contains the next lexical permutation of its values.=0A= =0A= end Permute ;=0A= =0A= begin -- package Permute=0A= null ;=0A= end Permute ;=0A= =0A= begin=0A= null ;=0A= end Permuting ;=0A= ------=_NextPart_000_0050_01C1F86C.FC97AE80--