Рассчитать комбинацию на основе позиции

Question

У меня есть такие комбинации:

1,2,3,4 // индекс 0
1,2,3,5 // индекс 1
1,2,3,6 // индекс 2

и т. Д. До 7,8,9,10

Так что это будет n = 10 k = 4 из комбинаторики

Как рассчитать комбинацию по индексу

Например, когда мой индекс == 1
myCmb = func (index)
возвращает 1,2,3,5

это пример, который мне нужен для больших чисел, для большего количества параметров и без (если это возможно) множества циклов

Я нахожу что-то вроде этого, чтобы получить позицию: http://answers.yahoo.com/question/index?qid=20110320070039AA045ib

Я хочу теперь изменить это ...

Я программирую на C ++ Спасибо за любые предложения или помощь

Answer 1

Вот реализация в Mathematica из пакета Combinatorica .Семантика довольно общая, поэтому я думаю, что это полезно.Пожалуйста, оставьте комментарий, если вам нужно что-то объяснить.

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

Использование похоже на:

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

<b>   {1, 2, 3, 5}</b>

Как вы можете видеть, эта функция работает на наборах.

---

Ниже приведена моя попытка объяснить приведенный выше код.

UnrankKSubset - это рекурсивная функция с тремя аргументами, которая называется (m, k, s):

1. mЦелое число, «ранг» комбинации в лексикографическом порядке, начиная с нуля.
2. k целое число, количество элементов в каждой комбинации
3. s Список,элементы, из которых можно собрать комбинации

В рекурсии есть два граничных условия:

1. для любого ранга m и любого списка s,если количество элементов в каждой комбинации k равно 1, то:

   возвращает элемент m + 1 списка s, сам по себе в списке.

   (+ 1 необходимо, потому что Mathematica индексирует от одного, а не от нуля. Я считаю, что в C ++ это будет s [m])

2. , если ранг m равен 0, то для любого k и любых s:

   возвращаются первые k элементов s

Основная рекурсивная функция для любых других аргументов, кроме указанных выше:

локальные переменные: (i, n, x1, u)

Binomial является биномиальным коэффициентом: 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);

Затем возвращаем:

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

То есть «предваряем»x1 элемент списка s (вспомните индексы Mathematica от одного, поэтому я считаю, что это будет индекс x1 - 1 в C ++) в список, возвращаемый рекурсивно вызываемой функцией UnrankKSubset с аргументами:

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

Drop[s, x1] - остаток списка s с первым x1элементы удалены.

---

Если что-либо из вышеперечисленного непонятно, или если вы хотели пояснить алгоритм, а не объяснение кода, пожалуйста, оставьте комментарий, и япопробую еще раз.

Answer 2

Похоже, вы хотите найти k-комбинацию для данного числа .

Следуя примеру , вот что должно работать:

#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;
}

Обратите внимание, для удобства код зависит от Boost для вычисления биномиальных коэффициентов (boost::math::binomial_coefficient<T>) и для анализа строк в целые числа (boost::lexical_cast).