Ada2005 random

Ada2005 random

[Peter Hermann]

In an application I need a variable discrete random function.

Due to good reason I am reluctant to use my own very old
http://www.csv.ica.uni-stuttgart.de/ftp/pub/ada/ica/misc/randomph.txt

Instead, I would prefer to use
generic
   type Result_Subtype is (<>);
package Ada.Numerics.Discrete_Random is

which offers a
   function Random (Gen : Generator) return Result_Subtype;

but does not offer something like
   function Random (Gen : Generator;
                    from : Result_Subtype := Result_Subtype'first;
                     to  : Result_Subtype := Result_Subtype'last)
                                      return Result_Subtype;
which may or may not make sense in that raw disguise.

Anyway in Ada95, I have to roll my own code or let me send one ;-)

Does an AI exist for Ada95 or Ada2005?
Did I miss something?

-- 
--Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de
--Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen
--http://www.csv.ica.uni-stuttgart.de/homes/ph/
--Team Ada: "C'mon people let the world begin" (Paul McCartney)

Re: Ada2005 random

[Lutz Donnerhacke]

* Peter Hermann wrote:
> In an application I need a variable discrete random function.
> 
> Due to good reason I am reluctant to use my own very old
> http://www.csv.ica.uni-stuttgart.de/ftp/pub/ada/ica/misc/randomph.txt
> 
> Instead, I would prefer to use
> generic
>    type Result_Subtype is (<>);
> package Ada.Numerics.Discrete_Random is
> 
> which offers a
>    function Random (Gen : Generator) return Result_Subtype;
> 
> but does not offer something like
>    function Random (Gen : Generator;
>                     from : Result_Subtype := Result_Subtype'first;
>                      to  : Result_Subtype := Result_Subtype'last)
>                                       return Result_Subtype;
> which may or may not make sense in that raw disguise.

What's wrong with the following?

subtype Specialized_Result_Subtype is Result_Subtype range from .. to;
package Specialized_Random is
  new package Ada.Numerics.Discrete_Random (Specialized_Result_Subtype);

Re: Ada2005 random

[Peter Hermann]

Lutz and all,
> * Peter Hermann wrote:
>> In an application I need a variable discrete random function.
                              ^^^^^^^^
with "variable" I meant the following flexibility,  e.g. :
                  a := random(generator1, 1 , 9);
                  b := random(generator1, 1 , 8);
                  c := random(generator1, 3 , 7);

Re: Ada2005 random

[Lutz Donnerhacke]

* Peter Hermann wrote:
> Lutz and all,
>> * Peter Hermann wrote:
>>> In an application I need a variable discrete random function.
>                               ^^^^^^^^
> with "variable" I meant the following flexibility,  e.g. :
>                   a := random(generator1, 1 , 9);
>                   b := random(generator1, 1 , 8);
>                   c := random(generator1, 3 , 7);

procedure random(g : in out Generator; min, max : X; rand : out X)
  --# derives rand from g, min, max and
  --#            g from g;
  --# pre max > min;
  --# post rand in min .. max;
  is
   absmax : X;
begin
   absmax := X'Last - (X'Last - X'First) mod (max - min);
   --# check absmax > X'First;
   loop
      random(g, rand); --  ... random (g : in out Generator; r : out X) ...
      exit when rand <= absmax;
   end loop;
   return (rand - X'First) mod (max - min) + min;
end random;

Ok, it's the C approach ;-)

Re: Ada2005 random

[David C. Hoos, Sr.]

----- Original Message ----- 
From: "Peter Hermann" <ica2ph@sinus.csv.ica.uni-stuttgart.de>
Newsgroups: comp.lang.ada
To: <comp.lang.ada@ada.eu.org>
Sent: April 03, 2003 3:56 AM
Subject: Re: Ada2005 random


> Lutz and all,
> > * Peter Hermann wrote:
> >> In an application I need a variable discrete random function.
>                               ^^^^^^^^
> with "variable" I meant the following flexibility,  e.g. :
>                   a := random(generator1, 1 , 9);
>                   b := random(generator1, 1 , 8);
>                   c := random(generator1, 3 , 7);
Such an approach is statistcally dubious, since the same generator is
being used for all draws.  Normally, one would use a distinct
generator for each sequence.

> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
> 
> 

Re: Ada2005 random

[Peter Hermann]

David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote:
> Such an approach is statistically dubious, since the same generator is
> being used for all draws.  Normally, one would use a distinct
> generator for each sequence.

agreed: this is of course not a purist's approach
although I could live with it in the practice.
Using Lutz Do's code (thank you) should do the job.
Do you have a better idea how to pick out randomly from a set with
an always changing number of members?

-- 
--Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de
--Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen
--http://www.csv.ica.uni-stuttgart.de/homes/ph/
--Team Ada: "C'mon people let the world begin" (Paul McCartney)

Re: Ada2005 random

[Randy Brukardt]

Peter Hermann wrote in message ...
>David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote:
>> Such an approach is statistically dubious, since the same generator
is
>> being used for all draws.  Normally, one would use a distinct
>> generator for each sequence.
>
>agreed: this is of course not a purist's approach
>although I could live with it in the practice.
>Using Lutz Do's code (thank you) should do the job.
>Do you have a better idea how to pick out randomly from a set with
>an always changing number of members?


When I wanted to do that, I just borrowed the code from the Ada random
number generator. In all of the implementations I've seen, the actual
generator is the float one; the integer one just uses some code to
return the proper value. I just made a function that did that with
variable bounds instead of the generic ones.

I needed that for a 'choosing' algorithm, say drawing balls one by one
out of a bowl. If you have 8 balls originally, you're choosing 1 out of
7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and
discarding the useless ones, the second last draw can take a very long
time (only 2 out of 8 choices are meaningful). I'm pretty sure that this
is a valid technique; certainly the underlying float generator is still
random (at least as much as it ever was!), and the use of that result is
unbiased.

While it would be nice if Ada supported this directly, it's easy enough
to write it yourself.

             Randy Brukardt.

Re: Ada2005 random

[Steve]

The following code almost does what you asked for.  The problem is that
without the delays the selected random number is always the same.  I think
this is because a new generator is created for each call, and the "seed"
value (based on time) is the same unless I include delays.

with Ada.Integer_text_Io;
with Ada.Text_Io;

procedure CLA_Test2 is

  function Check( low, high : Integer ) return Integer is
    subtype check_range is integer range low .. high;
    package ranged_random is
      new Ada.Numerics.Discrete_Random( check_range );
    gen : ranged_random.Generator;
  begin
    ranged_random.reset( gen );
    return ranged_random.Random( gen );
  end Check;

begin
  Ada.Integer_Text_Io.Put( Check( 1, 10 ) );
  Ada.Text_Io.New_Line;
  Delay 1.0;
  Ada.Integer_Text_Io.Put( Check( 1, 10 ) );
  Ada.Text_Io.New_Line;
  Delay 1.0;
  Ada.Integer_Text_Io.Put( Check( 1, 10 ) );
  Ada.Text_Io.New_Line;
  Delay 1.0;
  Ada.Integer_Text_Io.Put( Check( 1, 10 ) );
  Ada.Text_Io.New_Line;
  Delay 1.0;
end CLA_Test2;

I would probably go with creating my own routine using the float package.
Steve
(The Duck)


"Peter Hermann" <ica2ph@sinus.csv.ica.uni-stuttgart.de> wrote in message
news:b6eog4$8jl$1@news.uni-stuttgart.de...
> In an application I need a variable discrete random function.
>
> Due to good reason I am reluctant to use my own very old
> http://www.csv.ica.uni-stuttgart.de/ftp/pub/ada/ica/misc/randomph.txt
>
> Instead, I would prefer to use
> generic
>    type Result_Subtype is (<>);
> package Ada.Numerics.Discrete_Random is
>
> which offers a
>    function Random (Gen : Generator) return Result_Subtype;
>
> but does not offer something like
>    function Random (Gen : Generator;
>                     from : Result_Subtype := Result_Subtype'first;
>                      to  : Result_Subtype := Result_Subtype'last)
>                                       return Result_Subtype;
> which may or may not make sense in that raw disguise.
>
> Anyway in Ada95, I have to roll my own code or let me send one ;-)
>
> Does an AI exist for Ada95 or Ada2005?
> Did I miss something?
>
> --
> --Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de
> --Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen
> --http://www.csv.ica.uni-stuttgart.de/homes/ph/
> --Team Ada: "C'mon people let the world begin" (Paul McCartney)

Re: Ada2005 random

[Christoph Grein]

See RM A.5.2(51) for a generator returning values in 0 .. M-1 for
variable M.

Re: Ada2005 random

[Peter Hermann]

Randy Brukardt <randy@rrsoftware.com> wrote:
> While it would be nice if Ada supported this directly, it's easy enough

that's it. However, it should be well crafted and therefore 
not necessarily my initial proposal, because with this one
I am feeling statistically uncomfortable ;-)

As Christoph Grein pointed out, the starting point is A.5.2(50-54).
A valuable Ada2005 pret-a-porter user call need to be well thought over.

-- 
--Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de
--Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen
--http://www.csv.ica.uni-stuttgart.de/homes/ph/
--Team Ada: "C'mon people let the world begin" (Paul McCartney)

Re: Ada2005 random

[@ 2003-04-04 8:27 UTC (permalink / raw)]

Peter Hermann wrote:
> David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote:
> 
>>Such an approach is statistically dubious, since the same generator is
>>being used for all draws.  Normally, one would use a distinct
>>generator for each sequence.
> 
> 
> agreed: this is of course not a purist's approach
> although I could live with it in the practice.
> Using Lutz Do's code (thank you) should do the job.
> Do you have a better idea how to pick out randomly from a set with
> an always changing number of members?
> 

   Pick a random number from Integer and do a "mod" operation.

Rodrigo

Re: Ada2005 random

[Dale Stanbrough]

Randy Brukardt wrote:

> I needed that for a 'choosing' algorithm, say drawing balls one by one
> out of a bowl. If you have 8 balls originally, you're choosing 1 out of
> 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and
> discarding the useless ones, the second last draw can take a very long
> time (only 2 out of 8 choices are meaningful). I'm pretty sure that this
> is a valid technique; certainly the underlying float generator is still
> random (at least as much as it ever was!), and the use of that result is
> unbiased.
> 
> While it would be nice if Ada supported this directly, it's easy enough
> to write it yourself.



How about


   for i in reverse 8..2 loop

      put (random (blah) mod i);

   end loop;


?

dale

Re: Ada2005 random

[Stuart Palin]

Dale Stanbrough wrote:

> How about
> 
>    for i in reverse 8..2 loop
> 
>       put (random (blah) mod i);
> 
>    end loop;

Of the many problems with this bit of code, perhaps the most
serious is the bias it introduces to the randomness.

Consider if random returned a value 0..10, then taking the
result mod 8 would give 2 ways of getting 0..2 but only one
way of getting 3..7.  Similar skew exist for other cases
(except 5).

--
Stuart Palin

Re: Ada2005 random

[Peter Hermann]

Rodrigo Garc?a <rodrigo.garcia.ARROBA.epfl.ch> wrote:
>   Pick a random number from Integer and do a "mod" operation.

Rodrigo,
well: you won the first round :-)
instantiation of discrete_random with an actual generic parameter
having a huge range of values, such as integer or natural or positive
and then mod,abs should sufficiently satisfy my statistic conscience.

