Генерация идентификаторов для набора целых чисел

Question

Справочная информация:

Я работаю с перестановками последовательности целых чисел {0, 1, 2 ..., n}. У меня есть локальный алгоритм поиска, который систематически преобразует перестановку в другую перестановку. Смысл алгоритма заключается в создании перестановки, которая минимизирует функцию стоимости. Я хотел бы работать с широким спектром проблем, от n = 5 до n = 400.

Проблема:

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

Материал, который я пробовал:

Я начал с генерации последовательности из n простых чисел и умножения i-го числа в моей перестановке на i-е простое, после чего суммировал результаты. Результирующий ключ, однако, создает коллизии даже при n = 5.

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

Есть ли у stackoverflow какие-нибудь предложения для меня?

Answer 1

Хеширование Zobrist может работать на вас. Вам нужно создать NxN матрицу случайных целых чисел, каждая ячейка, представляющая этот элемент i, находится в j-й позиции в текущей перестановке. Для данной перестановки вы выбираете N значений ячеек и складываете их по одному для получения ключа перестановки (обратите внимание, что уникальность ключа не гарантируется).

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

Answer 2

Судя по вашему вопросу и оставленным комментариям, я бы сказал, что вашу проблему невозможно решить.

Позвольте мне объяснить.

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

• 1: Требуется уникальный номер для представления комбинации произвольного числа цифр / чисел

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

• 2: невозможно использовать фактические данные, которые использовались для создания хэша, поскольку их больше нет в памяти

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

Извините, но вы не можете этого сделать.

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

Если вы попробуете битовое поле, где каждая комбинация имеет бит, который равен 0, если его не видели, вам все равно потребуется большой объем памяти.

Для перестановки в n = 20, которую вы оставили в комментарии, у вас есть 20! (2 432 902 008 176 640 000) комбинаций, которые, если вы попытаетесь просто сохранить каждую комбинацию как 1-бит в битовом поле, потребуют 276 589 ТБ памяти.

Вам придется ограничить сферу своей деятельности.

Answer 3

Как уже предлагали другие, вы можете использовать хеширование для генерации целого числа, которое будет уникальным с высокой вероятностью. Однако, если вам нужно, чтобы целое число всегда было уникальным, вы должны rank перестановок, то есть назначить им порядок. Например, общим порядком перестановок для набора {1,2,3} является лексикографический порядок:

1. 1,2,3
2. 1,3,2
3. 2,1,3
4. 2,3,1
5. 3,1,2
6. 3,2,1

В этом случае id перестановки - это ее индекс в лексикографическом порядке. Конечно, есть и другие способы ранжирования.

Создание идентификаторов диапазона непрерывных целых чисел позволяет реализовать хранение обработанных перестановок в виде битового поля или логического массива.

Answer 4

Как быстро это должно быть?

Вы всегда можете собрать целые числа в виде строки, затем взять ее хеш, а затем просто получить первые 4 байта.

Для хэша вы можете использовать любую функцию, например, MD5 или SHA-256.

Answer 5

Вы можете MD5 хэшировать строку через запятую, связывающую ваши целые.

В C # это будет выглядеть примерно так (Отказ от ответственности: у меня нет компилятора на машине, которую я использую сегодня):

using System;
using System.Security.Cryptography;
using System.Text;

public class SomeClass {
    static Guid GetHash(int[] numbers) {
        string csv = string.Join(',', numbers);
        return new Guid(new MD5CryptoServiceProvider().ComputeHash(Encoding.ASCII.GetBytes(csv.Trim())));
    }
}

Редактировать: О чем я думал? Как утверждают другие, вам не нужен хеш. CSV должно быть достаточно в качестве строкового идентификатора (если ваш массив чисел не большой).

Answer 6

получить две перестановки из одной и той же серии чисел {1, .., n}, построить набор отображений (id, permutation1 [id], permutation2 [id]) или (id, f1 (id), f2 ( Я бы)); Вы получите уникальную карту по {f3 (id) | для кортежа (id, f1 (id), f2 (id)), из id мы получаем f2 (id) и находим id 'из кортежа (id', f1 (id '), f2 (id')) где f1 (id ') == f2 (id)}

Answer 7

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

Answer 8

Основные силы будут работать: если p_i - это i ^th , простое число и a_i - это i ^th элемент вашего кортежа, тогда

p_0**a_0 * p_1**a_1 * ... * p_n**a_n

должно быть уникальным по Фундаментальной теореме арифметики . Эти цифры станут довольно большими, хотя: -)

(например, для n = 5, (1,2,3,4,5) отобразится в 870 037 764 750, что уже превышает 32 бита)

Answer 9

Не имеет прямого отношения к вопросу, но в качестве альтернативного решения вы можете использовать Три дерева в качестве структуры поиска. Три дерева очень хороши для операций со строками, их реализация относительно проста, и она должна быть более быстрой (максимум n (k), где k - длина ключа), чем хэш-набор для большого количества длинных строк. И вы не ограничены в размере ключа (например, в обычном хэш-наборе в must int, не больше). Введите в вашем случае будет строка всех чисел, разделенных каким-либо символом.

Answer 10

Преобразование каждого числа в строку, объединение строк (через StringBuffer) и получение содержимого StringBuffer в качестве ключа.