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