NetLogo Models Library:
Sample Models/Mathematics/Probability/ProbLab/Unverified

Note: This model is unverified. It has not yet been tested and polished as thoroughly as our other models.

(back to the library)

Random Combinations and Permutations

If you download the NetLogo application, this model is included. You can also Try running it in NetLogo Web

WHAT IS IT?

"Random Combinations and Permutations" is a virtual laboratory for learning about probability, and specifically about combinations and permutations, sample space, samples, favored events, and outcome distributions. The model invites you to pick a secret combination and then see how long it takes the computer to find it. The computer discovers your secret combination by just guessing blindly until it happens to guess correctly.

The user defines the size of the combinatorial sample space and then picks a particular combination from this sample space. Next, at the user's command, the model generates random combinations selected out of the sample space. The model both matches each random combination against the user's secret combination and checks whether the random combination is a permutation of the original combination. Results of these two checks accumulate and are shown both in real-time, in monitors, and at the completion of samples, in the plot (the user can choose whether to only observe one of these measures or both of them).

This model is a part of the ProbLab curriculum. The ProbLab Curriculum is currently under development at the CCL. For more information about the ProbLab Curriculum please refer to http://ccl.northwestern.edu/curriculum/ProbLab/.

PEDAGOGICAL NOTE

In this model, you will: - Create a sample space by choosing how many objects you will be experimenting with and how many different appearances each of these can have, e.g., how many dice you will be rolling and how many different faces these dice have. For example, you can work with 3 dice that each has 4 faces. (Alternatively, you can work with colors instead of dice faces.) - Select from this sample space a particular combination that will be the favored event out of all outcomes of the experiment. For instance, you may create the dice combination "4, 1, 3." - Distinguish between combinations and permutations and understand the implications of this distinction to the interpretation of the experimental outcomes. For instance, you decide to accept as a favored event ('success' or 'hit') only the original order of you combination, "4, 1, 3." However, you may decide that the order is not important and accept - Set the size of the sample, for instance 1,000 outcomes. That is, the experiment will rapidly generate one outcome after another, and every 1,000 outcomes it will show in the plot how many of these were the favored event. So the endless stream of outcomes is parsed into linked sections of equal length - Run a simulated experiment in empirical probability. The program will choose randomly from the sample space that you have set, creating combinations that you will see in the view. The program monitors for outcomes that are your favored event. - Analyze distribution plots and monitors to understand relations between the sample space you created and the experimental outcomes. For instance, 3 dice each with 4 faces create a sample space of 4*4*4 = 64. Whatever your favored event was, for instance, "4, 1, 3," it will occur once in every 64 rolls, on average. So if your sample was of size 1,000 rolls, it should occur every 1,000/64 = 15.625 rolls, on average. - Understand more deeply the sample space you initially created, in order to calculate and anticipate sample outcomes. That is, why do 3 dice each with 4 faces create a sample space of 4*4*4? Why not, for instance, 3*3*3*3? Or just 3*4? 3+4?... - Distinguish between combinations and permutations and understand the implications of this distinction to the interpretation of the experimental outcomes. You will see that whether you are looking just for the original permutations of your combination ("4, 1, 3") or for any permutation ("4, 1, 3," "4, 3, 1," 3, 4, 1" etc.), the distributions of favored-events-per-sample will be different. These distributions will differ in their central-tendency indices: both in their mean and in their 'shape' (range and variance). - Master the model by integrating all the above in understanding the ratio between the means of the two distributions

HOW TO USE IT

Buttons SETUP -- initializes variables and assigns as objects in the experiment as many squares as you have set with the WIDTH and HEIGHT sliders. CREATE COMBI - allows you to use the mouse to click on squares so as to select the dice/colors for your combination of choice. Clicking repeatedly on the same square loops the die-faces / colors through an option cycle that has as many options as the value you set for the HOW-MANY-CHOICES slider. For instance, if the slider is set to "3" and you are working with colors, clicking repeatedly on a single square will give the colors green, blue, pink, green, blue, pink, green, etc. HIDE/REVEAL COMBI -- toggles between hiding and revealing the secret combination. This function is useful when you pose a riddle to a friend and you do not want them to know what your chosen combination is. SEARCH COMBI - activates the random search. The program generates random dice-faces / colors and matches the outcome against the combination you had created.

Sliders: #CHOICES - sets the number of dice-face / colors you wish to include in the sample space. You do not have to use for your combination as many different faces / colors as you set this slider to. For instance, you might want to set this slider to 5 but then only use two of these options. WIDTH & HEIGHT -- sliders for setting the values of the width and height dimensions, respectively, of the combination you are creating. SAMPLE SIZE -- sets the number of program-generated guesses per sample. At the end of each sample, the plot is updated as well as the RATIO monitor (see below)

Choices: Analysis-Type -- - "Permutations" - That is, order does not matter, so '1 2 3' is considered the same as its permutation '3 2 1' (it is registered as a favored event) - "Combination" - That is, order matters, so '1 2 3' is not accepted as the same as its permutation '3 2 1' (it is not registered as a favored event) - "both" - That is, the experiment will analyze outcomes from both the 'Permutations' and 'Combination' perspectives, and each will be represented in the plot.

Switches: SINGLE-SUCCESS? -- If "On," the program will stop running after it has guessed the combination correctly once. If "Off," the program will continue running indefinitely. DICE? - toggles between two options: - "On" means you will be creating and searching dice faces - "Off" means you will be creating and searching colors BARS? -- "On" gives you a histogram in the plot window; "Off" gives you a line graph.

Monitors: #SAMPLES -- shows how many samples have run up to this moment in the experiment #STEPS IN THIS SAMPLES -- shows how many guesses (or "attempts") the program has conducted in this sample, regardless of whether or not they were successful. COMBINATION -- shows how many successes (hit guesses) the program has performed in this sample according to the conditions that order matters PERMUTATIONS -- shows how many successes (hit guesses) the program has performed in this sample according to the conditions that order does not matter '#1' thru '#6' -- When you have set up your combination, these monitors will accumulate your setting according to type. For example, if you have set DICE? to "On" and the #CHOICES to 4 and you have set up the five dice faces as '4 2 3 3 2,' then - Monitor #1 will show "0," because there are no '1's in your combination, even though there could have been. - Monitor #2 will show "2" because there are two '2's in your combination. - Monitor #3 will show "2" because there are two '3's in your combination - Monitor #4 will show "1" because there is just a single '3' in your code. - Monitors #5 and #6 show "N/A" ("not available") -- telling us that there cannot be any number here, since the '5' and the '6' dice faces were not in your pool of choices. COMBI : PERMIS -- shows the ratio between the mean values of the sample outcome distributions corresponding to the conditions "combination" and "permutation," respectively. This monitor updates each time a sample has been completed.

Plot SUCCESSES PER SAMPLE DISTRIBUTION -- shows the counts of successes per sample for the conditions selected in the ANALYSIS-TYPE slider.

Follow the instructions in the "instructions" monitor window, which will lead you through the following process: - set the WIDTH and HEIGHT sliders or just use the default settings that are 1 by 3 - press SETUP - set the values of the #CHOICES slider (default is 2) - select your choice in the ANALYSIS-TYPE choice (you can change this later, too) - press CREATE COMBI. - set the DICE? switch either to "On," to work with dice, or "Off", to work with colors - click on each green square repeatedly until you are happy with your combination - optionally, press HIDE/REVEAL (you can always press this again to see your combination) - if you have set the SINGLE-SUCCESS?' switch to "On," then the search will stop the moment it has matched your original combination, according to your choice of ANALYSIS-TYPE - if you have set the SINGLE-SUCCESS?' switch to "Off," then the program will begin a new search and will generate random combinations on and on until you stop it. While it runs, monitors constantly update you on the progress of this process. A plot helps you track the accumulation of outcomes from the search in terms of your ANALYSIS-TYPE - press SEARCH COMBI

THINGS TO NOTICE

As the search procedure is running, look at the monitor #STEPS IN THIS SAMPLES. See how it is updating much faster than the monitor to its left, #SAMPLES. The number in #SAMPLES increases by 1 each time #STEPS IN THIS SAMPLES reaches the number that is set in the slider SAMPLE SIZE.

After you have setup a combination, look at the six monitors under the view. Some of them, perhaps all of them, have numbers in them. Some might have 'N/A' ('not available') in them. In any case, there are exactly as many monitors with numbers in them as the number of choices you have set up in the slider #CHOICES.

As the search procedure is running, watch the monitors COMBINATION and PERMUTATIONS. Note whether or not they are updating their values at the same pace. For most combinations that you set, PERMUTATIONS updates much faster. This is because PERMUTATIONS registers a successeach time the model hits on the set of colors / dice-faces you selected even if they appear in a different order form what you had selected.

As the search procedure is running, watch the monitor COMBI-TO-PERMI RATIO. At first, it changes rapidly, and then it changes less and less. Eventually, it seems to stabilize on some value. Why is this so?

Unless the red histogram ("permutations") covers the black histogram ("combination") entirely, you will see that the "permutations" histogram always becomes both wider and shorter than the "combinations" histogram. What does this mean? Why is this so? We say of the wider histogram that it has a greater "variance" as compared to the narrower histogram. The "permutations" histogram (red) typically stretches over a greater range of values as compared to the "combination" histogram (black).

Also, you may notice that the "permutations" and "combination" histograms cover the same area. That is because the total area of each histogram, irrespective of their location along the horizontal axis and irrespective of their shape, indicates the number of samples they represent. We know that the two histograms represent the same number of samples. Therefore, they have the same area.

THINGS TO TRY

Find a combination for which the monitors COMBINATION and PERMUTATIONS change at the same pace. What other features on the interface are unique for this combination? For instance, is the plot behaving the same as before? How is the COMBI-TO-PERMIS RATIO monitor behaving?

For different settings, we get different distances between the two histograms. Which settings are these and how do the affect the distance??

If you work with a friend, then the friend can try to set up combinations on your computer. You will need to guess what the combination is by looking at the information in the view as the program is running. What would make for a difficult combination? What would make for an easy combination? That is, are there some combinations that are harder to guess than others? Which are they?

Set the WIDTH slider at 2 and the HEIGHT slider at 1. Set the #CHOICES slider at 2. Create a combination with one green square and one blue square. Press SEARCH COMBI. Watch the plot and the COMBI-TO-PERMIS RATIO monitor. You will get a 1:2 ratio between the "combinations" and "permutation" distribution means. Now set the model again, changing only the #CHOICES slider to 3. Run the experiment. Once again, you will get a 1:2 ratio between the "combinations" and "permutation" distribution means. Has anything at all changed in your experimental results?

Create a combination and then try to figure out what the value of COMBI-TO-PERMIS RATIO will be before you run the experiment. For instance, what should the ratio be under the following settings: - #CHOICES at 4 - In your combination, two of the squares are green, one is blue, and one is pink

NETLOGO FEATURES

The model uses the same "looping" list containing the choices of colors (or dice faces) both for building and for searching for the combination. There are 6 optional colors or dice faces. These lists are created in the "initialize" procedure:

    set color-list [ green blue magenta cyan pink yellow]
    set dice-list ["one" "two" "three" "four" "five" "six"]

Once the user has set how many choices are wanted, part of this list is copied onto a new list -- either the 'color-rotation' list or the 'dice-rotation' list (see the "set- color-rotation " and "set-dice-rotation" procedures, respectively). For instance, for a HOW-MAY-CHOICES? setting of 3, the model will copy 'green blue magenta.' Later, in the search-combi procedure (actually, in the 'guess' sub-procedure), the program will randomly select an item from the color-rotation or dice-rotation lists. To create shorter lists form longer lists, we use a local variable, color-list-counter, that counts up as many choices as the user has set. For every count, an additional item from the list is copied onto the new list:

   repeat num-choices
   [
     set color-rotation lput (item color-list-counter color-list)
                             color-rotation
     set color-list-counter color-list-counter + 1
   ]

These lists are "rotating" lists because in the assign-color-or-image procedure we move along the list and when we get to its end we start over from the beginning of the list, as in a loop. For instance, a patch command in the assign-color-or-image procedure is the following:

    set pcolor item ((1 + position pcolor color-rotation) mod num-choices)
                    color-rotation

The critical code word in the above line is "mod." If we have 3 colors in the color-rotation list, then "1 + position etc." could exceed the limit of only 3 colors and be 4. But there is no 4th color in the list. "mod" works like this: '5 mod 3' is 2 because 5 has 2 more than 3. But '8 mod 3' is also 2, because 8 is 2 greater than 6, which is the greatest integer multiple of 3 that is contained in 8. Try typing "show 4 mod 3" in the command center, then try "show 7 mod 3" etc.

EXTENDING THE MODEL

Create a plot that tracks, over time, the value that is shown in the RATIO monitor.

It should be interesting to track how long it takes the model from one success to another. Add code, monitors, and a plot to do so.

Following is an extension idea for applying this model towards thinking about search algorithms. Currently, the program guesses combinations randomly. This could be improved upon so that the program finds the combination in less guesses. For instance, the moment one of the squares has the correct color or dice face, the program would continue guessing only for the other squares. Another idea might be to create a systematic search procedure.

CREDITS AND REFERENCES

This model is a part of the ProbLab curriculum. The ProbLab Curriculum is currently under development at Northwestern's Center for Connected Learning and Computer-Based Modeling. . For more information about the ProbLab Curriculum please refer to http://ccl.northwestern.edu/curriculum/ProbLab/.

HOW TO CITE

If you mention this model or the NetLogo software in a publication, we ask that you include the citations below.

For the model itself:

• Abrahamson, D. and Wilensky, U. (2004). NetLogo Random Combinations and Permutations model. http://ccl.northwestern.edu/netlogo/models/RandomCombinationsandPermutations. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

Please cite the NetLogo software as:

• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

Copyright 2004 Uri Wilensky.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

This model was created as part of the projects: PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN CLASSROOMS and/or INTEGRATED SIMULATION AND MODELING ENVIRONMENT. The project gratefully acknowledges the support of the National Science Foundation (REPP & ROLE programs) -- grant numbers REC #9814682 and REC-0126227.

(back to the NetLogo Models Library)