Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>It seems like you want to <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Combinatorial_number_system#Finding_the_k-combination_for_a_given_number" rel="nofollow">find the k-combination for a given number</a>.</p> <p>Following the <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Combinatorial_number_system#Example" rel="nofollow">example</a>, here's something that should work:</p> <pre><code>#include &lt;cstddef&gt; #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;boost/lexical_cast.hpp&gt; #include &lt;boost/math/special_functions/binomial.hpp&gt; std::size_t Choose(double n, double k) { using boost::math::binomial_coefficient; if (n &lt; k) return 0; return static_cast&lt;std::size_t&gt;(binomial_coefficient&lt;double&gt;(n, k)); } // Returns the largest n such that Choose(n, k) &lt;= pos. int CombinationElement(int k, int pos) { int n = k; int coeff = 1, prev_coeff = 0; while (coeff &lt;= pos) { coeff = Choose(++n, k); prev_coeff = coeff; } return n - 1; } // Returns an k-combination at position pos. std::vector&lt;int&gt; Combination(int k, int pos) { std::vector&lt;int&gt; combination; for (; k &gt; 0; --k) { int n = CombinationElement(k, pos); combination.push_back(n); pos -= Choose(n, k); } return combination; } int main(int argc, char** argv) { using std::cout; using std::endl; if (argc != 3) { cout &lt;&lt; "Usage: $ " &lt;&lt; argv[0] &lt;&lt; " K POS" &lt;&lt; endl; cout &lt;&lt; "Prints the K-combination at position POS." &lt;&lt; endl; return 1; } int k = boost::lexical_cast&lt;int&gt;(argv[1]); int pos = boost::lexical_cast&lt;int&gt;(argv[2]); std::vector&lt;int&gt; combination = Combination(k, pos); for (int i = 0; i &lt; k; i++) cout &lt;&lt; combination[i] &lt;&lt; " "; cout &lt;&lt; std::endl; } </code></pre> <p>Note, for convenience, the code depends on <a href="http://www.boost.org/" rel="nofollow">Boost</a> to calculate binomial coefficients (<code>boost::math::binomial_coefficient&lt;T&gt;</code>), and to parse strings into integers (<code>boost::lexical_cast</code>).</p>
 

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