Как удалить все повторяющиеся вариации?

Question

[jslby]

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

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

Т.е. из этого списка нужно получить такой:
хочу красный мяч
где взять красный мяч
какого цвета красный мяч
красный мяч хочу найти

А удалить следующие словосочетания:
красный мяч хочу - аналог: хочу красный мяч
мяч хочу красный - аналог: хочу красный мяч

Answer 1

[Saboteur]

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

Answer 2

[Владлен Грачев]

Сортировать слова — слишком просто. Можно разбить строку на слова (не забыв привести их к одному регистру). Потом каждое слово хэшировать. Затем полученные хэши складывать (как числа) и сумму использовать в качестве хэша словосочетания. Ну а дальше на выходе объект. По массиву исходных строк пробегаем в цикле, каждую строку добавляет в выходной объект, в качестве ключа используя хэш. Если такой ключ уже использовался, предыдущее значение будет перезаписано. Все выходит элементарно и красиво, однострочное тело цикла уникализации. Попутно не забыть придумать механизм борьбы с коллизиями.

Почему бы и нет?

Comments

[jslby]

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

[Владлен Грачев]

jslby, я не совсем понял ваш подход, но на правильный он не похож. Во-первых, перемешивание у вас случайное? Это не есть хорошо. Тогда надо использовать перестановки (из комбинаторики). При этом для трех слов будет 6 перестановок, а для четырех — уже 24. Это ад дикий.

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

[dtestyk]

можно чтобы не было коллизий взять идеальный хеш

Answer 3

[dtestyk]

Сортировать слова — слишком просто.

Присваиваем каждому слову простое число.
Тогда словосочетание будет их произведением.
Удаляем словосочетания с одинаковыми значениями.
Например, используя их в качестве ключа в хешмапе.