RodionGork's blog

Combinations with limited repetitions
By RodionGork, 10 years ago, translation, In English

How to generate combinations of K elements chosen from the set of size N where some elements are duplicates? For example:

[1, 1, 2, 3, 3, 3]
choosing subsets of size 3 we have:
[1, 1, 2]
[1, 1, 3]
[1, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]

Somewhat clumsy algorithm could be derived from simple generation of combinations without repetitions — however its "clumsiness" make me hesitating and I'm interested whether more nice approach exists. Regretfully "Combinations with Repetitions" on the web mostly refer to another problem (if I got it right) where the number of repetitions for each element is unbounded.

Thanks in advance for hints / links!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Why not to use bitmasks?

Easily you can generate all possible subsets and work only with the subsets containing exactly k elements.

If you don't want to generate unnecessary subsets, I provide you a nice code I found in topcoder forums:

int next(int x) {
		int y = x + Integer.lowestOneBit (x);
		x = x & ~y;
		while ((x & 1) == 0)
			x >>= 1;
		x >>= 1;
		return y | x;
}

next(x) returns the next integer > x with the same number of bits turned on in O(logN).

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

ur problem can be reduced to the following:

given a vector (a1, a2, ... an), find the number of vectors (b1, b2, ... bn) such that:

  • 0 ≤ bi ≤ ai
  • b1 + b2 + ... + bn = k

on hindsight this looks to be solvable using dynamic programming, but i'm not very sure.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Use backtracking, with an element, decide how many will it be appeared.

n=6, k=3;
b[] = {1, 2, 3}; // suppose that one-based
Count[] = {2, 1, 3};
int a[k]; // we build own array here

void backtrack(int u, int x){ // building a[u], use b[x..n]
    if (u==k+1) {
        cout << a[0] << a[1] << ... << a[k] << endl;
        return;
    }
    if (Count[x]) { // choose b[x]
        a[u]=b[x];
        Count[x]--;
        backtrack(u+1, x);
        Count[x]++;
    }
    backtrack(u, x+1);
}

Call backtrack(1, 1). All arrays above are one-based.

→ Reply