-- 
--Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de
--Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen
--http://www.csv.ica.uni-stuttgart.de/homes/ph/
--Team Ada: "C'mon people let the world begin" (Paul McCartney)

Re: Ada2005 random

[Stuart Palin]

Randy Brukardt wrote:

<snip>

> I needed that for a 'choosing' algorithm, say drawing balls one by one
> out of a bowl. If you have 8 balls originally, you're choosing 1 out of
> 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and
> discarding the useless ones, the second last draw can take a very long
> time (only 2 out of 8 choices are meaningful). I'm pretty sure that this
> is a valid technique; certainly the underlying float generator is still
> random (at least as much as it ever was!), and the use of that result is
> unbiased.

Depending on the size of the set, and the nature in which
the size changes you could create an initial set and then
use one of the many 'shuffling' algorithms readily available
(make sure you use one that truly preserves the randomness
statistics - ISTR there is a subtle point in one of the most
obvious algorithms).  You can then simply draw your random
selection by moving through the list.

There are probably many 'themes' on this idea that you can
play around with, depending on your needs.  (For instance if
your 'set' is a linked list, you could make it a doubly
linked list, the secondary link being a random order).
  
--
Stuart Palin

Re: Ada2005 random

[Lutz Donnerhacke]

* Dale Stanbrough wrote:
> How about
>    for i in reverse 8..2 loop
>       put (random (blah) mod i);
>    end loop;
> ?

