CODEWITHSUNDEEP
c++algorithmmatlab
Doombot
Doombot

Reputation: 573

Binomial coefficient with a twist

Right now, to enumerate all k=4 combinations among the set

Set = [1; 2; 3; 4; 5; 6; 7; 8]

I use the prebuilt Matlab function nchoosek that compute the binomial coefficients. The number of combinations of n things taken k at a time is computed by n!/((n–k)! k!).

Now, imagine that I have a set of data containing n = 8 elements:

Set = [1.A; 2.B; 3.C; 4.D; 5.B; 6.D; 7.C; 8.A]

I want to enumerate all the combinations of 4 integers in "Set", but with a twist: I must have only one element with the same letter in any combination (the order doesn't matter). For example:

[1.A; 2.B; 6.D; 7.C] would be a valid combination, but not [1.A; 2.B; 6.D; 8.A].

Having [1.A; 2.B; 6.D; 7.C], I must still generate the combination [8.A; 2.B; 6.D; 7.C]

Instead of having to generate 70 combinations, since there are 2 occurrences of A, B, C and D, I only have to generate 2*2*2*2 = 16 combinations. The 70-16 = 54 other combinations are irrelevant to my problem and I would rather not generate them since it becomes increasingly computationally expansive. For the moment, I generate the 70 combinations, then use some logic to remove the all the non relevant combinations.

So, my questions are:

  1. Is there a name for such a type of combinations? (Could help me to search for info and better understand the problem)
  2. Is there some existing algorithm allowing to compute that? In Matlab or C++. Please, if it is full of reg ex, a bit of explanations would be welcome...

Upvotes: 3

Views: 282

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

A general recursive (iterative if stacked) algorithm:

combs(index,multiset,k,result):
  if length of result == k:
    output result
    return
  if length of result + length of multiset - index < k:
    return
  for j in multiset[index]:
    combs(index + 1,multiset,k,result with multiset[index][j] added)
  combs(index + 1,multiset,k,result)

JavaScript example:

function combs(i,multiset,k,result){
  if (result.length == k){
    console.log(result);
    return;
  }
  if (result.length + multiset.length - i < k)
    return;
  for (var j=0; j<multiset[i].length; j++){
    _result = result.slice();
    _result.push(multiset[i][j]);
    combs(i + 1,multiset,k,_result);
  }
  combs(i + 1,multiset,k,result);
}

combs(0,[["1.A","8.A"],["2.B","5.B"],["3.C","7.C"],["4.D","6.D"]],4,[]);

Upvotes: 1

Louis Ricci
Louis Ricci

Reputation: 21086

This is just the standard C(N, K) with a uniquness check. The below code is JavaScript but converting it to C++ shouldn't be too difficult.

function nchoosekUnique(arr, k, combo, result) {
  if(combo.length === k) {
    result.push(combo);
    return result;
  }
  for(var i=0; i < arr.length - k; i++) {
    // UNIQUE CHECK
    var unique = true;
    for(var u=0; u<combo.length; u++) {
      if(combo[u][1] == arr[i][1]) { 
        unique = false; 
        continue; 
      }
    }
    //
    if(unique === true) {
      var comboCpy = combo.slice(0);
      var arrCpy = arr.slice(0);
      comboCpy[comboCpy.length] = arrCpy.splice(i, 1)[0];
      nchoosekUnique(arrCpy, k, comboCpy, result);
    }
  }
  return result;
}

var arr = [[1,"A"], [2,"B"], [3,"C"], [4,"D"], [5,"B"], [6,"D"], [7,"C"], [8,"A"]];
JSON.stringify(nchoosekUnique(arr, 4, [], []), null, '\t');

note If you're K's are very large you may want to use a Set (HashSet) implementation for the combo variable instead of just an array.

Upvotes: 1

Michael S Priz
Michael S Priz

Reputation: 1126

Your twist adds a constraint to the problem. As far as I know there is no special name for this new problem, it is just a combinatorics problem like any other.

Notice that what you have ultimately done is add choices for each possible "slot" in the result set. The underlying assumption for the regular choose formula is that a given item can be either in the set, or not in the set. Notice that for each group A, B, C, and D, either

  1. A single integer of that type is in the result set,

OR

  1. An integer of that type is not in the set at all

Thus selecting which types of integers will be in the result set is the analog of selecting the actual integers that were in the result set of the original problem! Once we select which types of integers are in the result set, we can just make any choice for which integer of each type we will put into the set.

In your case, if we must choose 4 types to put into the set then the number of ways to do that is 4 choose 4 = 1 (A,B,C,D). For type A there are 2 options, type B there are 2 options, type C there are 2 options and type D there are 2 options, so there are 2*2*2*2=16 sets to choose :)

Upvotes: 1

MBo
MBo

Reputation: 80187

Transform you set to the form

[A[1, 8], B[2,5], C[3,7], D[4,6]]

Generate base combinations by letter key - here is only one (C(4,4)) base combination (A,B,C,D) and expand combinations with number subkeys (for example, with recursive approach)

Upvotes: 2

Related Questions