[Math] Programmatically getting list of combinations

combinationscombinatorics

EDIT: This question is in a grey area between between SO and here. The source code isn't quite necessary, but I would at lease have a clue as to figure it out. Also, I've clarified and simplified my question. I will link my SO question here, and here's a link to it.

EDIT 2: Check the bottom for some information on a potentially relevant formula.

EDIT 3: The main question is bolded for emphasis.

I'm trying to implement the Math.hypot function introduced in ECMAScript 6 in ECMAScript 5 for browsers, etc. that don't already support it (Firefox is the only one I've found that does), limiting overflow and underflow, and I ran into a massive dilemma: how would I programmatically determine the list of all combinations of a given length of a single given set? An example of this is all combinations of three elements out of four possible elements:

Here's what I need (in pseudocode):

Set: [a, b, c, d]
Number per combination: 3

What I need:
[[a, b, c],
 [a, b, d],
 [a, c, d],
 [b, c, d]]

Just in case it is relevant, I thought I would put the formula I'm trying to code. Only finding the set $C$ is the real stumbling block. The rest is rather easy to code. Refer to the Stack Overflow question for details of my current implementation so far.

Shorthand used in my formulation:

  • $x$: the set of arguments passed to the function
  • $x_i$: the argument passed at position $i$
  • $n$: the total number of arguments
  • $P_n=\prod_{i=1}^nx_i$
  • $C$: the set of all combinations of $x$ excluding the last element and resulting set length $n-2$
    • Ex.: $x=\{a, b, c, d, e\}$
    • $C=\{{\{a, b, c\}}, {\{a, b, d\}}, {\{a, c, d\}}, {\{b, c, d\}}\}$
  • $C_i$ the group/set element at index $i$
  • $D_i$ the product of the elements at $C_i$

\begin{equation} \sqrt{\sum_{i=1}^nx_i}=\left|P_{n-1}\right|\sqrt{\sum_{k=1}^{n-2}\frac{1}{{D_k}^2}+\left(\frac{x_n}{P_{n-1}}\right)^2} \end{equation}

Best Answer

Ok a lot question let's answer the first!

Given a Set $A=\{a,b,c,d\}$ all subsets with $n=3$ elements are:

$$ \{a,b,c\}, \{a,b,d\}, \{a,c,d\}, \{b,c,d\} $$

To generate this list you can use this (in c), given $|A|=\#A=m$

# Counter Array int count[n]; int j;

# Initialise Array
for(; j < n; j++){
    count[j] = j;
}

# Now Iterate throught all combinations
while(1){
    for(j=n-1; 1; j--){
        count[j] += 1;

        if(count[j] >= m-n-j){
            if(j==0){
                goto abort;
            }
            count[j] = count[j-1]+1;
        }
        else{
            break;
        }
    }

    # Here you got your Set `count`
}
abort:

But this is supposed to be a help to understand the problem. This can be optimized!

Related Question