Algorithms


     In the article that appeared in Scientific American, November 1973. all rules were established before the pattern was started. In fact, rules were grouped together by category, called “field”: one path taken, two paths, etc. The selection of rules was made by taking the groups in combination. It was felt that this approach is very restrictive.

     We can start by calculating the number of permutations (patterns) that are possible. At right is a table showing the number of choices available for each of the rules. Rule zero, for example, describes the case where no previous paths are taken. They are all available – therefore we have five choices.

     If we were to establish a set of rules before observing the resulting pattern there would be no way of knowing what changes will effect the outcome. We must then prudently assume that any rule change is relevant. According to the choices available for each rule there are 309,586,821,120 permutations! In practice, however, only a small number of rules are used in a pattern – up to seven. The rest may or may not have been defined with no consequence. The number of unique patterns is thus much less than the theoretical maximum.

     The number of unique patterns is only several hundred. Some patterns which appear to be identical are constructed differently. Unfortunately such differences can not be appreciated by looking at the final result.

… to be continued …
  
RulePaths Taken
5 4 2 1 0
Choices
0 0 0 0 0 0 5
1 0 0 0 0 1 4
2 0 0 0 1 0 4
3 0 0 0 1 1 3
4 0 0 1 0 0 4
5 0 0 1 0 1 3
6 0 0 1 1 0 3
7 0 0 1 1 1 2
8 0 1 0 0 0 4
9 0 1 0 0 1 3
10 0 1 0 1 0 3
11 0 1 0 1 1 2
12 0 1 1 0 0 3
13 0 1 1 0 1 2
14 0 1 1 1 0 2
*15 0 1 1 1 1 1
16 1 0 0 0 0 4
17 1 0 0 0 1 3
18 1 0 0 1 0 3
19 1 0 0 1 1 2
20 1 0 1 0 0 3
21 1 0 1 0 1 2
22 1 0 1 1 0 2
*23 1 0 1 1 1 1
24 1 1 0 0 0 3
25 1 1 0 0 1 2
26 1 1 0 1 0 2
*27 1 1 0 1 1 1
28 1 1 1 0 0 2
*29 1 1 1 0 1 1
*30 1 1 1 1 0 1
31 1 1 1 1 1 none
* – These don’t really count as rules because there is only one choice to make. No decision process. Likewise, number 31 is not a rule since no choices can be made. The pattern terminates in this situation.
Number of permutations is 309,586,821,120.


Back to menu page.