Примечание: это изменение n-множителей для этой проблемы .
Для заданного набора A, состоящего из десятичных значений от 0,0 до 1,0, найдите набор Bтак, что каждый b в B является набором, состоящим из десятичных значений от 0,0 до 1,0, так что для каждого a в A существует набор уникальных значений, где a является произведениемподмножество элементов в B.
Например, учитывая
$ A = [0.125, 0.25, 0.5, 0.75, 0.9]
Возможное (но, вероятно, не наименьшее) решение для B:
$ B = solve(A)
$ print(B)
[[0.25, 0.5, 0.75, 0.9], [etc.], [etc.]]
Этоудовлетворяет исходной задаче, поскольку A[0] == B[0] * B[1], A[1] == B[1] и т. д., что позволяет воссоздать исходный набор A.Длина B меньше, чем A, но я предполагаю, что есть и меньшие ответы.Тем не менее, предполагая, что B не может быть уменьшено за пределы 4 значений, правильным решением этой проблемы будет набор решений.
Я предполагаю, что пространство решений для B велико, если не бесконечно.Если решение существует, как найти наименьший набор B?
Примечания:
- Похоже, это хорошо вписывается в проблему удовлетворения ограничений, но ямы не смогли выяснить, как он будет отформатирован.
- Мы не ограничены значениями в A. B может состоять из любого набора значений, независимо от того, существуют они в A.
- Нет предела, что можно использовать только два значения из B.Если у вас было
A = [0.125, 0.25, 0.5, 1.0], то правильный ответ для B мог бы быть [0.5, 1.0].Значение, A == [ B[0]*B[0]*B[0], B[0]*B[0], B[0]*B[1], B[1]*B[1] ] - Поскольку математика с плавающей запятой, как правило, проблематична, рациональные числа, вероятно, являются хорошей идеей.
- Нижний предел решений в
B будет |B| ≥ log2(|A| + 1), поскольку мы можемиметь не более 2^|B| - 1 непустых подмножеств B.(За это גלעד ברקן .)