Как я могу назначить уникальное значение для представления списка уникальных целых - PullRequest
Новая
       50

Как я могу назначить уникальное значение для представления списка уникальных целых

0 голосов
/ 23 сентября 2019

Мне нужно сравнить два списка уникальных целых чисел, назначив каждому списку уникальное значение для представления его целых чисел.Какой метод / алгоритм я могу применить для этого, который не слишком сложен в вычислениях и генерирует относительно короткий идентификатор / хэш для набора

Оба списка:

  • имеют уникальный набор целых чисел в диапазоне отОт 1 до 1000
  • заказываются

Например: 

l1 = [1,2,3,4...55,57...999]
l2 = [1,2,3,4...54,56...999]

l1 отсутствует 56, а l2 отсутствует 55. Все, что мне нужно знать в этом случаеявляется то, что списки не идентичны, поэтому я могу обновить l2.

Ответы [ 2 ]

0 голосов
/ 27 сентября 2019

Обновлено после комментария

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

Однако хеш-код может быть полезным.Предполагая, что вы создаете хэш-код для каждого списка.Вы захотите убедиться, что вы сортируете элементы в списках перед вычислением хеш-кода, потому что порядок определенно имеет значение при вычислениях хеш-кода.Это не обязательно генерирует уникальный хэш-код для каждого списка, но если хэш-коды для двух списков не идентичны, списки определенно отличаются.Если хэш-коды идентичны, списки могут быть идентичны.Код выглядит следующим образом: 

bool AreListsIdentical(list1, list2)
{
    if (list1.hashCode != list2.hashCode)
    {
        // hash codes are different, so lists are definitely not identical
        return false;
    }
    // hash codes are equal. Lists might be identical.
    if (list1.Count != list2.Count)
    {
        // lists have different numbers of items. Definitely not identical.
        return false;
    }
    // have to compare individual items
    for (int i = 0; i < list1.Count; ++i)
    {
        if (list1[x] != list2[x])
        {
            return false;
        }
    }
    return true;
}

Предыдущий ответ

У вас есть несколько списков, каждый из которых содержит уникальные номера в диапазоне от 1 до1000.Вы не говорите, насколько велик каждый список, но для иллюстрации я скажу, что каждый список содержит 10 чисел.

Вы также не говорите, имеет ли значение порядок в списке.Список [1,7,99,206] совпадает с [99,7,206,1]?Я покажу вам расчеты в любом случае.

Количество перестановок (порядок вопросов) из 1000 предметов, взятых по 10 за раз, составляет 9,56E + 29.Количество комбинаций (порядок не имеет значения) составляет 2.63E + 23.Это огромные цифры.

Вы говорите, что хотите «относительно короткий идентификатор».Мы можем легко выразить 64-битное значение в 12-символьной строке, поэтому давайте предположим, что вы хотите создать 64-битный хэш-код.Существует 1.84E + 18 возможных 64-битных значений.

Возможных перестановок в сто триллионов раз больше, чем возможных хеш-кодов.В 100 000 раз больше комбинаций, чем хеш-кодов.

Применяя принцип Pigeonhole , у вас есть n вещей, которые вы хотите поместить в m коробки.Так как n> m , по крайней мере, одна коробка будет содержать более одного элемента. Вы не можете иметь уникальное 64-битное значение для каждого списка.

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

0 голосов
/ 27 сентября 2019

Вы не упоминаете язык программирования, но что-то вроде этого (псевдокод): 

int32 ListHash(int[] List, int HashLimit)
{
  int32 result = List[0];
  for (int i = 1; i < length(List); i++)
  {
    result = (result >> 31) | (result << 1); // rotate one bit
    result = result ^ List[i]; // xor with current value
  }
  return (result % HashLimit);
}

может работать для вас.

...