The solution for the branching factor of the alpha-beta pruning algorithm and its optimality
Judea Pearl · Communications of the ACM · 1982
and Data Structures Editor stop(top).In such a situation, the element top has to be deleted from the stack and more operations are required to generate the next combination.When k > top > 2, one can show that the probability for a specific value of top that a[top] = stop(top) is a(top + l)/a(top), which reduces to (k -top + l)/(n -top).Hence, when k is small compared to n, it is very unlikely that the next combination is generated by using the theoretical maximum number of operations.If k is very small compared to n, then P(I), the probability that a combination is generated by changing only a [1], is approximately 1.In this case, almost all the combinations are generated by the single statement a[1] := a[1] -1.It is doubtful that any combination algorithm would require less work than this to generate a combination.