User bio
404 bio not found
Member since Jul 25, 2017
Replies:

First, my experience with tail recursion is very limited,
second, after adding the TailFact() method and a little change to Times() method in the above class, I must say, I don't see any benefit of the TailFact() method. Quite the contrary, now the function have to push two values on the stack instead of one...

/// Factorial using tail_recursion
/// 
ClassMethod TailFact(n)
{
	quit ..tfact(n,1)
}

ClassMethod tfact(n, f)
{
	quit $select(n>1:..tfact(n-1,f*n),1:f)
}

/// There is a noticeable time difference between MulFact() and RecFact().
/// 
/// Recursion helps to keep an algorithm clear an simple but needs more
/// resources - for a few loops it's OK, but for many loops it's a no-go
/// (beside a stack space, a stack frame must be prepared for each loop cycle)
ClassMethod Times(n)
{
	while $zh#1 {} s t1=$zh f i=1:1:1E6 { d ..MulFact(n) } s t1=$zh-t1
	while $zh#1 {} s t2=$zh f i=1:1:1E6 { d ..RecFact(n) } s t2=$zh-t2
	while $zh#1 {} s t3=$zh f i=1:1:1E6 { d ..TailFact(n) } s t3=$zh-t3
	write " Fact:",$j(t1,10,4),!,"Rfact:",$j(t2,10,4),!,"Tfact:",$j(t3,10,4),!
	write "RDiff:",$j(t2-t1/t1*100,8,2),"%",!,"TDiff:",$j(t3-t1/t1*100,8,2),!
}

and here some time values

USER>d ##class(DC.Math).Times(5)
 Fact:    0.3306
Rfact:    1.2199
Tfact:    1.4219
RDiff:  268.97%
TDiff:  330.07

USER>d ##class(DC.Math).Times(10)
 Fact:    0.4433
Rfact:    2.3913
Tfact:    2.5549
RDiff:  439.40%
TDiff:  476.28

USER>d ##class(DC.Math).Times(20)
 Fact:    0.7034
Rfact:    4.8017
Tfact:    5.2183
RDiff:  582.63%
TDiff:  641.86

If I understand you correctly, you want for a given number of objects all the possible combinations? That is, if we have 3 objects (3 numbers, 3 words or whatever) then you want:
1 of 3 (3 possibilities): (1) (2) (3)
2 of 3 (3 possibilities): (1,2) (1,3) (2,3)
3 of 3 (1 possibility)   : (1,2,3)
For 3 objects there are in sum 7 possible combinations (see above). Your ^x(1,1) string contains 137 items. I'm pretty sure, you will never see that mutch combination...

Here some numbers for all possible combinations for:
  1 item :                                                       1
 10 items:                                                   1,023
 20 items:                                               1,048,575
 50 items:                                   1,125,899,906,842,623
 75 items:                          37,778,931,862,957,161,730,000
100 items:               1,267,650,600,228,229,401,000,000,000,000
137 items: 174,224,571,863,520,493,300,000,000,000,000,000,000,000

A year has 365.25*86400, that are 31,557,600 seconds.  With another words, you would need a computer system, which is able to genarate 5.5 * 10^33 combinations each second! I don't have such a beast, and I'm sure, you too.

Anyway, maybe the below class gives you some clue, how to compute and how to generate combinations. One more note, recursion is the tool to make (some) solutions clear and simple but recursion in loops, especially in loops with thousands or millions of passes, isn't a good idea. Beside of resources (stack, memory) for each new call a stackframe must be prepared and after the call removed again. This costs time, much time. Try that Times() method in the below class.

/// Some math functions
Class DC.Math Extends %RegisteredObject
{

/// Factorial by multiplication (the more practical way)
/// Return n!
/// 
ClassMethod MulFact(n)
{
	for i=2:1:n-1 set n=n*i
	quit n+'n
}

/// Factorial by recursion (the way, people learn recursion in the school)
/// Return n!
/// 
ClassMethod RecFact(n)
{
	quit $select(n>1:n*..RecFact(n-1),1:1)
}

/// There is a noticeable time difference between MulFact() and RecFact().
/// 
/// Recursion helps to keep an algorithm clear an simple but needs more
/// resources - for a few loops it's OK, but for many loops it's a no-go
/// (beside a stack space, a stack frame must be prepared for each loop cycle)
ClassMethod Times(n)
{
	while $zh#1 {} s t1=$zh f i=1:1:1E6 { d ..MulFact(n) } s t1=$zh-t1
	while $zh#1 {} s t2=$zh f i=1:1:1E6 { d ..RecFact(n) } s t2=$zh-t2
	write " Fact:",$j(t1,10,4),!,"Rfact:",$j(t2,10,4),!," Diff:",$j(t2-t1/t1*100,8,2),"%",!
}

/// The Holy Trinity of the statistic functions: permutations, combinations and variations
/// 
/// Here we go with the combinations.
/// 
/// Return the number of combinations (without repetition) of K elements from a set of N objects
/// 
/// The number of possible combinations is: N over K
/// which is the same as:  N! / (K! * (N-K)!)
/// 
/// Note:
/// one can't make a direct use of the (above) Factorial function
/// because the MAXNUM limit will be hit very soon
ClassMethod Comb(k, n)
{
	set c=1 for k=1:1:k { set c=c/k*n, n=n-1 } quit c
}

/// Return the sum of all possible combinations of N objects
/// i.e. (1-of-n) + (2-of-n) + (3-of-n) + ... + (n-of-n)
/// 
ClassMethod AllComb(n)
{
	set s=0 for i=1:1:n { set s=s+..Comb(i,n) } quit s
}

/// Generate a list of combinations for K elements of N objects
/// 
ClassMethod GenComb(k, n)
{
	for i=1:1:k set e(i)=n-k+i
	set s=0, c(0)=0
	
10	set s=s+1, c(s)=c(s-1)
14	for c(s)=c(s)+1:1:e(s) goto 10:s<k do ..work1(.c,s)
16	set s=s-1 if s goto 14:c(s)<e(s),16
}

/// This method is the workhorse
/// either, print the combinations (one k-tuple at time)
/// or do your own task.
ClassMethod work1(c, s) [ Internal ]
{
	write "(" for i=1:1:s write:i>1 "," write c(i)
	write ")",!
}

/// For example, you could use that ^x(1,1) string
/// 
ClassMethod work2(c, s)
{
	set t=^x(1,1)
	write "(" f i=1:1:s write:i>1 "," write $p(t,",",c(i))
	write ")",!
}

/// save each combination (OK, c(0) should be killed)
/// 
ClassMethod work3(c, s)
{
	m ^mtemp("comb",$i(^mtemp("comb")))=c
}

}

write ##class(...).Comb(3,4) to compute the combinations 3-of-4 (3 items of 4 objects)
write ##class(...).AllComb(3) to compute all combinations of 3 objects (1-of-3 plus  2-of-3 plus 3-of-3)
do ##class(...).GenComb(3,4) to show all 3-of-4 combinations
For all possible combinations of N objects you must do a loop:
for i=1:1:N do ##class(...).GenComb(i,N)

Certifications & Credly badges:
Julius has no Certifications & Credly badges yet.
Global Masters badges:
Followers:
Following:
Julius has not followed anybody yet.