N-я или произвольная комбинация большого набора

Ответ 1

Вот мой снимок:

int k = 527; //The kth combination is calculated
int N=500; //Number of Elements you have
int a=0,b=1,c=2; //a,b,c are the numbers you get out

while(k >= (N-a-1)*(N-a-2)/2){
    k -= (N-a-1)*(N-a-2)/2;
    a++;
}
b= a+1;
while(k >= N-1-b){
    k -= N-1-b;
    b++;
}

c = b+1+k;


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result

Получил это представление о том, сколько комбинаций осталось до следующего числа. Однако он работает только для трех элементов. Я не могу гарантировать, что это правильно. Было бы здорово, если бы вы сравнили его с вашими результатами и дали некоторую обратную связь.

Ответ 2

Если вы ищете способ получить лексикографический указатель или ранг уникальной комбинации вместо перестановки, то ваша проблема подпадает под биномиальный коэффициент. Биномиальный коэффициент обрабатывает проблемы выбора уникальных комбинаций в группах из K с общим количеством элементов.

Я написал класс в С# для обработки общих функций для работы с биномиальным коэффициентом. Он выполняет следующие задачи:

• Выводит все K-индексы в хорошем формате для любого N, выбирающего K в файл. K-индексы могут быть заменены более описательными строками или буквами.

• Преобразует K-индексы в соответствующий лексикографический указатель или ранг записи в таблице отсортированных биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, основанные на итерации. Он делает это, используя математическое свойство, присущее Pascal Triangle, и очень эффективно по сравнению с итерацией по множеству.

• Преобразует индекс в отсортированную таблицу биномиальных коэффициентов в соответствующие K-индексы. Я считаю, что это также быстрее, чем более старые итеративные решения.

• Использует метод Mark Dominus для вычисления биномиального коэффициента, который гораздо реже переполняется и работает с большими числами.

• Класс написан на .NET С# и предоставляет способ управления объектами, связанными с проблемой (если они есть), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое, когда true, создаст общий список для хранения объектов, которые будут управляться. Если это значение ложно, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы использовать 4 вышеуказанных метода. Для доступа к таблице предоставляются методы доступа.

• Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был широко протестирован с 2 случаями и нет известных ошибок.

Чтобы прочитать об этом классе и загрузить код, см. Tablizing the Binomial Coeffieicent.

Следующий проверенный код будет проходить через каждую уникальную комбинацию:

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 500;  // Total number of elements in the set.
   int K = 3;  // Total number of elements in each group.
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   // The Kindexes array specifies the indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination.  
      BC.GetKIndexes(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

Вы можете легко переносить этот класс на С++. Вам, вероятно, не придется переносить общую часть класса для достижения ваших целей. Ваш тестовый пример 500 выбирает 3 дает 20 708 500 уникальных комбинаций, которые будут вписываться в 4 байта int. Если 500 выбрать 3 просто примерный пример, и вам нужно выбрать комбинации больше 3, тогда вам придется использовать длинные или, возможно, фиксированные точки int.

Ответ 3

Вы можете описать конкретный выбор из 3 из 500 объектов как тройной (i, j, k), где i - это число от 0 до 499 (индекс первого номера), j - от 0 до 498 (индекс второго, пропуская какое бы то ни было число было первым), а k находится в диапазоне от 0 до 497 (индекс последнего, пропуская оба ранее выбранных числа). Учитывая это, на самом деле довольно легко перечислять все возможные варианты: начиная с (0,0,0), увеличивать k до достижения максимального значения, а затем увеличивать j и reset k до 0 и так далее, пока j не достигнет своего максимального значения и так далее, пока j не достигнет своего максимального значения; затем увеличивайте i и reset как j, так и k и продолжайте.

Если это описание звучит знакомо, это потому, что он точно так же, как приращение номера базы-10, за исключением того, что база намного сложнее, и на самом деле база варьируется от цифры до цифры. Вы можете использовать это понимание для реализации очень компактной версии идеи: для любого целого n от 0 до 500 * 499 * 498 вы можете получить:

struct {
  int i, j, k;
} triple;

triple AsTriple(int n) {
  triple result;
  result.k = n % 498;
  n = n / 498;
  result.j = n % 499;
  n = n / 499;
  result.i = n % 500;  // unnecessary, any legal n will already be between 0 and 499
  return result;
}

void PrintSelections(triple t) {
  int i, j, k;
  i = t.i;
  j = t.j + (i <= j ? 1 : 0);
  k = t.k + (i <= k ? 1 : 0) + (j <= k ? 1 : 0);
  std::cout << "[" << i << "," << j << "," << k << "]" << std::endl;
}

void PrintRange(int start, int end) {
  for (int i = start; i < end; ++i) {
    PrintSelections(AsTriple(i));
  }
}

Теперь, чтобы очертить, вы можете просто взять цифры от 0 до 500 * 499 * 498, разделить их на поддиапазоны любым способом, который вы хотите, и каждый осколок вычислить перестановку для каждого значения в своем поддиапазоне.

Этот трюк очень удобен для любой проблемы, в которой вам нужно перечислить подмножества.