enumerate combinations

[EngrStudent]

A combination cares about members, but a permutation cares about order.  What we call a combination lock, is really a permutation lock: order matters.

I have (currently) about 215 elements that I want to be able to enumerate a list of combinations (based on indices) for pick r where r is typically less than 25. 

How do I enumerate the distinct combinations for a variable n.  If r were 4 then there would be about 86 million unique combinations.  If r is only 2 then there are ~23000.

If n were fixed, I would nest for loops, where the next one starts at the index of the current, so that I would be doing a triangular (or hyper-corner) search instead of searching the whole space. 

Some references:

- https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size...

[EngrStudent]

update:

When I calculate the number of combinations of 227 pick 2, I get 25651.  When I try to compute this using factorials (the relevant built-ins) it gives the factorial of 227 as infinity.  It is calling some external library which doesn't like that value.

[billko]

I'm guessing the answer is too large to hold in a double.  Factorial for 128 is already 385.62E+213.

[EngrStudent]

The combinations is a ratio of products.  There is a natural-log trick that gets around this nicely.

I put this MathScript in so I can know the number of elements in the output.  (Yes there are some crutches in the code.) 

When I try to compute 636 pick 6, I get 89,771,348,696,200 instead of 897,71,348,696,212.  There is no way my enumeration search is going to attempt ~89 trillion evaluations in reasonable time, but at least I can know that and build in some padding (soft stuff that keeps me from banging into walls such as the age of the universe).

Wow do I wish I had a support system that could help me look less incompetent.  For the majority of my stuff, I am lone-wolfing it, which is a high-risk venture.

[EngrStudent]

So in doing the "hyper-corner" there is a clever trick in that if you check each column for "is it the max index of valid points for that column" and then take the difference, you are only going to find a single positive value. 

This tells the column to increment, and then the remaining columns are incremented above that.

[mcduff]

Interesting problem. Sorry I cannot help. But I will offer strange advice on a LabVIEW forum. I know from limited experience that Mathematica is good at these problems, may not help you, but I was able to test your answers from before with 1-line expressions:

Length[Subsets[Range[215], 2]]

23,221

Length[Subsets[Range[215], 4]]

88,224,391

mcduff

[EngrStudent]

Mcduff, you are brick: solid.  Thanks.

In R, when I do it, I get this:

> choose(215,2)
[1] 23005
> choose(215,4)
[1] 86567815

The function "combn" enumerates them.  That thing I'm hand-coding in G is a one-word, built-in, in R.  

[mcduff]

I wonder why the answers are different?

Anyway, I get what you are saying. I like to use LabVIEW, in fact, it is probably why I am still employed, however it is not the only tool that I have. Sometimes I need Matlab, Mathematica, pro Fit, python, etc. Luckily in a lot of situations I can choose what tool to use and am not stuck making it fit a certain tool.

Good luck!

mcduff

[Mark_Yedinak]

---

@EngrStudent wrote:

Mcduff, you are brick: solid.  Thanks.

In R, when I do it, I get this:

> choose(215,2)
[1] 23005
> choose(215,4)
[1] 86567815

The function "combn" enumerates them.  That thing I'm hand-coding in G is a one-word, built-in, in R.  

---

LabVIEW, more precisely G, is a programming language. It is not intended to be the be-all-end-all mathematics tool. I not familiar with the R tool that you mention but I suspect that is a very focused tool for solving mathematics problems, not a general purpose programming language. Most programming languages would not have that as a builtin function.

[EngrStudent]

I think we might be "up in the stratosphere" or "out in the boonies" for the intended functions.  Both the "exp" and the "ln" aren't in fact either.  They tend to be polynomial (rational) aproximations that fit to roundoff in the domain.  It could be then, that living in the area of these larger numbers, or at least large number of additions of logarithms, we are in some place of interaction of round-off and numeric inaccuracy that the different algorithms diverge.  I remember something about addition being very bad for roundoff, but multiplication less so.  It has been a decade or so, so memory is fuzzy.

I tend to do more R, Python (sympy/numpy), MatLab, then others.  A diverse toolbox, and then testing the heck out of whatever you make to be sure it works right, are useful ways to move forward well.  There are no "silver bullets", there are just well known tools with strengths and weaknesses that can be used well by folks who know them well.