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)
Just as an info, I can read cyrillic, I can talk serbian, consequently I understand a little bit (the emphasis is on little) Russian, and Ukrainian but I can't make the difference between the two. By the way, we try to solve problems and not language differences... 😉
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