Найти индекс конкретной комбинации без генерации всех ncr-комбинаций

Question

Я пытаюсь найти индекс конкретной комбинации без создания фактического списка всех возможных комбинаций. Для примера: 2 числовых комбинаций от 1 до 5, 1,2, 1,3,1,4,1,5, 2,3,2,4,2,5..so..on. Каждая комбинация имеет свой собственный индекс, начинающийся с нуля, если моя догадка правильная. Я хочу найти этот индекс без создания всей возможной комбинации для данной комбинации. Я пишу на C#, но мой код генерирует все возможные комбинации на лету. Это было бы дорого, если n и r равны 80 и 9, и я даже не могу перечислить фактический диапазон. Есть ли возможный способ найти индекс, не производя фактическую комбинацию для конкретного индекса

public int GetIndex(T[] combination) 
        { 
         int index = (from i in Enumerable.Range(0, 9) 
             where AreEquivalentArray(GetCombination(i), combination) 
             select i).SingleOrDefault(); 

         return index; 

        } 

Answer 1

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

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

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

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

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

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

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

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

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

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

public void Test10Choose5() 
{ 
    String S; 
    int Loop; 
    int N = 10; // Total number of elements in the set. 
    int K = 5; // 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); 
    } 
} 

Если вам нужно использовать значение не намного больше, чем 80 выбрать 9, то вам придется конвертировать класс использовать длинные позиции. Наибольшее значение, которое может удерживать длинное, составляет 18 446 744 073 709 551 616, что составляет 2^64.Таким образом, наибольшее значение, которое может выбрать 80, выбирает N, будет 80 выбрать 21, что составляет 10 100 903 263 463 355 200. Если вам нужны номера, которые больше, чем это, вы, вероятно, захотите изучить возможность изменения класса для использования .NET framework BigInteger class.

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

Answer 2

Я нашел ответ на свой вопрос простым языком. Это очень просто, но кажется эффективным в моей ситуации. Выбор метода осуществляется с другого сайта, хотя он генерирует комбинации для n выбранных элементов. R:

public long GetIndex(T[] combinations) 
     { 
      long sum = Choose(items.Count(),atATime); 
      for (int i = 0; i < combinations.Count(); i++) 
      { 
       sum = sum - Choose(items.ToList().IndexOf(items.Max())+1 - (items.ToList().IndexOf(combinations[i])+1), atATime - i); 
      } 

      return sum-1; 

     } 
private long Choose(int n, int k) 
     { 
      long result = 0; 
      int delta; 
      int max; 
      if (n < 0 || k < 0) 
      { 
       throw new ArgumentOutOfRangeException("Invalid negative parameter in Choose()"); 
      } 
      if (n < k) 
      { 
       result = 0; 
      } 
      else if (n == k) 
      { 
       result = 1; 
      } 
      else 
      { 
       if (k < n - k) 
       { 
        delta = n - k; 
        max = k; 
       } 
       else 
       { 
        delta = k; 
        max = n - k; 
       } 
       result = delta + 1; 
       for (int i = 2; i <= max; i++) 
       { 
        checked 
        { 
         result = (result * (delta + i))/i; 
        } 
       } 
      } 
      return result; 
     }