Re: Random numbers with no duplicates

From: Gary Labowitz (glabowitz_at_comcast.net)
Date: 09/27/04

  • Next message: Spacen Jasset: "Re: Random numbers with no duplicates" 
    Date: Mon, 27 Sep 2004 08:41:36 -0400

    "David White" <no@email.provided> wrote in message
    news:ufO5d.2860$pl.51123@nasal.pacific.net.au...
    > "Gary Labowitz" <glabowitz@comcast.net> wrote in message
    > news:oJydnQObS4S3CsrcRVn-tA@comcast.com...
    > > "David White" <no@email.provided> wrote in message
    > > news:n7I5d.2844$pl.50584@nasal.pacific.net.au...
    > > > That's not right. The last card would always be swapped with itself,
    > > leaving
    > > > the array as it is.
    > > >
    > > > BTW, another feature of this algorithm is that you only need to fill
    the
    > > > array once for any number of repeat uses. Once all values have been
    > > > selected, they are all still in the array. They are in some
    > pseudo-random
    > > > order, but that doesn't matter because the starting order is
    irrelevant
    > to
    > > > the randomness of the selections. Just reset the range to 10 and
    repeat
    > > the
    > > > process.
    > > If on the last step the tenth card is swapped with a randomly selected
    > > location, there is a pretty good chance that it will not be swapped with
    > > itself.
    >
    > On the last step there's only one location left that can be selected.
    >
    > > The algorithm is to swap each location in the array (from 0 - (n-1))
    with
    > > randomly selected locations in the range 0 - (n-1).
    >
    > No, the algorithm is to randomly generate an index in the range 0..N-1
    > inclusive, where N is the number of values remaining, and swap the value
    at
    > the selected location with the value at N-1. Then you decrement N, which
    > places the selected value outside the selectable range for the next
    > selection. Here are the relevant parts from a card dealer class:
    >
    > CardDeck::CardDeck()
    > {
    > srand(/* suitable seed */);
    > cards_remaining = N; // e.g., 52
    > for(int icard = 0; icard < N; ++icard)
    > deck[icard] = icard;
    > }
    >
    > int CardDeck::DealCard()
    > {
    > if(cards_remaining == 0)
    > return -1; // error, deck empty
    > int icard = rand() % cards_remaining; // crude, and not ideal, but

    > good enough for most purposes
    > int card = deck[icard];
    > deck[icard] = deck[cards_remaining-1];
    > deck[cards_remaining-1] = card;
    > --cards_remaining;
    > return card;
    > }
    >
    > void CardDeck::Shuffle() // i.e., to re-deal
    > {
    > cards_remaining = N;
    > }

    We're dancing around two different flag poles. I'm under the assumption that
    shuffle works as follows:

    Select a location in the array. This selection process will proceed from [0]
    to [n-1].
    Generate a (pseudo-)random number between 0 and n-1.
    Swap the selected location with the randomly selected location.

    Repeat the above process until you have done n swaps.

    What you indicate doing is only swapping elements that remain after each
    swap. I. e., you are keeping track of how many swaps have already been done
    and only doing the remaining locations. This biases the swapping a bit. For
    example, in a swap of 52 locations (cards) if the random number 50 doesn't
    appear in the first 49 generations (due to a duplicate of, say 33, and
    assuming the rest all appear once) then the next to the last card is always
    swapped with the last. In fact, I think it forces all card to be swapped
    "downward" only if their number doesn't come up before they are reached. Or
    something.
    I think I prefer swapping each location with a candidate location of the
    entire group for each swap.
    This is the way the shuffle algorithm in Java is coded, and I was just
    asking if anyone here knew the source for std::shuffle in C++. 

    -- 
Gary
  • Next message: Spacen Jasset: "Re: Random numbers with no duplicates"

    Relevant Pages

    • Re: Swap two selections
      ... The following will swap the first and the last selected words ... Dim A As String, B As String, i As Long ... How would I identify the first selection ...
      (microsoft.public.word.vba.beginners)
    • Re: Swap two selections
      ... > As long as the selection includes the space after the third word, ... > following will swap the first and third words: ... > Dim A As String, B As String, C As String ... How would I identify the first selection ...
      (microsoft.public.word.vba.beginners)
    • Re: Gimp Question
      ... >>can I 'select' individual parts of the black foreground text and swap ... You can use Select->By Color to make a selection of the color you want ... Edit->Fill with Pattern to fill the selected area with a new color or ...
      (Fedora)
    • Re: One category disappeared
      ... set chosenCategoryName to choose from list with title "Category Selection" with prompt "Select a category to be applied to Group Members..." ... repeat until catCreated ... set creationResult to display dialog "Name for new category..." ... set chosenCategory to ...
      (microsoft.public.mac.office.entourage)
    • Re: Batch Editing Contacts
      ... No way to "batch edit", exactly, but a script can select a group of contacts ... set theList to the selection ... repeat with theC in theList ... set theID to (the ID of theC as string) ...
      (microsoft.public.mac.office.entourage)