StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This code requires that the "element pool" array be sorted from minimum to maximum, with no duplicate entries.</p> <p>The function <code>first_combination</code> initializes the result array ("dist") to the first combination. After this, <code>next_combination</code> is called in a loop until it returns false (just like in your example). The "n" and "k" arguments have been replaced with template parameters that pick up the arrays' sizes -- so the enumeration functions need the pool array in addition to the result.</p> <pre><code>#include <iostream> template<typename T, int N, int K> void first_combination(const T (&pool)[N], T (&dist)[K]) { for(int ki=0; ki<K; ++ki) { dist[ki] = pool[0]; } } template<typename T, int N, int K> bool next_combination(const T (&pool)[N], T (&dist)[K]) { int ni = 0;; int ki = 0; for(;;) { const int prev_ni = ni; // search the pool for the value in this slot for(ni=0; pool[ni] != dist[ki]; ++ni) { if(ni == N) return false; // slot contains a value not found in the pool } if(++ni < N) break; ni = 0; dist[ki] = pool[0]; if(++ki == K) return false; } int v = pool[ni]; dist[ki] = v; // code below assumes pool[] is sorted for(--ki; ki>=0; --ki) { if(dist[ki] < v) { dist[ki] = v; } else { v = dist[ki]; } } return true; } template<typename T, int COUNT> void dumparray( T (&dist)[COUNT]) { std::cout << '{'; for(int i=0; i<COUNT; ++i) { if(i) std::cout << ','; std::cout << dist[i]; } std::cout << '}' << std::endl; } int main(int argc, char* argv[]) { const int pool[] = {1,3,6,7}; int dist[3] = {0}; first_combination(pool, dist); do { dumparray(dist); } while(next_combination(pool, dist)); return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload