LF>можно этот набор охарактеризовать одним числом Q, так чтобы при подстановке в какую-либо
LF>функцию этого полученного числа и числа из заданного множества получалось True — остальных чисел — False ?

Попытаться придумать какую-нибудь хэш-функцию?
В какой-то книжке было описано, как Doug McIlroy (?) из Bell Labs придумал, как сохранить весь словарь английский слов (для проверки орфографии), отведя на хранение каждого слова только 1 бит.

есть, например, множество 6ти разрядных целых чисел (произвольной длины)

Х[] = (
123456,
012983,
239047,
023945,
934857,
394857,...)


можно этот набор охарактеризовать одним числом Q, так чтобы при подстановке в какую-либо
функцию этого полученного числа и числа из заданного множества получалось True — остальных чисел — False ?
что-то типа:

Q = Code(X);

int a = 999999;

if (Test(a, Q)){
// число принадлежит множеству Х
} else {
// число НЕ принадлежит множеству Х
}

Как это можно сделать ?
Как можно реализовать ф-ии Code и Test ?

Спасибо

Здравствуйте, LameFox, Вы писали:

LF>Как это можно сделать ?
LF>Как можно реализовать ф-ии Code и Test ?

Ну в общем случае — нет. Например, если a & b == 0 для каждой пары чисел, то функция будет | (or).

Здравствуйте, LameFox, Вы писали:

LF>есть, например, множество 6ти разрядных целых чисел (произвольной длины)

LF>Х[] = (
LF>123456,
LF>012983,
LF>239047,
LF>023945,
LF>934857,
LF>394857,...)


LF>можно этот набор охарактеризовать одним числом Q, так чтобы при подстановке в какую-либо
LF>функцию этого полученного числа и числа из заданного множества получалось True — остальных чисел — False ?
Всего множеств сколько? 2^(10^6). Число Q — идентификатор множества (т.е. по нему можно множество восстановить). Значит число Q должно иметь 10^6 бит информации, т.е. в простейшем случае быть от 0 до 2^(10^6)-1.
2^(10^6) ~ 10^(3*10^5), т.е. всего 300Кб

Что можно сделать.
1. Подумать все ли множества допустимы. Может число и поменьше окажется.
2. Наложить более мягкие условия на Q, типа

if (Test(a, Q)){
// число принадлежит множеству Х
} else {
// требуется более детальная проверка
}

3. Попытаться найти в множестве закономерности, которыми можно воспользоваться.

Здравствуйте, LameFox, Вы писали:

LF>есть, например, множество 6ти разрядных целых чисел (произвольной длины)

LF>[...]

LF>можно этот набор охарактеризовать одним числом Q, так чтобы при подстановке в какую-либо
LF>функцию этого полученного числа и числа из заданного множества получалось True — остальных чисел — False ?

Конечно можно!
Но число это должно быть длиной 1 млн бит.

Здравствуйте, Tan4ik, Вы писали:


T>2. Наложить более мягкие условия на Q, типа

Можно отменить условие однозначного разделения множеств.
Т.е. Test(a, Q) возвращает 100% True если число принадлежит множеству Х
и с вероятностью, допустим 10% что True возвращено для другого числа.
Главная проблема задачи, что разрядность Q не должно сильно превышать разрядность чисел множества.
и разрядность должна быть фиксированной.
Т.е. в 3 раза — допустимо, 30 раз — нет

Здравствуйте, LameFox, Вы писали:

T>>2. Наложить более мягкие условия на Q, типа

LF>Можно отменить условие однозначного разделения множеств.
LF>Т.е. Test(a, Q) возвращает 100% True если число принадлежит множеству Х
LF>и с вероятностью, допустим 10% что True возвращено для другого числа.
LF>Главная проблема задачи, что разрядность Q не должно сильно превышать разрядность чисел множества.
LF>и разрядность должна быть фиксированной.
LF>Т.е. в 3 раза — допустимо, 30 раз — нет
Думаю в такой формулировке без дополнительных данных задача неразрешима.

Здравствуйте, Ranger_XL, Вы писали:


LF>>можно этот набор охарактеризовать одним числом Q, так чтобы при подстановке в какую-либо
LF>>функцию этого полученного числа и числа из заданного множества получалось True — остальных чисел — False ?

R_X>Попытаться придумать какую-нибудь хэш-функцию?
R_X>В какой-то книжке было описано, как Doug McIlroy (?) из Bell Labs придумал, как сохранить весь словарь английский слов (для проверки орфографии), отведя на хранение каждого слова только 1 бит.
Что за книжка ? Можно поподробнее плиз

А>Что за книжка ? Можно поподробнее плиз

Если не ошибаюсь, книжка Бентли "Жемчужины программирования"