MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: choose with replacement


  • To: mathgroup@smc.vnet.net
  • Subject: [mg10964] Re: choose with replacement
  • From: Daniel Lichtblau <danl@wolfram.com>
  • Date: Sat, 14 Feb 1998 00:53:38 -0500
  • Organization: Wolfram Research, Inc.
  • References: <6bam9i$c7l@smc.vnet.net>

Daniel Sanders wrote:
> 
> Hi,
> 
> I'm new to Mathematica programming, and I'm a bit stumped to find the
> code for the following maybe someone has a suggestion.
> 
> Simply put, I want to make a new list from an existing finite list by
> randomly choosing an element from list_1 to be included in list_2.
> List_1 would loose that element, and the random number generator would
> be reduced to correspond to the new length of the old list_1.  This
> process would continue untill list_1 has no elements, and list_2 has
> all the elements of list_1 reordered.
> 
> I have a feeling that this is not hard to do, but I can't seem to get it
> right.  Any suggestions?
> 
> Dan

It appears what you really have in mind is choosing without replacement
(not with). Moreover it seems you do not actually need to know the
elements chosen until the entire set is permuted. In other words, let's
say your set is a deck of cards. It seems you want a way to shuffle the
entire deck, not a way to pick individual cards at random.

Why does this distinction matter? If we want to shuffle the entire deck
in one shot, we can do this in O(n*log(n)) for a deck of size n, as
follows. I'll give just some code fragments with a length specified,
but it is easy to make this into a Module or some such. Also for
simplicity I'll assume the starting list is just a range of integers,
but it could as well be any Mathematica list.

len = 100;
lis = Range[len];
tmp = Sort[Transpose[{Table[Random[], {len}], lis}]]; shuffledlis =
Last[Transpose[tmp]]

In effect we pick a bunch of random reals, associate each with a list
element (that is, form ordered pairs), and sort the mess. Sort will not
look at the second element except in case of a tie for the first
elements, so this is just fine. There is a minor subtlety here in that
we could in principle have a collision if we picked the same real value
twice. A birthday-paradox type of computation shows that, for a list of
10^6 elements, the probability of this happening is still below one in
eight thousand (I guess you need to know that a machine real between 0
and 1 has 53 bits to be chosen at random). If you plan to shuffle a
million-card deck, and cannot risk the minor diminution of randomness
associated with such a collision, then a work around would be to choose
at random from a larger set.

If instead you want to deal out a few hands of stud poker, hence need to
know the cards as they are dealt, then you really do need to deplete
one list as you grow the other (incorrect grammar there, I know).
Again, I'll just give a quick-and-dirty example below.

shuffledlis = {}
tmplis = lis;
For[j=len, j>0, j--,
	index = Random[Integer, {1,j}];
	shuffledlis = {tmplis[[index]], shuffledlis};
	tmplis = Drop[tmplis, {index}];
	]
Flatten[shuffledlis]

The adjective "quick" applies to the coding, but not the run time. Each
Drop[] statement is O(n), hence the loop is O(n^2) in complexity. This
is bad if your initial list is large. Possibly I will show how one
might obtain better complexity in a week or so (if no better method
show up first).


Daniel Lichtblau
Wolfram Research



  • Prev by Date: Re: Convolution
  • Next by Date: Re: Dead keys in Mathematica for Linux
  • Prev by thread: RE: choose with replacement
  • Next by thread: How to change the argument of a function?