Симметрическая разность n множеств

[VAL]

Xaositect в сообщении #741688 писал(а):

Мне стало очень любопытно, зачем это потребовалось в программе. Я в математике-то эту операцию всего несколько раз встречал.

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

[Dext]

Xaositect в сообщении #741688 писал(а):

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

Вроде бы, я уже понял

То есть для [-1,0,2,16,17],[-1,2,7],[-5,-5,0,2,8],[-1,2,8] симметр. разность равна [-5,-1,7,16,17] ?

Xaositect в сообщении #741688 писал(а):

Мне стало очень любопытно, зачем это потребовалось в программе. Я в математике-то эту операцию всего несколько раз встречал.

Вкратце, для обработки данных. Кода немерено.


P.S. Похоже всё-таки для реальных нужд "по Munin'у" придётся переделать

[VAL]

Dext в сообщении #741693 писал(а):

То есть для [-1,0,2,16,17],[-1,2,7],[-5,-5,0,2,8],[-1,2,8] симметр. разность равна [-5,-1,7,16,17] ?

А зачем Вам повторяющиеся элементы во множестве?
И почему Вы перечисляете элементы в квадратных скобках? Так обычно обозначают упорядоченные наборы.

[Dext]

VAL в сообщении #741703 писал(а):

А зачем Вам повторяющиеся элементы во множестве?

Они могут быть в массиве множестве на входе.

VAL в сообщении #741703 писал(а):

И почему Вы перечисляете элементы в квадратных скобках? Так обычно обозначают упорядоченные наборы.

По привычке. В квадратных скобках в некоторых языках программирования записываются массивы.

[VAL]

Dext в сообщении #741705 писал(а):

VAL в сообщении #741703 писал(а):

А зачем Вам повторяющиеся элементы во множестве?

Они могут быть в массиве множестве на входе.

Тогда это не множества. И классическая симметрическая разность тут неприменима.
Стало быть, надо определять операцию, специально для этого случая. Например, $-5$ из Вашего предыдущего примера, скорее всего не должно попадать в ответ. Впрочем, не зная постановки решаемой вами задачи, утверждать ничего не берусь.

Цитата:

VAL в сообщении #741703 писал(а):

И почему Вы перечисляете элементы в квадратных скобках? Так обычно обозначают упорядоченные наборы.

По привычке. В квадратных скобках в некоторых языках программирования записываются массивы.

. Но массивы - это совсем не множества. И даже не мультимножества.

[Dext]

VAL в сообщении #741715 писал(а):

VAL в сообщении #741703 писал(а):

И почему Вы перечисляете элементы в квадратных скобках? Так обычно обозначают упорядоченные наборы.

Цитата:

По привычке. В квадратных скобках в некоторых языках программирования записываются массивы.

Но массивы - это совсем не множества. И даже не мультимножества.

Мне нужно над массивами делать такие же операции (некоторые), как и над множествами.

[VAL]

Dext в сообщении #741719 писал(а):

Мне нужно над массивами делать такие же операции (некоторые), как и над множествами.

Но сначала надо определиться.

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

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

Если же $-5$ должно попасть в ответ, то у Вас не мультимножества, а множества. Но тогда во входных операндах не должно быть повторов (их следует отсекать на стадии формирования).

[Dext]

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


P.S. Помогите с http://dxdy.ru/post741729.html

[VAL]

Dext в сообщении #741731 писал(а):

P.S. Помогите с http://dxdy.ru/post741729.html

Посмотрел.
Для оценки сложности чего-то недостаточно: то ли данных, то ли моего понимания задачи.

[arseniiv]

VAL в сообщении #741724 писал(а):

Но тогда во входных операндах не должно быть повторов (их следует отсекать на стадии формирования).

Почему? Это не обязательно, представление может быть любым, лишь бы операции были реализованы соответствующе. Возможное повторение элементов в массиве, представляющем множество, в некоторых случаях сильно не мешает.

[Munin]

А я ещё третий вариант придумал:
в ответ входят все элементы, которые входят хотя бы в одно множество, но не входят во все множества.

Обобщение определения "объединение минус пересечение".

[VAL]

arseniiv в сообщении #741736 писал(а):

VAL в сообщении #741724 писал(а):

Но тогда во входных операндах не должно быть повторов (их следует отсекать на стадии формирования).

Почему? Это не обязательно, представление может быть любым, лишь бы операции были реализованы соответствующе. Возможное повторение элементов в массиве, представляющем множество, в некоторых случаях сильно не мешает.

Если входные структуры обрабатываются именно как множества, а не как мультимножества (настолько я понял ТС, дело обстоит именно так), то зачем тратить память и время на обработку избыточных данных? IMHO, проще отсекать лишнее на стадии формирования данных.
Впрочем, повторяю, не зная всю задачу целиком, сложно делать окончательные выводы.

[Dext]

VAL в сообщении #741751 писал(а):

Если входные структуры обрабатываются именно как множества, а не как мультимножества (настолько я понял ТС, дело обстоит именно так), то зачем тратить память и время на обработку избыточных данных? IMHO, проще отсекать лишнее на стадии формирования данных.
Впрочем, повторяю, не зная всю задачу целиком, сложно делать окончательные выводы.

Пример, когда появляются дубли в массиве и они нужны для алгоритма. Допустим, требуется найти пересечение двух сортированных массивов (без дублей) A и B за линейное время.
Алгоритм (в общем) таков:

1) сливаем входные массивы в один массив C (один цикл, время $O(n+m)$);
2) удаляем в C все элементы кроме тех, которые имеют дубли (один цикл, время $O(n+m)$).

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

[arseniiv]

Можно и не объединяя в третий массив идти вперёд одновременно по обоим входным и выкидывать элементы в выходной, алгоритм как раз похож на слияние с сохранением упорядоченности. Временная сложность, правда, не изменяется никак.