This is not uniformly distributed. Don't use that!

Re: Ada2005 random

[Lutz Donnerhacke]

* Peter Hermann wrote:
> Rodrigo Garc?a <rodrigo.garcia.ARROBA.epfl.ch> wrote:
>>   Pick a random number from Integer and do a "mod" operation.

> well: you won the first round :-)

No.

> instantiation of discrete_random with an actual generic parameter
> having a huge range of values, such as integer or natural or positive
> and then mod,abs should sufficiently satisfy my statistic conscience.

Using "mod" destroys the uniformness of your random data an therefore will
not meet most of the assumed randomness preconditions.

Re: Ada2005 random

[Lutz Donnerhacke]

* Steve wrote:
> The following code almost does what you asked for.

No.

> The problem is that without the delays the selected random number is
> always the same.

This should lead you to the error.

> I think this is because a new generator is created for each call, and the
> "seed" value

Ack

> (based on time) is the same unless I include delays.

Nobody says, that the time is included in the seed. And more important: Even
if the random seed is generated from the time, the generation of random
values from the seed does have completely different statistical properties
than generating a seed from the time.

Therefore your code is wrong, wrong, and wrong. Don't use it!

Re: Ada2005 random

[Dale Stanbrough]

In article <slrnb8r5e4.ov.lutz@taranis.iks-jena.de>,
 Lutz Donnerhacke <lutz@iks-jena.de> wrote:

