Идеальный минимальный хэш для математических комбинаций
Сначала определите два целых числа N а также K, где N >= K, оба известны во время компиляции. Например: N = 8 а также K = 3,
Затем определите набор целых чисел [0, N) (или же [1, N] если это упрощает ответ) и назовите его S, Например: {0, 1, 2, 3, 4, 5, 6, 7}
Количество подмножеств S с K элементы задаются формулой C(N, K), пример
Моя проблема заключается в следующем: создать идеальный минимальный хэш для этих подмножеств. Размер примера хеш-таблицы будет C(8, 3) или же 56,
Меня не волнует порядок, только то, что в хеш-таблице содержится 56 записей, и что я могу быстро определить хеш из набора K целые числа. Меня тоже не волнует обратимость.
Пример хэша: hash({5, 2, 3}) = 42, (Число 42 не важно, по крайней мере, не здесь)
Есть ли общий алгоритм для этого, который будет работать с любыми значениями N а также K? Я не смог найти его с помощью поиска в Google или своими собственными наивными усилиями.
3 ответа
Существует алгоритм для кодирования и декодирования комбинации в ее номер в лексикографическом порядке всех комбинаций с заданным фиксированным K, Алгоритм является линейным для N для кода и декодирования комбинации. На каком языке вы заинтересованы?
РЕДАКТИРОВАТЬ: вот пример кода в C++(он находит лексикографический номер комбинации в последовательности всех комбинаций из n элементов, в отличие от тех, которые с k элементы, но это действительно хорошая отправная точка):
typedef long long ll;
// Returns the number in the lexicographical order of all combinations of n numbers
// of the provided combination.
ll code(vector<int> a,int n)
{
sort(a.begin(),a.end());
int cur = 0;
int m = a.size();
ll res =0;
for(int i=0;i<a.size();i++)
{
if(a[i] == cur+1)
{
res++;
cur = a[i];
continue;
}
else
{
res++;
int number_of_greater_nums = n - a[i];
for(int j = a[i]-1,increment=1;j>cur;j--,increment++)
res += 1LL << (number_of_greater_nums+increment);
cur = a[i];
}
}
return res;
}
// Takes the lexicographical code of a combination of n numbers and returns the
// combination
vector<int> decode(ll kod, int n)
{
vector<int> res;
int cur = 0;
int left = n; // Out of how many numbers are we left to choose.
while(kod)
{
ll all = 1LL << left;// how many are the total combinations
for(int i=n;i>=0;i--)
{
if(all - (1LL << (n-i+1)) +1 <= kod)
{
res.push_back(i);
left = n-i;
kod -= all - (1LL << (n-i+1)) +1;
break;
}
}
}
return res;
}
Я сожалею, что у меня есть алгоритм для задачи, которую вы просите прямо сейчас, но я считаю, что это будет хорошим упражнением, чтобы попытаться понять, что я делаю выше. Правда в том, что это один из алгоритмов, которые я преподаю в курсе "Разработка и анализ алгоритмов", и именно поэтому я написал его заранее.
Это то, что вам (и мне) нужно:
hash() карты k-tuples от [1..n] на съемочную площадку 1..C(n,k)\subset N, Усилие k вычитания (и O(k) в любом случае является нижней границей, см. замечание Странджева выше):
// bino[n][k] is (n "over" k) = C(n,k) = {n \choose k}
// these are assumed to be precomputed globals
int hash(V a,int n, int k) {// V is assumed to be ordered, a_k<...<a_1
// hash(a_k,..,a_2,a_1) = (n k) - sum_(i=1)^k (n-a_i i)
// ii is "inverse i", runs from left to right
int res = bino[n][k];
int i;
for(unsigned int ii = 0; ii < a.size(); ++ii) {
i = a.size() - ii;
res = res - bino[n-a[ii]][i];
}
return res;
}
Если вы ищете способ получения лексикографического индекса или ранга уникальной комбинации, тогда ваша проблема подпадает под биномиальный коэффициент. Биномиальный коэффициент решает проблемы выбора уникальных комбинаций в группах из K с общим количеством N элементов.
Я написал класс на C# для обработки общих функций для работы с биномиальным коэффициентом. Он выполняет следующие задачи:
Выводит все K-индексы в хорошем формате для любого N, выбирают K в файл. K-индексы могут быть заменены более описательными строками или буквами.
Преобразует K-индексы в соответствующий лексикографический индекс или ранг записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерации. Это достигается с помощью математического свойства, присущего треугольнику Паскаля, и является очень эффективным по сравнению с итерацией по множеству.
Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы. Я считаю, что это также быстрее, чем старые итеративные решения.
Использует метод Марка Домина для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполняется и работает с большими числами.
Класс написан на.NET C# и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое при значении true создаст общий список для хранения управляемых объектов. Если это значение равно false, таблица не будет создана. Таблицу не нужно создавать, чтобы использовать 4 вышеуказанных метода. Методы доступа предоставляются для доступа к таблице.
Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с 2 случаями, и никаких известных ошибок нет.
Чтобы прочитать об этом классе и загрузить код, см. Таблизацию биномиального коэффициента.
Следующий проверенный код будет перебирать каждую уникальную комбинацию:
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);
}
}
Вы должны быть в состоянии довольно легко перенести этот класс на язык по вашему выбору. Вам, вероятно, не придется портировать через общую часть класса для достижения ваших целей. В зависимости от количества комбинаций, с которыми вы работаете, вам может потребоваться использовать больший размер слова, чем 4 байта.