Получение лексикографического индекса подмножества

Question

У меня есть список всех подмножеств размера k из набора {1, 2, ..., n}, упорядоченного в лексикографическом порядке, например, все подмножества размера 2 из набора {1, 2, 3, 4} являются {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. где индекс {1, 2} равен 0, {1, 3} равен 1 и т. д.

Теперь мне нужно написать алгоритм, который получает подмножество (предположим, что подмножество упорядочено) и возвращает его индекс в списке.

Я написал следующий алгоритм:

int GetSubsetIndex(List<int> subset, int N) 
{ 
    int Skip = 0; 
    int Last = 0; 
    int Depth = 1; 
    int K = subset.Count; 

    while (Depth <= K) 
    { 
     for (int i = Last + 1; i < subset[Depth - 1]; i++) 
     { 
      Skip += BinomialCoefficient(N - i, K - Depth); 
     } 

     Last = subset[Depth - 1]; 
     Depth++; 
    } 

    return Skip; 
} 

Этот алгоритм использует специальную структуру лексикографического порядка подмножеств, вот объяснение:

Допустим, у нас есть набор размером 6 (N = 6) и подмножество длины 3 (K = 3), то мы получим 6 подмножеств. теперь число подмножеств, начинающихся с 1, равно 5, выбор 2, число подмножеств, начинающихся с 2, равно 4, выбор 2 и т. д.

Если первое число в подмножестве X, мы можем skip (N-1 выбрать K-1) + (N-2 выбрать K-1) + ... + (NX выбрать K-1) подмножества. Если X было первым числом, второе число Y в подмножестве не менее X + 1. Теперь мы можем пропустить (N- [X + 1] выбрать K-2) + (N- [X + 2] выбрать K-2) + ... + (N-Y выбрать K-2) и т. Д.

В коде алгоритма Skip представляет количество подмножеств, которые мы пропустили, последний представляет последнее число, которое мы рассмотрели в подмножестве (инициализировано 0, когда набор начинается с 1), Глубина - это то, насколько глубоко мы находимся в подмножестве, и K - длина всех подмножеств.

Задача этого алгоритма, который работает с O(N) время, если расчет биномиальный коэффициент O(1) (если он был предварительно обработан) или O(N*k) (если это не было), на практике некоторые подмножества могут быть вычислены очень быстро , Я пытаюсь понять, как получить этот индекс с короткой временной привязкой.

Вы можете выполнить любую предварительную обработку, если вы не используете больше, чем O(N chooke K) памяти, то есть количество подмножеств.

Answer 1

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

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

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

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

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

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

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

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

Чтобы прочитать об этом классе и загрузить код, см. 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, может быть 80 выбрано 21, что составляет 10 100 903 263 463 355 200. Если вам нужны номера, которые больше, чем это, вы, вероятно, захотите изучить возможность изменения класса для использования .NET framework BigInteger class. Не следует переносить его на C++ или на любой другой язык.

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

Answer 2

Ответ, который вы хотите, это комбинаторная система чисел. См. http://en.wikipedia.org/wiki/Combinatorial_number_system

Инструкции по поиску n-го подмножества размера k или для подмножества размера k найти его индекс.