> * Dale Stanbrough wrote:
> > How about
> >    for i in reverse 8..2 loop
> >       put (random (blah) mod i);
> >    end loop;
> > ?
> 
> This is not uniformly distributed. Don't use that!

If the random numbers are uniformly distributed, why wouldn't a 
window on that distribution also be uniformly distributed?
Could you give an example?

Dale

Re: Ada2005 random

[Jeffrey Carter]

Peter Hermann wrote:
> In an application I need a variable discrete random function.

PragmARC.Universal_Random from the PragmAda Reusable Components has what 
you want.

http://home.earthlink.net/~jrcarter010/pragmarc.htm

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail

Re: Ada2005 random

[Steve]

"Lutz Donnerhacke" <lutz@iks-jena.de> wrote in message
news:slrnb8r5nt.ov.lutz@taranis.iks-jena.de...
[snip]
> Nobody says, that the time is included in the seed....

Actually they did (or at least based on a time-dependent state):

LRM A.5.2(34)
  Sets the state of the specified generator to one that is an unspecified
function of the value of the parameter Initiator (or to a time-dependent
state, if only a generator parameter is specified). The latter form of the
procedure is known as the time-dependent Reset procedure.


In my example a new "Generator" (presumably containing a seed value) is
created each time the routine is called.  This is likely to give different
results than propagting the generator through a sequence of calls to Random.

> And more important: Even
> if the random seed is generated from the time, the generation of random
> values from the seed does have completely different statistical properties
> than generating a seed from the time.
>
> Therefore your code is wrong, wrong, and wrong. Don't use it!

BTW: Just because I gave an example of how it "might" be done, doesn't mean
I think it's a good method.  The fact that a new "generator" is created with
each call is somewhat dubious.

Steve
(The Duck)

Re: Ada2005 random

[Martin Krischik]

On Fri, 04 Apr 2003 10:21:44 +0000, Dale Stanbrough wrote:

> Randy Brukardt wrote:
> 
> 
>    for i in reverse 8..2 loop

Should that not be:

for i in reverse 2 .. 8 loop

on in full:

for i in reverse Integer range 2 .. 8 loop

> 
>       put (random (blah) mod i);
> 
>    end loop;

With Regards

Martin

-- 
Martin Krischik
mailto://Martin@krischik.com
http://ada.krischik.com

Re: Ada2005 random

[Pascal Obry]

Dennis Lee Bieber <wlfraed@ix.netcom.com> writes:

>         Might do for the short run, but I can see a failure in the long
>         run...
> 
>         For simplicity, say "Integer" covers 0..8, and the selection run 0..7 
> (necessitating use of a mod 8)... The result will be that selection 0 
> will have 2/9 chances with 1..7 having 1/9, rather than all having a 
> 1/8 chance.

