RE: Generation of permutations

["Steven Deller" <deller@smsail.com>]

[-- Attachment #1: Type: text/plain, Size: 1419 bytes --]

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 <reinert.korsnes@chello.no> wrote in message 
> > news:<aajce7$7jb$1@snipp.uninett.no>...
> > 
> >>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 
<http://www.sgi.com/tech/stl/stl_algo.h>. 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

[-- Attachment #2: permuting.a --]
[-- Type: application/octet-stream, Size: 1094 bytes --]

------------------------------------------------------------------------------
-- package PERMUTING 
-- Provides a Permute generic package.  The generic parameters are an element
-- of any type, an index of discrete type, and an ordering function.  The 
-- package defines a list data type and procedure.   The procedure takes a
-- single argument of list type, and rearranges it to the next lexical 
-- permutation.  The exception "no_more_permutations" is raised when the
-- input list is lexically the last permutation.
-- The algorithm is derived from that presented in Dijkstra's "A Discipline of 
-- Programming".
------------------------------------------------------------------------------

package Permuting is

	generic
		type Element is private;
		type Index is (<>);
		with function "<=" ( left, right: Element ) return Boolean is <>;
	package Permute is
		type List is array (Index range <>) of Element;
		procedure Permute ( L: in out List );
		No_more_permutations : exception ;
	end Permute ;
	pragma Share_Body ( Permute , False ) ;

end Permuting ;

[-- Attachment #3: permutingB.a --]
[-- Type: application/octet-stream, Size: 2067 bytes --]

------------------------------------------------------------------------------
-- package body PERMUTING 
------------------------------------------------------------------------------

package body Permuting is

  package body Permute is

	procedure Exchange ( I, J: in out Element ) is
		Temp: Element;
	begin
		Temp := I;
		I := J;
		J := Temp;
	end Exchange;
	pragma Inline ( Exchange );

	procedure Permute ( L: in out List ) is

	  I, J : Index ;

	begin -- procedure Permute

	  -- Find the list tail, the largest end sequence that is all in order.
	  -- Find I, the last list position (largest i) where L(I) < L(I+1)
	  -- and the list tail is then all elements from L(I+1) on.

	  I := Index'pred( L'last ) ;
	  while ( I >= L'first  and then  L(Index'succ(I)) <= L(I) ) loop
		I := Index'pred(I) ;
	  end loop ;

	  if -- no such I exists (complete list is monotonically decreasing)
		( I < L'first ) 
	  then
		raise No_more_permutations ; -- because list is already lexically last
	  end if ;

 	  -- Find J in the tail, such that L(J) is the smallest value 
 	  -- for which L(J) > L(I).
 	  -- Note that L(I+1) > L(I) so at least one tail value is 
 	  -- larger than L(I), though there are usually more.
 	  -- Note also that the tail is in decreasing order, so we need only 
 	  -- search from the end backwards until we find a value that is larger.

	  J := L'last ;
	  while ( L(J) <= L(I) ) loop
		J := Index'pred(J) ;
	  end loop ;

	  Exchange( L(I), L(j) ) ;

 	  -- Put values in the tail into monotonically increasing order.
 	  -- Note that the tail is monotonically decreasing, so we need only
 	  -- reverse the order of values in the tail.

	  I := Index'succ(I) ;
	  J := L'last ;
	  while ( I < J ) loop 
		Exchange( L(I), L(J) ) ;
		I := Index'succ(I) ;
		J := Index'pred(J) ;
	  end loop ;

 	  -- List now contains the next lexical permutation of its values.

	  end Permute ;

	begin -- package Permute
		null ;
	end Permute ;

begin
	null ;
end Permuting ;