Установить преобразование

Question

Я ищу способ трансформировать сет, и у меня возникли проблемы.Это потому, что требования довольно строгие.

Набор A содержит набор целых чисел, детали действительно не имеют значения.
Набор B содержит набор целых чисел, например:

• Каждое значение в A напрямую отображается на одно и только одно значение в B.
• Каждый бит имеет значение true в одном и только одном значении в B.
• Сумма любых N значенийв B имеет строгое отношение к (сумме) его исходных значений в A. Это отношение может не зависеть от знания фактических значений N, о которых идет речь, хотя другие вещи, такие как знание количества суммируемых значений, хороши.

Это в основном мысленное упражнение, а не фактическая реализация, поэтому подробно описываются реалии, например, ограничений памяти, которые будут сильно увеличиваться с размером A.

Например, вы можете удовлетворитьПервые два требования, просто сказав, что B [i] = 2 ^ A [i].Но это бесполезно, потому что если вы сделали 2 ^ x = 2 ^ A [i] + 2 ^ A [j], вы не сможете сделать вывод, что сумма A [i] и A [j] равна x или некоторому другомувыражение, которое не включает A [i] или A [j].

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

Редактировать: мне было неясно.Сожалею.Эта идея существует главным образом в моей голове.

Я уже знаю сумму значений B.Проблема в том, что я начинаю с суммы значений B и нахожу значения в B, которые суммируются, что тривиально из-за ограничения уникальных битов.Проблема в том, что сумма первоначально выражается в значениях A, поэтому я должен иметь возможность преобразовать сумму из суммы значений A в сумму значений B.Это бесполезно для меня, если мне придется преобразовывать его отдельно для каждой возможной суммы, потому что преобразование зависит от значений, которые я суммирую.

Дополнительная правка: Кроме того, мой механизм реверса из B [i] в ​​A [я] это таблица поиска.Не нужно реально существующей математической функции.Любой A [i] уникален среди любого другого A [j].

Answer 1

Проблема в том, что сумма первоначально выражается в значениях A, поэтому я должен иметь возможность преобразовать сумму из суммы значений A в сумму значений B.

Это означает нахождение значений A из суммы значений A, что я не считаю возможным, если значения A являются произвольными.

РЕДАКТИРОВАТЬ: Как вы это описали,эта проблема, кажется, является проблемой суммы подмножеств , которая является NP-полной.Вы можете использовать динамическое программирование, чтобы улучшить его производительность, но я не знаю, сможете ли вы пойти намного дальше.

Answer 2

Учитывая (A_1 + ... + A_n), можем ли мы считать, что каждый A_i уникален?Если нет, проблема невозможна: добавление A_1 к себе A_2 раз дает тот же результат, что и добавление A_2 к себе A_1 раз.Если каждый A_i уникален, то что мы можем предположить о биекции между A и B?Например, если известно N, то A [i] = B [i] + d тривиально обратимо для всех d.Даже если мы можем предположить, что каждый A_i в сумме уникален, проблема восстановления B_i возможна, если (и только если) нет двух подмножеств A суммы с одинаковым значением.Насколько легко можно восстановить B_i, зависит от характера биекции.

Answer 3

Я думаю, что ваше третье ограничение создает проблему.Когда вы говорите, что A взаимно однозначно с B, это означает, что существует обратимое отображение F: A->B и его обратное F': B->A такое, что F'(F(x))=x.Теперь «сумма любых N значений в B строго связана с суммой исходных значений в A».Это означает, что существует некоторое G такое, что G(A_1+A_2+...+A_n)=B_1+B_2+...+B_n;сумма B-значений связана с A-значениями.Но из-за первого предложения мы установили, что A_1=F'(B_1), поэтому «знание фактических значений N, о которых идет речь» (A_1 through A_n, хотя ваш первоначальный вопрос оставляет неоднозначным, к каким значениям вы обращаетесь), равнозная "B-значения, из-за взаимно-однозначного соответствия.Таким образом, невозможно выполнить ограничения один и три одновременно для конечного набора целых чисел;если вы получили указание «суммировать эти n B-значений», вы должны уже знать A-значения - просто примените обратное преобразование.