Ok, but integer has a range of -(2 ** 31) .. +(2 ** 31 - 1) so the difference
could be something around +/- (x / (2 ** 31 - 1)) !

Not so bad for a simple program I would say.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|         http://perso.wanadoo.fr/pascal.obry
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Ada2005 random

[tmoran]

> Ok, but integer has a range of -(2 ** 31) .. +(2 ** 31 - 1) so the difference
> could be something around +/- (x / (2 ** 31 - 1)) !
  A small error if x is small, but rather large if x is, say, 3/8 * 2**31
If the generator's range = a*x+b, then (random mod x) will take
values < b a+1 times and values >= b only a times.  If a is small,
a/(a+1) will differ substantially from 1.0
  Also, there's no guarantee that the generator's range is Integer or
that it is 32 bits wide.

Re: Ada2005 random

[Pascal Obry]

tmoran@acm.org writes:

> > Ok, but integer has a range of -(2 ** 31) .. +(2 ** 31 - 1) so the difference
> > could be something around +/- (x / (2 ** 31 - 1)) !
>   A small error if x is small, but rather large if x is, say, 3/8 * 2**31

Right, reading original question it seems that x was supposed to be small.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|         http://perso.wanadoo.fr/pascal.obry
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Ada2005 random

[Samuel Tardieu]

>>>>> "Dale" == Dale Stanbrough <dstanbro@bigpond.net.au> writes:

Dale> If the random numbers are uniformly distributed, why wouldn't a
Dale> window on that distribution also be uniformly distributed?

"mod" does not create a window.

Dale> Could you give an example?

Suppose that random numbers are uniformly distributed over the set
{0,1,2}. Apply "mod 2" to that, you get {0,1,0}. The probability of
getting a 0 is twice the one of getting a 1.

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam

Re: Ada2005 random

[@ 2003-04-06 15:44 UTC (permalink / raw)]

Christoph Grein wrote:
> See RM A.5.2(51) for a generator returning values in 0 .. M-1 for
> variable M.

   Without any kind of doubt, that's the rightest solution!

Rodrigo

PS: In fact, it reminds me when I learned how to get random numbers in 
BASIC, where the only random function returns float values between 0 and 1.

Re: Ada2005 random

[Jean-Etienne Doucet]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1555 bytes --]

Randy Brukardt wrote:
|
| I needed that for a 'choosing' algorithm, say drawing balls one by one
| out of a bowl. If you have 8 balls originally, you're choosing 1 out of
| 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and
| discarding the useless ones, the second last draw can take a very long
| time (only 2 out of 8 choices are meaningful). I'm pretty sure that this
| is a valid technique; certainly the underlying float generator is still
| random (at least as much as it ever was!), and the use of that result is
| unbiased.
|

For this kind of problems, I use the Ada.Numerics.Float_Random generator,
along with the function:

  function Rand (N : Positive) return Positive is
     -- gives a random integer in the range 1 .. N
  begin
     return Integer(Float(N) * Random(Gen) + 0.5);
  end Rand;


It can be used for ranges other than 1 .. N:

  function Rand (Min, Max : Integer) return Integer is
     -- gives a random integer in the range Min .. Max
  begin
     return Rand(Max - Min + 1) + Min - 1;
  end Rand;


