picking random items out of a list only once

Question

I'm trying to create a function that randomly returns a value from a list but remembers the values that have been given before. At the end when the list is empty it should return an empty list. Basically like emptying a bucket full of eggs one at a time.

Suppose I have two lists:

data1 = Range[10];
data2 = Range[20];

Asume function

getRandomItem[l_List]

I tried playing with downvalues but that doesn't work.

Calling getRandomItem[data1] two times would give (e.g)

{1} and {3}

Calling getRandomItem[data2] two times would give (e.g)

{15} and {20}

At the end as stated before when all items are chosen both getRandomItem[data1] and getRandomItem[data2] should return {}.

I would like to do that without declaring data1 and data2 as global variables nor do I which to change/alter them. So, basically I presume the function itself should remember which data has been given to it and where it had left the previous time.

Answer 1

How about making a closure? A closure is a function with an internal state.

makeDrippingBucket[list_] := 
 Module[{bucket = list}, 
  If[bucket === {}, {}, 
    With[{item = RandomChoice[bucket]}, 
     bucket = DeleteCases[bucket, item]; {item}]] &]

Then use this to make a "bucket", like this:

bucket = makeDrippingBucket[{1,2,3,4,5}]

This object has an internal state that changes every time you call it. Every time you call bucket[], it will give you a new number, until it gets empty.

bucket[]

(* ==> {3} *)

---

EDIT

The same thing, using @Eli's solution of pre-randomizing the list:

makeDrippingBucket[list_] := 
 Module[{bucket = RandomSample[list]}, 
  If[bucket === {}, {}, 
    With[{item = Last[bucket]}, bucket = Most[bucket]; {item}]] &]

Answer 2

One thing you can do is

data1Random = RandomSample[data1];
data2Random = RandomSample[data2];

This gives you a random ordering of the initial dataset, without any repetitions. Then you can just pick them out from that list one by one in order.

Edit Thinking along the lines of Szabolcs's answer, I've come up with a possible approach to the "drops in a bucket" element of the question. If you use:

data1Random = {RandomSample[data1], Length[data1]}
getRandomItem[data_] := If[data[[2]] > 0, 
 {data[[1, data[[2]]]], {data[[1]], data[[2]] - 1}}, 
 {{}, {data[[1]], 0}}]

you can keep track of how many things you've used already. Here's how you'd use this:

{drop, data1Random} = getRandomItem[data1Random]

where drop is the random value, and you re-assign data1Random's counter each time. A quick benchmark:

data1 = Range[100000];
Do[{drop, data1Random} = getRandomItem[data1Random], {Length@data1}]; // AbsoluteTiming

(* ==> 0.9531128 *)

compared to Szabolcs's second answer

bucket = makeDrippingBucket[data1]
Do[bucket[], {Length@data1}]; // AbsoluteTiming

(* ==> 12.9529592 *)

This is much slower than celtschk's solution

bucket = makeDrippingBucket[data1]
Do[bucket[], {Length@data1}]; // AbsoluteTiming

(* ==> 0.3593727 *)

---

Further Edit Here's a way which does the left-hand-side reassignment within the function:

SetAttributes[getRandomItem, HoldAll]
getRandomItem[data_]:=({drop,data}=If[data[[2]]>0,
 {data[[1,data[[2]]]],{data[[1]],data[[2]]-1}},{{},{data[[1]],0}}];
 drop)

Then, for usage:

data1Random = {RandomSample[data1], Length[data1]};
getRandomItem2[data1Random]

only outputs the random number, and can be re-evaluated until it's used them all up, and it outputs {}. This is actually faster than the previous version (same benchmark runs in 0.7657132) and has a simpler usage.

Answer 3

Here's my solution, based on Szabolcs' solution which used Eli Lansey's solution of pre-randomizing. Basically I've replaced the list manipulation with index calculation.

makeDrippingBucket[list_] :=
  Module[{bucket = RandomSample[list],
          index = 0,
          len = Length[list]},
    If[index == len, {}, bucket[[++index]]]&]

Of the solutions Eli benchmarked, up to now it seems to be the fastest (see the corresponding comment on this post).

Answer 4

Here's a more imperative solution, still based on closing over a mutable symbol, if for some reason you don't want to pre-randomize the list. I'm not sure I'd recommend it, but it's an alternative approach that might be interesting:

Pillsy`DrippingBucket[list_List] := 
 Module[{array = list, fill = Length@list},
  Function[{},
   If[fill == 0, (* bucket is empty! *) 
    $Failed,
    With[{k = RandomInteger[{1, fill}]},
     array[[{k, fill}]] = array[[{fill, k}]];
     array[[fill--]]]]]]

Its speed is comparable to Eli Lansey's approach for a 100000 element list if you're going to drip away the whole bucket; the advantage comes about if you're only using a small number of drips, because you only have to pay for the ones you use. Still, for most applications I'd just use RandomSample.

Answer 5

Here's a solution using Internal`Bag et al. It also does not involve the computational cost of pre-randomizing your list if you aren't going to empty your bucket fully.

Begin["Lou`"];
bag; data;
CreateBucket[list_List] := (bag = Internal`Bag[]; data = list;)
EmptyBucket[] := If[data === {}, {}, 
    ((Internal`StuffBag[bag, data[[#]]];
      data = Drop[data, {#}];)&@RandomInteger[{1, Length[data]}];
      Internal`BagPart[bag, -1])
];

ListSoFar[] := Internal`BagPart[bag, All];
End[];

You can now use it in the following manner:

AppendTo[$ContextPath, "Lou`"];
CreateBucket[{1, 2, 3, 4, 5}]; (* create a bucket of data *)
EmptyBucket[]                  (* empty your bucket one by one *)
(* Out[1]= {5} *)

EmptyBucket[]
(* Out[2]= {1} *)

ListSoFar[]                    (* see what has been output so far *)
(* Out[3]= {5, 1} *)

When you finally empty your bucket, it returns {}.