LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

enumerate combinations

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...

0 Kudos
Message 1 of 33
(3,160 Views)

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.

0 Kudos
Message 2 of 33
(3,136 Views)

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

Bill
CLD
(Mid-Level minion.)
My support system ensures that I don't look totally incompetent.
Proud to say that I've progressed beyond knowing just enough to be dangerous. I now know enough to know that I have no clue about anything at all.
Humble author of the CLAD Nugget.
0 Kudos
Message 3 of 33
(3,130 Views)

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.) 

 

Capture.GIF

 

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.

0 Kudos
Message 4 of 33
(3,116 Views)

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.

0 Kudos
Message 5 of 33
(3,095 Views)

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

 

Message 6 of 33
(3,084 Views)

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.  

0 Kudos
Message 7 of 33
(3,077 Views)

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

0 Kudos
Message 8 of 33
(3,071 Views)

@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.



Mark Yedinak
Certified LabVIEW Architect
LabVIEW Champion

"Does anyone know where the love of God goes when the waves turn the minutes to hours?"
Wreck of the Edmund Fitzgerald - Gordon Lightfoot
0 Kudos
Message 9 of 33
(3,068 Views)

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.

0 Kudos
Message 10 of 33
(3,067 Views)