It works as well for enum types:

  type Enum is (...);
  
  function Random_Enum return Enum is 
     -- gives a random Enum value
  begin
     return Enum'Val(Rand(Enum'Pos(Enum'Last) + 1) - 1);
  end Random_Enum;


I've never had a problem with this.

_______________________________________________________________________________
Jean-Etienne Doucet / LAAS-CNRS / Toulouse, France       E-mail: doucet@laas.fr
"S'il n'y a pas de solution, c'est qu'il n'y a pas de probl�me."  (Les Shadoks)

Re: Ada2005 random

[Lutz Donnerhacke]

* Jean-Etienne Doucet wrote:
> For this kind of problems, I use the Ada.Numerics.Float_Random generator,
> along with the function:

If performance is not an issue, you are right.

Re: Ada2005 random

[Randy Brukardt]

Martin Krischik wrote in message ...
>On Fri, 04 Apr 2003 10:21:44 +0000, Dale Stanbrough wrote:
>
>> Randy Brukardt wrote:
>> 
>> 
>>    for i in reverse 8..2 loop
>
>Should that not be:
>
>for i in reverse 2 .. 8 loop


Yes, of course.

         Randy.

Re: Ada2005 random

[Robert I. Eachus]

Dale Stanbrough wrote:
> Randy Brukardt wrote:
> 
> 
>>I needed that for a 'choosing' algorithm, say drawing balls one by one
>>out of a bowl. If you have 8 balls originally, you're choosing 1 out of
>>7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and
>>discarding the useless ones, the second last draw can take a very long
>>time (only 2 out of 8 choices are meaningful). I'm pretty sure that this
>>is a valid technique; certainly the underlying float generator is still
>>random (at least as much as it ever was!), and the use of that result is
>>unbiased.
>>
>>While it would be nice if Ada supported this directly, it's easy enough
>>to write it yourself.

If you need a permutation, the best way to do it is to generate a set of 
random (float) values, associate them with the data to be permuted and 
the sort on this key.  I have seen a lot of code that attempts to 
permute a list by going through the list and exchanging elements.  For 
lists of length greater than two this can easily be shown to be biased.

For example there are 3! = 6 possible permutions of a list of three 
elements, the usual version of the swapping algorithm has 3^3 = 27 
possible outcomes, another (worse) variation has 2^3 = 8 different 
outcomes.  In either case the number of outcomes is not evenly divisible 
by the number of different permutations.

Even if you do this, there is another potential problem.  For a set of 
size N, there are N! possible permutations.  For example for a deck of 
cards, there are 52! possible permutations.  If you are generating 
bridge hands, there are 52!/(13!)^4 different possible deals.  Now if 
you are taking the (pseudo-)random sequence from a single generator, 
there will be at most as many different possible hands as there are 
possible starting seeds for the generator.  For the generator that I 
wrote, which AFAIK is still used by GNAT, if you use the time based 
version of Reset, there are more than 2^32 possible starting values, but 
of course, they won't all occur in a particular year.

If you really, really care about making it possible to generate a large 
fraction of all possible permutations, the way to do it is to take 
several generators with seeds generated based on different random data, 
then shuffle the deck more than once.

This program should serve as an example of how to do this.  (Note, I 
don't claim this is "right" since I don't use two generators, and 
shuffle twice.)

with Ada.Numerics.Float_Random;
package Statistics is

    subtype Generator is Ada.Numerics.Float_Random.Generator;

    type Direction is (Ascending, Descending);

    generic
      type Element_Type is private;
      type Index_Type is (<>);
      type List_Type is array (Index_Type range <>) of Element_Type;
      with function "<" (L, R : Element_Type) return Boolean is <>;
    procedure Sorting (List : in out List_Type);
    --  General-purpose sorting procedure

    generic
      type Element_Type is private;
      type Index_Type is (<>);
      type List_Type is array (Index_Type range <>) of Element_Type;
    procedure Shuffling (List : in out List_Type;
                         Gen  : in     Generator);
    --  Permute the contents of List randomly

end Statistics;
------------------------------------------------------------------------
with Ada.Numerics.Float_Random;
package body Statistics is

    package NFR renames Ada.Numerics.Float_Random;

--  generic
--    type Element_Type is private;
--    type Index_Type is (<>);
--    type List_Type is array (Index_Type range <>) of Element_Type;
--    with function "<" (L, R : Element_Type) return Boolean is <>;
    procedure Sorting (List : in out List_Type) is
       --  Quicksort
       Part  : Element_Type;
       First : Index_Type;
       Last  : Index_Type;
    begin
      --  Don't break on short lists;
       if List'Length <= 1
       then return;
       elsif List'Length = 2 then
          if List(List'Last) < List(List'First)
          then
             Part := List(List'First);
             List(List'First) := List(List'Last);
             List(List'Last) := Part;
          end if;
          return;
       end if;

       --  now it is safe to assume that List'First and List'Last
       --  are in range.

       First := List'First;
       Last  := List'Last;

       -- choose partition value
       Part := List(First);

       -- partition list
    Main_Loop:
       loop
          if Part < List(Last) then
             Last := Index_Type'PRED(Last);
             exit Main_Loop when Last=First;
          else
             List(First) := List(Last);
             First := Index_Type'SUCC(First);
             exit Main_Loop when Last=First;
             while List(First) < Part loop
                First := Index_Type'SUCC(First);
                exit Main_Loop when Last=First;
             end loop;
             List(Last) := List(First);
             Last := Index_Type'PRED(Last);
             exit Main_Loop when Last=First;
          end if;
       end loop Main_Loop;

       List(First) := Part; -- at this point First = Last.
       Sorting(List(List'First..Index_Type'PRED(Last)));
       Sorting(List(Index_Type'SUCC(Last)..List'Last));
    end Sorting;


    --  generic
    --   type Element_Type is private;
    --   type Index_Type is (<>);
    --   type List_Type is array (Index_Type range <>) of Element_Type;
    procedure Shuffling (List : in out List_Type;
                         Gen  : in     Generator) is
       List_Copy : constant List_Type := List;

       type Rec is
          record
             Index : Index_Type;
             Rand  : Float;
          end record;

       type Rec_Array is array (Index_Type range <>) of Rec;

       Temp : Rec_Array(List'Range);

       function "<" (L, R: Rec) return Boolean is
       begin return L.Rand < R.Rand; end "<";

       procedure Sort is new Sorting(Rec, Index_Type, Rec_Array, "<");

     begin
        for I in Temp'Range loop
           Temp(I) := (I, NFR.Random(Gen));
        end loop;

        Sort(Temp);  --  Sort based on value of random number

        --  Now rearrange List based on the order of indices in Temp
        for I in List'Range loop
           List(I) := List_Copy(Temp(I).Index);
        end loop;
     end Shuffling;

end Statistics;
---------------------------------------------------------------------------
with Ada.Numerics.Float_Random;
with Statistics;
with Text_IO; use Text_IO;
procedure Bridge_Hands is
-- a procedure to produce random (but sorted) bridge hands for duplicate.

   package NFR        renames Ada.Numerics.Float_Random;

   Gen: NFR.Generator;
   function Rand(G: in NFR.Generator := Gen) return Float renames 
NFR.Random;

   type Direction is (North, East, South, West);
   type Suits is (Spades, Hearts, Diamonds, Clubs);
   type Ranks is (Ace, King, Queen, Jack, Ten, Nine, Eight, Seven,
                 Six, Five, Four, Three, Deuce);

   Display_Suit: constant array(Suits) of Character := "SHDC";
   Display_Rank: constant array(Ranks) of Character := "AKQJT98765432";

   subtype Dealer_Name is String(1..5);
   Display_Dealers: constant array(0..3) of Dealer_Name :=
      ("North", "East ", "South", "West ");
   subtype Vulnerability is String(1..11);
   Display_Vulnerability: constant array(0..3) of Vulnerability :=
      ("None       ","North/South","East/West  ","Both       ");
   package Int_IO is new Text_IO.Integer_IO(Integer);
   Number_of_Hands: Integer;

   type Card is record
     Suit: Suits;
     Rank: Ranks;
   end record;

   type Card_Array is array (Natural range <>) of Card;

   Deck: Card_Array(0..51);

   subtype Hand is Card_Array(0..12);
   Hands: array(Direction) of Hand;


   function By_Rank(L,R: Card) return Boolean is
   begin return L.Rank < R.Rank; end By_Rank;
   pragma INLINE(By_Rank);

   procedure Sort_Hand is
     new Statistics.Sorting(Card, Natural, Card_Array, By_Rank);

   procedure Shuffle is
     new Statistics.Shuffling(Card, Natural, Card_Array);

   procedure Deal is
   begin
     for I in Hand'Range loop
       for J in Hands'Range loop
         Hands(J)(I) := Deck(I*4 + Direction'POS(J));
       end loop;
     end loop;
     for I in Hands'Range loop
       Sort_Hand(Hands(I));
       -- sort cards by rank, but not by suit.
     end loop;
   end Deal;

   function Cards(D: in Direction; S: in Suits) return String is
     Temp: String(1..26) := (others => ' ');
     Index: Natural := 3;
   begin
     Temp(1) := Display_Suit(S);
     for I in Hand'Range loop
       if Hands(D)(I).Suit = S
       then
         Temp(Index) := Display_Rank(Hands(D)(I).Rank);
         Index := Index + 2;
       end if;
     end loop;
     if Index = 3 then Temp(3..5) := "---"; end if;
     return Temp;
   end Cards;

begin

   -- Use time-dependant random numbers:

   NFR.Reset(Gen);

   -- Initialize deck.

   for I in Deck'Range loop
     Deck(I) := (Suits'VAL(I/13), Ranks'VAL(I mod 13));
   end loop;

   Text_IO.Put_Line("Enter number of hands, default is 32:");

   begin
     Int_IO.Get(Number_of_Hands);
   exception when others =>
     Number_of_Hands := 32;
   end;

   for I in 0..Number_of_Hands - 1 loop
     Text_IO.New_Page;
     Text_IO.New_Line(3);
     Text_IO.Put_Line("                                Board:        "
         & Integer'IMAGE(I+1));
     Text_IO.Put_Line("                                Dealer:        "
       & Display_Dealers(I mod 4));
     Text_IO.Put_Line("                                Vulnerability: "
       & Display_Vulnerability((I + I/4) mod 4));
     New_Line(3);

     Shuffle(Deck, Gen);

     Deal;

     Text_IO.Put_Line("                                NORTH");
     Text_IO.New_Line;
     Text_IO.Put_Line("                              " &
                      Cards(North,Spades));
     Text_IO.Put_Line("                              " &
                      Cards(North,Hearts));
     Text_IO.Put_Line("                              " &
                      Cards(North,Diamonds));
     Text_IO.Put_Line("                              " &
                      Cards(North,Clubs));
     New_Line(2);
     Text_IO.Put_Line("       WEST                                  " &
                      "          EAST");
     Text_IO.New_Line;
     Text_IO.Put_Line("     " & Cards(West,Spades) &
                      "                      " & Cards(East,Spades));
     Text_IO.Put_Line("     " & Cards(West,Hearts) &
                      "                      " & Cards(East,Hearts));
     Text_IO.Put_Line("     " & Cards(West,Diamonds) &
                      "                      " & Cards(East,Diamonds));
     Text_IO.Put_Line("     " & Cards(West,Clubs) &
                      "                      " & Cards(East,Clubs));
     New_Line(2);
     Text_IO.Put_Line("                                SOUTH");
     Text_IO.New_Line;
     Text_IO.Put_Line("                              " &
                      Cards(South,Spades));
     Text_IO.Put_Line("                              " &
                      Cards(South,Hearts));
     Text_IO.Put_Line("                              " &
                      Cards(South,Diamonds));
     Text_IO.Put_Line("                              " &
                      Cards(South,Clubs));
   end loop;

end Bridge_Hands;

Re: Ada2005 random

[Mark Biggar]

Robert I. Eachus wrote:
> Dale Stanbrough wrote:
> 
>> Randy Brukardt wrote:
>>
>>
>>> I needed that for a 'choosing' algorithm, say drawing balls one by one
>>> out of a bowl. If you have 8 balls originally, you're choosing 1 out of
>>> 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and
>>> discarding the useless ones, the second last draw can take a very long
>>> time (only 2 out of 8 choices are meaningful). I'm pretty sure that this
>>> is a valid technique; certainly the underlying float generator is still
>>> random (at least as much as it ever was!), and the use of that result is
>>> unbiased.
>>>
>>> While it would be nice if Ada supported this directly, it's easy enough
>>> to write it yourself.
> 
> 
> If you need a permutation, the best way to do it is to generate a set of 
> random (float) values, associate them with the data to be permuted and 
> the sort on this key.  I have seen a lot of code that attempts to 
> permute a list by going through the list and exchanging elements.  For 
> lists of length greater than two this can easily be shown to be biased.
> 
> For example there are 3! = 6 possible permutions of a list of three 
> elements, the usual version of the swapping algorithm has 3^3 = 27 
> possible outcomes, another (worse) variation has 2^3 = 8 different 
> outcomes.  In either case the number of outcomes is not evenly divisible 
> by the number of different permutations.

The way I usualy do random array shuffle has no bias

for i in reverse 2..n loop
	j := random(1..i);
	swap(x(i), x(j));
end loop;

that translates to "randomly select with out replacement until the
unselected set is empty"  and in the 3 item case results in exactly
6 outcomes (first iteration select 1 of 3, second iteration select
1 of 2 for 6 outcomes).

-- 
Mark Biggar
mark@biggar.org
mark.a.biggar@attbi.com