1

Всем привет

вопрос касается не API и механизмов языка, а алгоритмов

вкратце формулировка у неё следующая: у нас есть два множества, между которыми есть отображение. Оно может быть инъективным и/или сюръективным. Нужно определить, возможно ли выделить из заданного множества связей подмножество, соответствующее биекции

если ближе к предметике, то первое множество - это актуальные значения, второе - ожидаемые. Порядок следования для обоих множеств значения не имеет. Для ожидаемых прописана операция, применив которую к актуальному мы получим булевское значение. Например, actual="abc" operation="endsWith" expected="c" выдаст true: actual является прообразом expected. И вот у нас есть два таких множества одинакового размера, и нам нужно установить, отображаются ли они друг в друга биективно. Единственный рабочий вариант, который пока у меня есть - это брутфорсить. Но не хотелось бы. Можно ли установить по каким-либо критериям возможность выделения биективного отображения без перебора всех возможных вариантов? (Например, критерий "каждый элемент обоих множеств должен иметь минимум одну связь" необходим, но недостаточен, а проверять, мапится ли каждый прообраз из actual на свой образ в expected - это уже брутфорс). Может быть, есть какие-то теоремы, опираясь на которые, можно построить алгоритм? С удовольствием бы почитал что-нибудь по этой теме

Спасибо

8
  • 1
    какой размер множества? Так-то задача о паросочетании... Алгоритмы простые, сложность около линейной в случайных графах.
    – pavel
    15 фев 2018 в 14:40
  • в основном ожидаются небольшие, не более 10 значений, но в принципе возможны и на 1000+ 15 фев 2018 в 14:42
  • 1
    Чтобы отображение было биективно необходимо и достаточно, чтобы оно было инъективно (т.е. разные элементы исходного множества отображаются на разные элементы целевого множества) и сюръективно (т.е. все элементы целевого множества могут быть получены из исходного множества) 15 фев 2018 в 14:54
  • 1
    Если, как Вы говорите, оба множества одного размера, то сюръективность автоматически будет означать и инъективность, иначе никак :)
    – Yaant
    15 фев 2018 в 15:26
  • 1
    Ну, мы же сейчас говорим про случай, когда мощности множеств (пусть А и B) совпадают. Если каждый элемент B является образом по крайней мере одного одного элемента A, значит мощность прообраза B (назовем его С) должна быть не меньше мощности B: |C| >= |B|, при этом, с одной стороны С является подмножеством А, т. е. |C| <= |A|, а с другой, |A| = |B|. Отсюда следует, что |C| = |A|, а поскольку речь о конечных множествах, то C = A..
    – Yaant
    15 фев 2018 в 17:26

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Посмотрите другие вопросы с метками или задайте свой вопрос.