Anticipating your next question:
It may be also interesting to look at an
"inductive law n--> n+1" for that.
For the number of combinations we have (visualized by Pascal's triangle)
[1] numOfCombs(n,k-1) + numOfCombs(n,k) = numOfCombs(n+1,k) for 0 < k <= n.
This is an "inductive law n->n+1", i.e. if you have computed the number of combinations for a fixed n and all k <= n, then you can get the number of combinations for all k <= n+1 from that.
Recall the case k-1=0 is the one possibility to take no element out of n.
For the combinations we have similarly an "inductive law n->n+1":
[2] combin*(n,k-1) &cr& combin(n,k) = combin(n+1,k) for 0 < k <= n.
Here combin*(n,k-1) is built as follows:
Take combin(n,k), without the leading cr, and put comma & n+1 after each line of it.
Recall the case k-1=0 is the one combination to take no element out of n, an empty line.
That is, if you have computed the combinations for a fixed n and all k <= n, then you can get the combinations for all k <= n+1 from that.
But the result of this induction is no longer sorted lexicographically. One way to solve this is to sort it after concatenating:
Code: Select all
-- lexicographic ordering of lines with k items
repeat with j=k down to 1
sort rslt numeric by item j of each
end repeat
The formula [2] above is intuitively clear:
You have everything computed for a fixed n and now the new element n+1 appears.
This changes the combinations for taking k out of n+1 as follows.
First we have combin(n,k), that is the combinations of taking k and n+1 is not included, what remains unchanged.
Then we have additionally the combinations of taking k and n+1 is included.
That is, writing it out sorted, take k-1 out of the first n and then additionally n+1, that is the list combin*(n,k-1) as described above.
This "inductive law" allows (theoretically, using 'string'-addition) to compute the combination lists for _any_ n (depending on hardware limits only), while the recursive formula has a platform dependent limit for n from the recursion depth.
[But remember the huge sizes of the files.
Using decimal representation in bytes combin(100,4) has 3921225 lines and length 45799908 Bytes, combin(100,3) has 161700 combinations and length 1416492 Bytes,
so combin(101,4) has 3921225+161700=4082925 combinations and length 45799908+1416492+4*161700 = 47863200 Bytes]