Сортировка списка наборов питонов по значению

Question

Документы Frozenset говорят:

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

Тем не менее, документы для наборов Python говорит:

Поскольку наборы определяют только частичное упорядочение (отношения подмножеств), выходные данные метода list.sort() для списков наборов не определены.

Это заставляет меня спросить: почему так? И, если я хочу отсортировать список наборов по содержимому набора, как я могу это сделать? Я знаю, что расширение intbitset: https://pypi.python.org/pypi/intbitset/2.3.0, имеет функцию для возврата битовой последовательности, которая представляет собой установленное содержимое. Есть ли что-то сопоставимое для наборов питонов?

Answer 1

Кортежи, списки, строки и т. Д. Имеют естественный лексикографический порядок и могут быть отсортированы, потому что вы всегда можете сравнить два элемента данной коллекции. То есть либо a < b, b < a, или же a == b,

Естественное сравнение между двумя наборами имеет a <= b имею в виду a это подмножество b, что такое выражение a <= b на самом деле делает в Python. Под "частичным заказом" в документации подразумевается, что не все наборы сопоставимы. Взять, к примеру, следующие наборы:

a = {1, 2, 3}
b = {4, 5, 6}

Является a подмножество b? Нет b подмножество a? Нет. Они равны? Нет. Если вы не можете сравнить их вообще, вы явно не можете их отсортировать.

Единственный способ, которым вы можете отсортировать коллекцию наборов, - это если ваша функция сравнения действительно может сравнивать любые два элемента ( общий порядок). Это означает, что вы все еще можете сортировать коллекцию наборов, используя вышеуказанное отношение подмножеств, но вы должны будете убедиться, что все наборы сопоставимы (например, [{1}, {1, 2, 4}, {1, 2}]).

Самый простой способ сделать то, что вы хотите, это преобразовать каждый отдельный набор в нечто, что вы на самом деле можете сравнить. В основном вы делаете f(a) <= f(b) (где <= очевидно) для некоторой простой функции f, Это сделано с key Ключевой аргумент:

In [10]: def f(some_set):
   ...       return max(some_set)
   ...

In [11]: sorted([{1, 2, 3, 999}, {4, 5, 6}, {7, 8, 9}], key=f)
Out[11]: [{4, 5, 6}, {7, 8, 9}, {1, 2, 3, 999}]

Ты сортируешь [f(set1), f(set2), f(set3)] и применяя полученный порядок к [set1, set2, set3],

Answer 2

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

Более того, list.sort() сортирует список на месте, используя только < оператор между элементами.

Если вы просто используете a.sort() без прохождения key параметр, говоря set_a < set_b (или же set_a.__lt__(set_b)) недостаточно. Под недостаточным я имею в виду, что set_a.__lt__(set_b) является оператором подмножества. (Является a подмножество b?). Как упоминалось @Blender и упоминалось в вашем вопросе, это обеспечивает частичное, а не полное упорядочение, что недостаточно для определения того, какая последовательность содержит наборы.

Из документов:

set < other: Проверить, является ли набор подходящим подмножеством других, то есть set <= other а также set != other,

Вы могли бы передать key в sort(), он просто не может ссылаться на что-либо, связанное с "упорядочением" наборов внутри, потому что помните - их нет.

>>> a = {2, 3, 1}
>>> b = {6, 9, 0, 1}
>>> c = {0}
>>> i = [b, a, c]
>>> i.sort(key=len)
>>> i
[{0}, {1, 2, 3}, {0, 9, 6, 1}]