Доказать гипотезу.

[gris]

Изменение массива удвоит количество числовых сравнений, но уж или место, или время. Золотое правило.
С умножениями и прочими многочленами такая беда: вдруг числа очень большие, на грани формата. И что делать?

[ewert]

gris в сообщении #621360 писал(а):

Изменение массива удвоит количество числовых сравнений

Ничего не увеличит -- ведь проверка булевского массива тоже подразумевает сравнение. Хуже того: поскольку при этом обращаться придётся к дополнительному участку памяти -- время за счёт использования булевского массива только увеличится (если не вдаваться в детали архитектуры процессора).

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

[Xaositect]

Cash в сообщении #621359 писал(а):

Достаточно ли этого теоретически?

Теоретически необходимо $n$ алгебраически независимых симметрических многочленов.

[Евгений Машеров]

У Вас проверяется восемь условий. А Вы хотите обойтись проверкой трёх или четырёх.

[Sender]

Кстати, можно ли как-то быстро вычислить $N$ элементарных симметрических многочленов? В голову приходят только способы со сложностью $O(N^2)$.

[Maslov]

Евгений Машеров в сообщении #621366 писал(а):

У Вас проверяется восемь условий. А Вы хотите обойтись проверкой трёх или четырёх.

На мой взгляд, чисто теоретически в целочисленном случае достаточно проверки одного условия. Что-нибудь типа
$\sum\limits_{k=1}^8 9^{a_k} = \sum\limits_{k=1}^8 9^{b_k}$
Но на практике такой подход, естественно, неприменим.

[Cash]

Цитата:

Теоретически необходимо $n$ алгебраически независимых симметрических многочленов

В общем случае, да.
Но ведь у нас же данные - целочисленные. Неужели это нисколько не меняет дело?

[Xaositect]

Cash в сообщении #621461 писал(а):

В общем случае, да.
Но ведь у нас же данные - целочисленные. Неужели это нисколько не меняет дело?

Ну, можно упаковать все в одно целое число. А вообще, если переменная умеет хранить $2^n$ значений, то для однозначного восстановления однго из $C_{2^n}^8$ сочетаний потребуется не меньше $7$ переменных при $n\geq 8$ и $8$ переменных при $n\geq 16$.

[alexo2]

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

[_Ivana]

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

[main.c]

Задача состоит в том, чтобы дать ответ, можно ли из второго массива получить первый, путём перестановки его элементов. Сортировать запрещается.
Ну в общем-то я уже сделал её, так как мою гипотезу безжалостно опровергли пришлось делать по другому: считаю количество нулей в одном и другом массиве, если не совпадает сразу ответ "нет", а иначе начинаю цикл, беру первый элемент массива, если ноль, беру следующий, если нет, то считаю сколько раз этот элемент встречается в обоих массивах, одновременно с этим обнуляю эти элементы, проверяю, совпадает ли количество, если совпадает берём следующий элемент, если нет, сразу ответ "нет", ну и так проверяю все элементы.

[ewert]

main.c в сообщении #621573 писал(а):

иначе начинаю цикл, беру первый элемент массива, если ноль, беру следующий, если нет, то считаю сколько раз этот элемент встречается в обоих массивах,

Зачем сколько раз-то?...

Как только для очередного ненулевого элемента первого массива встречается равный ему элемент второго -- тот элемент второго надо обнулить и перейти к следующему ненулевому элементу первого массива. И как только такой встречи не случилось -- всё, совпадения нет. А если удалось пройти первый массив до конца, так и не наткнувшись на невстречу -- значит, совпадение.

Мой предыдущий вариант с манипуляцией знаками подразумевал ровно то же самое, только в качестве маркера использовался знак, а не нулёвость. Достоинство знакового подхода: возможность при необходимости восстановить исходные массивы без потери памяти и при этом практически без потери скорости. Недостаток: вдвое уменьшается допустимый диапазон входных данных; но -- всего лишь вдвое.

----------------------------
Истчо Пыс. Это темо -- явно алгоритмическое, и место ей -- откровенно не в математике, а в компьютерных разделах. Это к сведению модераторов.

[Евгений Машеров]

Ну,я бы сказал, что тут есть математическая сторона вопроса и алгоритмическая. Математическая - можно ли сравнить два набора из n чисел с точностью до перестановки (мультимножества?), проверив менее чем n условий. Для вещественных чисел ответ довольно тривиален - нет, нельзя. Для целых чисел, ограниченных по диапазону значений, ответ неясен. Полагаю, тоже нельзя. Но контрпример с ходу не нарисую. Алгоритмическая же - как лучше всего организовать проверку. И она действительно уместна в другом форуме.

[ИСН]

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

-- Пт, 2012-09-21, 21:47 --

Или Вы имели в виду, что все доступные нам переменные ограничены, так что собрать такое число не выйдет?

[Евгений Машеров]

Можно. Скажем, значения 8 симметрических многочленов, приписанные один за другим. Но ни в какую разрядную сетку не влезут...