82324

Calculate Combination based on position

Question:

I have combinations like this:

1,2,3,4 //index 0<br /> 1,2,3,5 //index 1<br /> 1,2,3,6 //index 2

and so on until 7,8,9,10

So this will be n=10 k=4 from combinatorics

How calculate combination by index

For example when my index==1<br /> myCmb = func(index)<br /> returns 1,2,3,5

this is example i need this for bigest numbers, and for more params and without (if this possible) many loops

i find something like this to obtain position: <a href="http://answers.yahoo.com/question/index?qid=20110320070039AA045ib" rel="nofollow">http://answers.yahoo.com/question/index?qid=20110320070039AA045ib</a>

I want now reverse this...

I programming in C++ Thanks for any sugesstions or help

Answer1:

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>.

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:

#include <cstddef> #include <iostream> #include <string> #include <boost/lexical_cast.hpp> #include <boost/math/special_functions/binomial.hpp> std::size_t Choose(double n, double k) { using boost::math::binomial_coefficient; if (n < k) return 0; return static_cast<std::size_t>(binomial_coefficient<double>(n, k)); } // Returns the largest n such that Choose(n, k) <= pos. int CombinationElement(int k, int pos) { int n = k; int coeff = 1, prev_coeff = 0; while (coeff <= pos) { coeff = Choose(++n, k); prev_coeff = coeff; } return n - 1; } // Returns an k-combination at position pos. std::vector<int> Combination(int k, int pos) { std::vector<int> combination; for (; k > 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 << "Usage: $ " << argv[0] << " K POS" << endl; cout << "Prints the K-combination at position POS." << endl; return 1; } int k = boost::lexical_cast<int>(argv[1]); int pos = boost::lexical_cast<int>(argv[2]); std::vector<int> combination = Combination(k, pos); for (int i = 0; i < k; i++) cout << combination[i] << " "; cout << std::endl; }

Note, for convenience, the code depends on <a href="http://www.boost.org/" rel="nofollow">Boost</a> to calculate binomial coefficients (boost::math::binomial_coefficient<T>), and to parse strings into integers (boost::lexical_cast).

Answer2:

Here is an implementation in Mathematica, from the package <a href="http://www.combinatorica.com/" rel="nofollow"><em>Combinatorica</em></a>. The semantics are fairly generic, so I think it is helpful. Please leave a comment if you need anything explained.

UnrankKSubset::usage = "UnrankKSubset[m, k, l] gives the mth k-subset of set l, listed in lexicographic order." UnrankKSubset[m_Integer, 1, s_List] := {s[[m + 1]]} UnrankKSubset[0, k_Integer, s_List] := Take[s, k] UnrankKSubset[m_Integer, k_Integer, s_List] := Block[{i = 1, n = Length[s], x1, u, $RecursionLimit = Infinity}, u = Binomial[n, k]; While[Binomial[i, k] < u - m, i++]; x1 = n - (i - 1); Prepend[UnrankKSubset[m - u + Binomial[i, k], k-1, Drop[s, x1]], s[[x1]]] ]

Usage is like:

UnrankKSubset[1, 4, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}] <b> {1, 2, 3, 5}</b>

As you can see this function operates on sets.

<hr />

Below is my attempt to explain the code above.

<h3>UnrankKSubset is a recursive function with three arguments, called (m, k, s):</h3> <ol><li>m an Integer, the "rank" of the combination in lexigraphical order, starting from zero.</li> <li>k an Integer, the number of elements in each combination</li> <li>s a List, the elements from which to assemble combinations</li> </ol><h3>There are two boundary conditions on the recursion:</h3> <ol><li>

for any rank m, and any list s, if the number of elements in each combination k is 1, then:

return the m + 1 element of the list s, itself in a list.

(+ 1 is needed because Mathematica indexes from one, rather than zero. I believe in C++ this would be s[m] )

</li> <li>

if rank m is 0 then for any k and any s:

return the first k elements of s

</li> </ol><h3>The main recursive function, for any other arguments than ones specified above:</h3>

local variables: (i, n, x1, u)

Binomial is binomial coefficient: Binomial[7, 5] = 21

Do:

i = 1 n = Length[s] u = Binomial[n, k] While[Binomial[i, k] < u - m, i++]; x1 = n - (i - 1);

Then return:

Prepend[ UnrankKSubset[m - u + Binomial[i, k], k - 1, Drop[s, x1]], s[[x1]] ]

That is, "prepend" the x1 element of list s (remember Mathematica indexes from one, so I believe this would be the x1 - 1 index in C++) to the list returned by the recursively called UnrankKSubset function with the arguments:

<ul><li>m - u + Binomial[i, k]</li> <li>k - 1</li> <li>Drop[s, x1]</li> </ul>

Drop[s, x1] is the rest of list s with the first x1 elements removed.

<hr />

If anything above is not understandable, or if what you wanted was an explanation of the algorithm, rather than an explanation of the code, please leave a comment and I will try again.

Recommend

  • Programming a specific 3d (star-like) model in OpenGL? [closed]
  • Fix precision issues when *displaying* floats in python
  • Is it safe to combine sizeof and placement new?
  • Template based Subject Observer pattern - Should I use static_cast or dynamic_cast
  • How to convert a subset of numpy recarray to continuous array?
  • How to increase the RAM Memory usage programatically?
  • How to programmatically detect if a bitmap has alpha channel?
  • QModelIndex becomes invalid when removing rows
  • What diagnostic tools are available for Node.js applications?
  • How can I spawn a long running process in a Perl CGI script?
  • VBA: Extract Top 'x' Entries from each category
  • C++ how to get substring after get position of its index
  • Crafting a LINQ based solution to determine if a set of predicates are satisfied for a pair of colle
  • Subclassing QGraphicsItem prevents me from being able to use itemAt() on a QGraphicsScene/View
  • OOP Javascript - Is “get property” method necessary?
  • GridView breaks while scrolling
  • copying resource to sdcard gives a damaged file in android
  • Database structure design with variable amounts of fields
  • how to adjust image in a panel in Java swing?
  • Java Scanner input dilemma. Automatically inputs without allowing user to type
  • Regex thinks I'm nesting, but I'm not
  • Problems to linebreak with an int in JLabel
  • How reduce the height of an mschart by breaking up the y-axis
  • output of program is not same as passed argument
  • Fill an image in a square container while keeping aspect ratio
  • MySQL WHERE-condition in procedure ignored
  • Convert array of 8 bytes to signed long in C++
  • Rearranging Cells in UITableView Bug & Saving Changes
  • align graphs with different xlab
  • Windows forms listbox.selecteditem displaying “System.Data.DataRowView” instead of actual value
  • How get height of the a view with gone visibility and height defined as wrap_content in xml?
  • FormattedException instead of throw new Exception(string.Format(…)) in .NET
  • Is there any way to bind data to data.frame by some index?
  • Django query for large number of relationships
  • Sorting a 2D array using the second column C++
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • Reading document lines to the user (python)
  • How can I use `wmic` in a Windows PE script?
  • java string with new operator and a literal
  • How to push additional view controllers onto NavigationController but keep the TabBar?