# Determining And Drawing Possabilities

• Jul 24th 2009, 11:38 AM
GreenLED
Determining And Drawing Possabilities
I already understand how to calculate the possibilities of a combination lock. For example, if you have a combination lock with 4 numbers and each has 0-9 you would use 10 (the number of possibilities you have available on one "wheel") ^ (to the power) of 4 (being the number of numbers on the combination lock). Thus, you have 10,000 possibilities.

Here's is the problem. What is the manual way to do this on paper? I have for my example 3 places on my combination lock so-to-speak EACH number has 4 numbers 1-4. So, ...

111

What would be a good way to write each of these possibilities down?

I cannot seem to come up with a good way to do this. Each time I try, I get caught because I cannot come up with a standard way to do this.

Here's what I've go so far ...

111
112
113
114

121
122
123
124

There's not method to my maddness though ... what order should I go through in order to write down all the possibilities?
• Jul 24th 2009, 01:57 PM
HallsofIvy
The reason why it is nice to have a formula for this is that your picture is going to be huge!

Step 1: Get a really large piece of paper.

Step 2: Write the numbers 0, 1, 2, ..., 9 equally spaced along the left edge of that paper. From 0, draw 10 short lines connecting to the number 0, 1, 2, ..., 9 written again. From 1, draw 10 more short lines connecting to more copies of 0, 1, 2, 3, ..., 9. Once you have finished that you will have the numbers 0, 1, 2, 3, ..., 9 written 10 times slightly to the right of your first list (a total of 100 numbers in your second list).

From each of those, draw a straight line from each of those to a third list. There will be 1000 numbers in that list.

From each of those 1000 numbers, draw 10 lines to copies of 0, 1, 2, ..., 9 in a fourth list. There will be 10000 numbers in that fourth list. Like I said, you will need a really long sheet of paper to do that! Believe me, using \$\displaystyle 10^4\$ is far easier than drawing a chart like that and counting! That's why we have that formula.

If you want a list rather than a "tree" do this: start with "0000" (NOT "1111") and change one column at a time:
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014

etc.
Of course, that is exactly the same as listing all integers from 0 to 9999.
• Jul 24th 2009, 02:22 PM
GreenLED
Hmmm. I think your getting somewhere, but not quite what I have in mind. Here's my final goal. I am trying to create a script which will take some characters (a-z) in each slot and find out how many possibilities there are and print these. I tried to first simplify it by using numbers, but I think it's confusing people rather then helping because in the number sets you drew they sigify a count up. These characters can be IN any order. Let me give you a simple exacple. Let's say that the only two letters in the alphabet were a and b. Let's then assume we have 3 slots to work with.

[a][a][a]

Thus the question here is how many possabilities do we have with this situation. THe answer is simple . . .8. Three slots with 2 possabilities in each slot will give you eight sets. However, I need to somehow translate this into a method in which I can tell my script that I am writing to go through and find all the possible cominations. The script I"m writing has to have some method in which it will determine every single possible comination. Once I have overcome this hurdle then I have to increment the size of the slots. In other words, I would begin with say 1 slot like this...

[a] -- so this would have 26 possible answers --- a threough z.

But, the tricky part is to develop a method so that it will no perfectly identify all the combinations without fail. The combinations do NOT have to be dictionary words.

Hopefully, you understand my request here. To be simple though I think we need to stick with the above example, then the rest will take care of itself. So the example I'd like to work off of is this ...

[a][a][a]

There are eight possibilities here. However, There needs to be a method of going through and checking this. Once I have this down, I will test with 3 characters --- say a, b and c to ensure that it will catch every combination that we have available to us. Do you understand my request better now?
• Jul 24th 2009, 03:51 PM
yeongil
Quote:

Originally Posted by GreenLED
Let's say that the only two letters in the alphabet were a and b. Let's then assume we have 3 slots to work with.

[a][a][a]

Thus the question here is how many possabilities do we have with this situation. THe answer is simple . . .8. Three slots with 2 possabilities in each slot will give you eight sets. However, I need to somehow translate this into a method in which I can tell my script that I am writing to go through and find all the possible cominations. The script I"m writing has to have some method in which it will determine every single possible comination.

In computer science, I remember using multi-dimensional arrays and nested loops in order to something similar to what you're describing. Suppose you have an array or things declared
stuff[3][3][3]
(I'm going back to numbers FTM. Note that from here on out that I'm using pseudocode.)
This is a 3x3x3 array that would contain all possible combinations for three-letter "words" with using letters a, b, and c.

To do something on each element of this array, use a nested loop. Assign 3 variables that will do the counting for you in the loop (x, y, z). So:
Code:

for (x goes from 1 to 3)
{
for (y goes from 1 to 3)
{
for (z goes from 1 to 3)
{
do something to stuff[x][y][z]...
}
}
}

I'll say it again: the above is not meant to be proper code for any particular programming language.

