доброго времени суток
необходим эффективный алгоритм сравнения массивов целых элементов. задача, собственно, в том, чтобы сделать выборку только из различных массивов
первое, что приходит в голову - поэлементное сравнение, но их(массивов) 2^2^n, по 2^n элементов в каждом
думаю, нужно посчитать какую-нибудь численную характеристику(навроде суммы всех элементов) и по ней сравнивать. сумма и среднее отпадает, т.к. сумма почти везде одинаковая, а отличаются массивы в основном порядком элементов. напр.:
4 2 2 2 4 2 2 2
2 2 2 2 2 2 4 4

Добавлено через 14 минут и 10 секунд
в общем, подумал, и переформулирую вопрос - какая есть(если есть) уникальная численная характеристика последовательности чисел?

И что вы хотите получить от результата сравнения?

Значение числа, которое получается, если воспринимать ряд чиел как последовательность цифр числа по соотв. основанию.

А вообще - учитесь формулировать свои мысли. Ибо из остального ни хрена не понять...

элементарно - одинаковые они или нет. если да - то пропуск, если нет - положить в двумерный массив результатов, с которыми, соб-но и нужно сравнивать

Добавлено через 2 минуты и 41 секунду

сорри, просто сплю уже(((

Добавлено через 4 минуты
все, понял, спасибо

Я так понял, вы хотите выполнить попарное сравнение всех массивов и выбрать уникальные - так?

Это сообщение отредактировал(а) DarkProg - 9.10.2011, 17:16

да, так

Добавлено @ 17:32
ну или не совсем так)
алгоритм примерно такой:
получаем новый массив
сравниваем его с множеством предыдущих
если он уникальный - кладем в множество, иначе - идем дальше

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


Это сообщение отредактировал(а) dengalf - 9.10.2011, 17:32

Можно в качестве хэш-функции брать скалярное произведение массива на линейку Голомба соответствующей длины. Если сложно и/или упорядочиваемые массивы вещественнозначны - просто на случайный вектор (естественно, один и тот же). Естественно, массивы с одинаковыми хэш-суммами надо дополнительно проверять на одинаковость.

Каким образом - от этого можно понять что проще реализовать?

массивы это абсолютные значения коэффициентов уолша

Если потребовать, ответата на вопрос 
массивы отличаются меньше чем на 1 процент данных или больше чем на 2 процента, то задача имеет решение в терминах вероятностных алгоритмов за константное время

А ну тогда вы их вычисляете, значит, вариант



 самый рациональный в данном случае