(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 3.0, MathReader 3.0, or any compatible application. The data for the notebook starts with the line of stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 18229, 533]*) (*NotebookOutlinePosition[ 19989, 590]*) (* CellTagsIndexPosition[ 19919, 584]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["Sampling Without Replacement from Multisets", "Title", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ by Paraskevas V. Lekeas National Technical University of Athens Algorithms and Logic Lab plekeas@mail.ntua.gr Thessalias 4, 15772, Zografou, Greece 12 July 2004 \ \>", "Subsubtitle", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Sampling without replacement from multisets", "Section"], Cell["\<\ The following are for sampling a list without replacement. When we say a \ list, in fact we mean a multiset. This means that this list may have multiple \ elements of the same kind, which have to be treated as different when \ sampling. \ \>", "ExampleText", CellTags->"Nest"], Cell[TextData[{ "Here we define a function called ", StyleBox["rnd", FontWeight->"Bold"], " which gets as input the list we want to sample, computes its Length and \ picks a random integer between 1 and Length." }], "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(rnd[ll_] := Random[Integer, {1, Length[ll]}]\)], "Input"], Cell[TextData[{ "Here we define another function, ", StyleBox["takelement", FontWeight->"Bold"], ",which gets as input the list we want to sample and extracts the ith \ element of the list where i equals to the random number drawn previously by ", StyleBox["rnd", FontWeight->"Bold"], "." }], "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(takelement[ll_] := \(t = Take[l, {aa = rnd[l], aa}]\)\)], "Input"], Cell["\<\ Here we define an empty list where we should put the sampled elements.\ \>", "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(emptylist := {}\)], "Input"], Cell["\<\ Here we define a function that drops the sampled element from list l \ (sampling without replacement).\ \>", "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(dropelement[k_] := \(l = Drop[l, {aa, aa}]\)\)], "Input"], Cell["\<\ Here we define a function which represents the final sample. By calling this \ function we just append in each iteration the sampled element.\ \>", "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(sample := Flatten[AppendTo[emptylist, t]]\)], "Input"], Cell[TextData[{ "Here all the functions are placed together as a procedure called ", StyleBox["gyros", FontWeight->"Bold"], "." }], "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(gyros[n_] := \((takelement[l_]; dropelement[l_]; sample)\)\)], "Input"], Cell[TextData[{ "At last we Nest procedure gyros by giving as input the list and the sample \ size we want to draw. Be careful that we have to name our sample only with \ the letter ", StyleBox["l", FontWeight->"Bold"], ", and of course we have to have define that list first!" }], "ExampleText", CellTags->"Nest"] }, Closed]], Cell[CellGroupData[{ Cell["Instructions on how to use", "Section"], Cell[TextData[{ "Load in memory (Shift+Enter) all the previous functions.\nLoad the list \ from where you will get the sample. Name that list with letter ", StyleBox["l", FontWeight->"Bold"], ".\nDecide the size of your sample. \nBe careful, when you want to draw \ another sample you have to reevaluate function ", StyleBox["emptylist", FontWeight->"Bold"], " in order to begin with an empty sample list, and also reevaluate the \ starting list in order to draw samples from the same starting list." }], "ExampleText", CellTags->"Nest"] }, Closed]], Cell[CellGroupData[{ Cell["Example", "Section"], Cell["Here is a list (multiset) of Length 99:", "ExampleText", CellTags->"Nest"], Cell[BoxData[ RowBox[{"l", ":=", RowBox[{"{", RowBox[{ StyleBox["10.5000000000000004`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.3600000000000003`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.5700000000000011`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["24.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.5700000000000011`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["16.0700000000000002`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.2699999999999995`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["17.4699999999999988`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["15.3699999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8900000000000005`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.4700000000000015`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["31.4699999999999979`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["19.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.2699999999999995`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["29.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["16.9499999999999984`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["16.0700000000000002`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8900000000000005`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.9700000000000002`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.2699999999999995`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.2699999999999995`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.3600000000000003`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["9.56000000000000049`", StyleBoxAutoDelete->True, PrintPrecision->3], ",", StyleBox["12.5700000000000011`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["17.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.9700000000000002`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["17.4699999999999988`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8699999999999983`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["19.`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.2699999999999995`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["9.56000000000000049`", StyleBoxAutoDelete->True, PrintPrecision->3], ",", StyleBox["30.6700000000000017`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.9700000000000002`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["29.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.2699999999999995`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8900000000000005`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8900000000000005`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["32.0000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.3600000000000003`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["32.0000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.5700000000000011`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["24.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["34.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["32.0000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["72.0000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.9500000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8699999999999983`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["19.25`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["44.0000000000000035`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["29.`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["16.0700000000000002`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["21.0000000000000008`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["19.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["14.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["37.799999999999998`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["31.0000000000000008`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["22.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["18.5`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["24.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.3600000000000003`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["4.95000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->3], ",", StyleBox["16.9499999999999984`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["21.9499999999999984`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["25.6400000000000005`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.8699999999999983`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.5700000000000011`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["52.0000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["20.9499999999999975`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.4700000000000015`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.1999999999999988`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["44.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["14.5`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["10.6999999999999984`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["23.5499999999999998`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["14.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["29.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["21.3600000000000012`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["27.5`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["5.95000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->3], ",", StyleBox["20.`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["18.75`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["26.4999999999999991`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.1899999999999999`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["14.5`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["35.`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["11.1699999999999999`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["13.9999999999999991`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["18.6000000000000014`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["42.4600000000000044`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["94.9500000000000099`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["20.9499999999999975`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["79.950000000000001`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["12.9499999999999992`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["55.`", StyleBoxAutoDelete->True, PrintPrecision->4], ",", StyleBox["7.95000000000000017`", StyleBoxAutoDelete->True, PrintPrecision->3], ",", StyleBox["27.1999999999999975`", StyleBoxAutoDelete->True, PrintPrecision->4]}], "}"}]}]], "Input"], Cell["Here we ensure that we start from the empty list:", "ExampleText", CellTags->"Nest"], Cell[BoxData[ \(emptylist := {}\)], "Input"], Cell["\<\ Here we draw without replacement a sample s1 of size 10 from list l:\ \>", "ExampleText", CellTags->"Nest"], Cell[CellGroupData[{ Cell[BoxData[ \(s1 = Nest[gyros[#]&, l, 10]\)], "Input"], Cell[BoxData[ \({10.3600000000000003`, 24.950000000000001`, 13.9700000000000002`, 12.9499999999999992`, 11.8699999999999983`, 15.3699999999999992`, 11.1699999999999999`, 19.9499999999999992`, 10.5000000000000004`, 11.8900000000000005`}\)], "Output"] }, Open ]], Cell["\<\ Here we verify that the size of the remaining list plus the size of s1 equals \ to the size of the list before the sampling:\ \>", "ExampleText", CellTags->"Nest"], Cell[CellGroupData[{ Cell[BoxData[ \(Length[l] + Length[s1]\)], "Input"], Cell[BoxData[ \(99\)], "Output"] }, Open ]], Cell["\<\ Since l has been changed (we erased from it all the drawn elements) If we \ would like to draw another sample from l, we have to reevaluate it, \ reevaluate the emptylist and go on.\ \>", "ExampleText", CellTags->"Nest"] }, Closed]] }, Closed]] }, FrontEndVersion->"Microsoft Windows 3.0", ScreenRectangle->{{0, 800}, {0, 535}}, WindowSize->{766, 443}, WindowMargins->{{2, Automatic}, {Automatic, 5}}, PrintingCopies->1, PrintingPageRange->{Automatic, Automatic} ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{ "Nest"->{ Cell[2174, 74, 288, 6, 42, "ExampleText", CellTags->"Nest"], Cell[2465, 82, 260, 7, 42, "ExampleText", CellTags->"Nest"], Cell[2808, 94, 348, 11, 42, "ExampleText", CellTags->"Nest"], Cell[3248, 110, 121, 3, 25, "ExampleText", CellTags->"Nest"], Cell[3423, 118, 153, 4, 25, "ExampleText", CellTags->"Nest"], Cell[3659, 127, 192, 4, 25, "ExampleText", CellTags->"Nest"], Cell[3931, 136, 176, 6, 25, "ExampleText", CellTags->"Nest"], Cell[4204, 147, 326, 8, 42, "ExampleText", CellTags->"Nest"], Cell[4615, 162, 557, 12, 93, "ExampleText", CellTags->"Nest"], Cell[5238, 181, 82, 1, 25, "ExampleText", CellTags->"Nest"], Cell[17018, 486, 92, 1, 25, "ExampleText", CellTags->"Nest"], Cell[17164, 492, 119, 3, 25, "ExampleText", CellTags->"Nest"], Cell[17660, 509, 175, 4, 25, "ExampleText", CellTags->"Nest"], Cell[17969, 524, 232, 5, 42, "ExampleText", CellTags->"Nest"]} } *) (*CellTagsIndex CellTagsIndex->{ {"Nest", 18884, 551} } *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1731, 51, 108, 2, 150, "Title"], Cell[1842, 55, 242, 13, 210, "Subsubtitle"], Cell[CellGroupData[{ Cell[2109, 72, 62, 0, 53, "Section"], Cell[2174, 74, 288, 6, 42, "ExampleText", CellTags->"Nest"], Cell[2465, 82, 260, 7, 42, "ExampleText", CellTags->"Nest"], Cell[2728, 91, 77, 1, 29, "Input"], Cell[2808, 94, 348, 11, 42, "ExampleText", CellTags->"Nest"], Cell[3159, 107, 86, 1, 29, "Input"], Cell[3248, 110, 121, 3, 25, "ExampleText", CellTags->"Nest"], Cell[3372, 115, 48, 1, 29, "Input"], Cell[3423, 118, 153, 4, 25, "ExampleText", CellTags->"Nest"], Cell[3579, 124, 77, 1, 29, "Input"], Cell[3659, 127, 192, 4, 25, "ExampleText", CellTags->"Nest"], Cell[3854, 133, 74, 1, 29, "Input"], Cell[3931, 136, 176, 6, 25, "ExampleText", CellTags->"Nest"], Cell[4110, 144, 91, 1, 29, "Input"], Cell[4204, 147, 326, 8, 42, "ExampleText", CellTags->"Nest"] }, Closed]], Cell[CellGroupData[{ Cell[4567, 160, 45, 0, 33, "Section"], Cell[4615, 162, 557, 12, 93, "ExampleText", CellTags->"Nest"] }, Closed]], Cell[CellGroupData[{ Cell[5209, 179, 26, 0, 33, "Section"], Cell[5238, 181, 82, 1, 25, "ExampleText", CellTags->"Nest"], Cell[5323, 184, 11692, 300, 428, "Input"], Cell[17018, 486, 92, 1, 25, "ExampleText", CellTags->"Nest"], Cell[17113, 489, 48, 1, 29, "Input"], Cell[17164, 492, 119, 3, 25, "ExampleText", CellTags->"Nest"], Cell[CellGroupData[{ Cell[17308, 499, 60, 1, 29, "Input"], Cell[17371, 502, 274, 4, 29, "Output"] }, Open ]], Cell[17660, 509, 175, 4, 25, "ExampleText", CellTags->"Nest"], Cell[CellGroupData[{ Cell[17860, 517, 55, 1, 29, "Input"], Cell[17918, 520, 36, 1, 29, "Output"] }, Open ]], Cell[17969, 524, 232, 5, 42, "ExampleText", CellTags->"Nest"] }, Closed]] }, Closed]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)