I don't know if this is what you're looking for. To be honest, your 2nd post in this thread made things less clear to me than your 1st one, sorry. :confused:

01
• Jul 24th 2009, 04:02 PM
GreenLED
:D, You're getting so close!! Here's the code I currently have. This code IS working. Let me put the idea into VERY simple language. Take an array of all possible characters (chars) and print out ALL possible combinations from 1 slot to 64 slots. Slots simply refers to the length of the "word"

Example: How many possibilites do you have if you have word made of of one character, how many possibiliities do you have if you have a word made up of two characters, how many possibilities do you have if you have a word of made up of three characters, etc. etc. etc. -- keeping in mind that words are not really "words"! just the characters themselves.

I think you're sudo code is better designed then mine is, but I can't quite picture how I would implement your code. Here's mine...

Code:

<?PHP
// Variables
\$chars = array("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z");
\$round = 0;

// Output
FOREACH (\$chars as \$char)
{ ECHO "<li>" . \$char; }

?>

Here's the live result displayed here: http://handysite.org/stage/remote/

I really hope this is not confusing you. I'm trying to jump over this mental hurdle myself. I keep tripping over it and I want to understand how to do this.
• Jul 24th 2009, 04:20 PM
GreenLED
Well, you can ignore that URL I posted. It now contains your code in a working PHP form. Unbelievable, this works! It's been some time since I've worked in PHP. I've started to loose it. I can't mentally walk through that nested loop and understand exactly how it's working, but it is! I'm not happy that I can't grasp what's going on. In fact, I have no intention of moving on until I do. Walk me through what's going on here in those nested loops. Here's the updated code for that URL I posted.

Code:

<?PHP
// Variables
\$chars = array(a, b);

// Output
FOREACH (\$chars as \$x)
{
FOREACH (\$chars as \$y)
{
FOREACH (\$chars as \$z)
{
ECHO "<li>" . \$x . " " . \$y . " " . \$z;
}
}
}

?>

• Jul 24th 2009, 04:52 PM
GreenLED
I know this is my third post in reply, but this is really messing with my mind. I don't understand how this is being processed in real-time. If you look at [http://handysite.org/stage/remote/] you'll see the result of the last code I posted. It's working correctly (least as far as I know) but I don't understand how the loops are running and when they are terminating and what is happening after one terminates and how you could have 2 variables (like when you have a b b) the same --. I need something like ---

Loop z says "I still have letter b in my array" then it terminates and loop y ... etc. Something like this would be helpful. This is truly stumping me. It should be so basic too, lol. Aggrevating! (Headbang)
• Jul 24th 2009, 04:57 PM
yeongil
It's probably harder to visualize because we only have a & b to play with. Using numbers again, try imagining a 3-digit odometer. Here's pseudocode that would allow you to print all the possible numbers:

Code:

for (x goes from 0 to 9)
{
for (y goes from 0 to 9)
{
for (z goes from 0 to 9)
{
print (x y z)
}
}
}

The innermost loop [for (z...)] corresponds to the 3rd digit, the mid-level loop [for (y...)] corresponds to the 2nd digit, and the outermost loop [for (x...)] corresponds to the 1st digit.

The more "slots" you need, the more levels of nested loops you need. Say that you want to print all \$\displaystyle 26^5\$ possible 5-letter "words" (why would anyone want to do that? (Rofl)) Here's some pseudocode to do that:
Code:

for (v goes from "a" to "z")
{
for (w goes from "a" to "z")
{
for (x goes from "a" to "z")
{
for (y goes from "a" to "z")
{
for (z goes from "a" to "z")
{
print (v w x y z)
}
}
}
}
}

There may be a more efficient way to do this, but it works. HTH.

01
• Jul 24th 2009, 06:43 PM
GreenLED
After a vigorous metnal exercise walking through the loops parse by parse, I've got some good strides in the right direction. You really have to think it through though. I never enjoy writing code unless I understand exactly what is being exectued. Anyhow, I will have to create some worksheets or something to supplement this thinking for myself. Thank you for the logic! Hopefully I can end this thread now, but you never know :D.
• Jul 25th 2009, 01:41 PM
awkward
Quote:

Originally Posted by GreenLED
After a vigorous metnal exercise walking through the loops parse by parse, I've got some good strides in the right direction. You really have to think it through though. I never enjoy writing code unless I understand exactly what is being exectued. Anyhow, I will have to create some worksheets or something to supplement this thinking for myself. Thank you for the logic! Hopefully I can end this thread now, but you never know :D.

If I may restate the problem in terms of numbers rather than symbols, let's suppose you want to generate all the possible n-tuples where each element is taken from the set {0, 1, 2, ..., r-1}.

This is easy, provided you know how to convert numbers to a specified base (radix). Just count from 0 to r^n and print each number in radix r.

Pseudocode:

Code:

for i = 0 to r^n
Convert i to radix r and print
loop