Сортировка списка пар по частоте парных элементов

Question

Я совершенно новичок в Python и, пробуя различные случайные фрагменты, натолкнулся на проблему, которую, как мне кажется, я "решил", но код не не чувствует себя правильным -Я сильно подозреваю, что будет лучший способ получить желаемый результат.

К вашему сведению - я использую любую последнюю версию Python 3 для Windows.

Определение проблемы

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

Пары находятся в форме[i,j] с 0 <= i <= j < n, где n - известное максимальное значение для элементов.В списке нет повторяющихся пар.

Количество элементов i представляет собой простое число пар (не парных элементов) в формах [i,j], [j,i] и * 1019.* где j - любое значение, которое приводит к действительной паре.

В отсортированном результате пара [i,j] должна появляться перед парой [k,l], если count(i) < count(k) или count(i) == count(k)и count(j) < count(l) (Если count(j) == count(l), то оба могут быть в любом порядке - меня не беспокоит то, что сортировка стабильна, хотя это было бы бонусом).

В отсортированном результатепара [i,j] должна появляться перед парой [k,l], если
min(count(i),count(j)) < min(count(k),count(l)) или
min(count(i),count(j)) == min(count(k),count(l)) и max(count(i),count(j)) < max(count(k),count(l)).
Другими словами, если пара равна [0,1] и 1 имеетсчитается один, но у 0 есть четыреста, пара должна все еще быть (или, по крайней мере, очень близко) впереди списка - им нужна сортировка по наименее частому элементу в паре.

Вот надуманный пример, который я построил:

input   [[0,0],[1,2],[1,4],[2,2],[2,3],[3,3],[3,4]]

Вот количество отдельных элементов и исходные пары, которые они объединяют.e from:

0: 1   [0,0]
1: 2   [1,2],[1,4]
2: 3   [1,2],[2,2],[2,3]
3: 3   [2,3],[3,3],[3,4]
4: 2   [1,4],[3,4]

И вот результат вместе с оценками пары:

output: [[0,0],[1,4],[1,2],[3,4],[2,2],[2,3],[3,3]]
scores:   1     1-2   1-3   2-3   3     3     3

Здесь 0 имеет счетчик один (появляется в один пара, хотя и дважды), поэтому на первом месте.1 имеет число два, поэтому появляется второе - с [1,4] перед [1,2], потому что 4 имеет число два, а 2 имеет число три и так далее.

Myтекущее решение

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

#my implementation uncommented to reduce post size, see history for comments
def sortPairList( data , n ):
    count = []
    for i in range(0,n):
        count.append( 0 )

    #count up the data
    for p in data:
        count[p[0]] += 1
        if p[1] != p[0]:
            count[p[1]] += 1

    maxcount = 0
    for i in range(0,n):
        if count[i] > maxcount:
            maxcount = count[i]

    def elementFrequency(p):
        if count[ p[0] ] < count[ p[1] ]:
            return count[ p[0] ] + float(count[ p[1] ]) / (maxcount+1)
        else:
            return count[ p[1] ] + float(count[ p[0] ]) / (maxcount+1)

    data.sort( key=elementFrequency )

Есть какие-нибудь предложения по более "Python" способу сделать это?
Или что-то не так с моей текущей попыткой?

Новый тестовый пример (см. Комментарии к ответу)

input:    [[0,0],[0,3],[0,5],[0,7],[1,1],[1,2],[1,8],[2,4],[2,5],[3,4],[3,5],[3,9],[4,4],[4,7],[4,8],[6,8],[7,7],[7,9],[8,9]]
expected: [[6,8],[1,1],[1,2],[2,5],[0,5],[1,8],[3,5],[3,9],[7,9],[8,9],[2,4],[0,0],[0,3],[0,7],[7,7],[3,4],[4,7],[4,8],[4,4]]

Answer 1

Я бы, вероятно, использовал Счетчик (нужен Python ≥2.7 или ≥3.1) для подсчета.

from collections import Counter
from itertools import chain
def sortPairList2(data):
    tally = Counter(chain(*map(set, data)))
    data.sort(key=lambda x: sorted(tally[i] for i in x))

Обратите внимание, что:

1. Вы можете создать анонимную функцию с помощью lambda.Например,

   >>> c = 4
   >>> a = lambda p: p - c
   >>> a(7)
   3
   

2. Ключ сортировки не обязательно должен быть числом.Все, что сопоставимо, может быть использовано в качестве возвращаемого значения ключевой функции.В моем коде для заказа используется list.

3. В вашем Python есть много простых идиом для вашего исходного кода.

   • count можно инициализировать с помощью count = [0] * n вместо этого цикла.
   • maxcount можно получить с помощью max с функцией ,maxcount = max(count)

4. Понимание списка часто используется в Python.Если ваша цель состоит в том, чтобы преобразовать итерируемое в другое итерируемое, предпочтите понимание вместо циклов.

Answer 2

>>> n = 4
>>> freqs = {i: sum(i in j for j in inp) for i in range(n+1)}
>>> def key(x):
    a, b = x
    return min(freqs[a], freqs[b]), max(freqs[a], freqs[b])

>>> sorted(inp, key=key)

P.S. Обратите внимание, что input - это недопустимое имя для переменной, поскольку она скрыта для встроенного.

Answer 3

Аналогично решению KennyTM, но для Python 2.5 или выше:

import collections

def sort_by_occurence(sequences):
    tally = collections.defaultdict(int)
    for sequence in sequences:
        for item in sequence:
            tally[item] += 1
    sequences.sort(key=lambda x:map(tally.get, x))


pair_list = [[0,0],[1,2],[1,4],[2,2],[2,3],[3,3],[3,4]]
sort_by_occurence(pair_list)
print pair_list

Answer 4

Пока решение KennyTM работает, я пытался сделать это сам.

Мое решение предварительно вычисляет частоты и сохраняет их в словаре, где str(n) является ключевым.У меня были некоторые проблемы с изменением функции сравнения, известной из Python2, на ключ, используемый в Python3, но я нашел рецепт в код ActiveState

item_cnt = {}

def icount(n):
    return item_cnt[str(n)]

def add_item(n):
    sn = str(n)
    try:
        item_cnt[sn] += 1
    except KeyError:
        item_cnt[sn] = 1

# sort callback
def cmp_items(ij, kl):
    i, j = ij
    k, l = kl
    if icount(i) < icount(k) or icount(i) == icount(k) and icount(j) < icount(l):
        return -1
    return 1

input = [[0,0],[1,2],[1,4],[2,2],[2,3],[3,3],[3,4]]
# count all items
for (i, j) in input:
    add_item(i)
    add_item(j)

# works with Python 2.x
#input.sort(cmp_items)
# works with Python2.6 and Python 3.x
# to convert compare function to key look at:
# http://code.activestate.com/recipes/576653-convert-a-cmp-function-to-a-key-function/
input.sort(key=cmp_to_key(cmp_items))
print(input)