Упорядочение массива для максимальных парных совпадений

Question

У меня есть массив:

array([[ 4, 10],
       [ 4,  2],
       [ 0,  7],
       [ 5, 11],
       [ 6,  8],
       [ 3,  6],
       [ 9,  7],
       [ 2, 11],
       [ 9,  5],
       [ 8,  1]])

Я хочу метод, с помощью которого можно упорядочить пары значений так, чтобы как можно больше парных наборов из 2 элементов имели общее значение.Это пример желаемого упорядоченного массива:

array([[ 4, 10],
       [ 4,  2],
       [ 2, 11],
       [ 5, 11],
       [ 9,  5],
       [ 9,  7],
       [ 0,  7],  #note the gap here:
       [ 8,  1],
       [ 6,  8],
       [ 3,  6]])

Для этих массивов выполняется несколько условий.Дублированных пар нет (то есть: [1,0] и [0,1] не появятся в других местах массива, если [0,1] уже существует).Ни одна пара не имеет такое же значение (то есть: [1,1] не будет существовать).Ни одна пара не будет иметь более двух совпадений (iow: ни одно значение не существует более двух раз во всем массиве.), Но пара может иметь всего лишь несколько совпадений (обратите внимание, что в приведенном выше массиве пробел, между которым нет совпадения).

Очевидно, я могу создать любую перестановку массива, но это кажется грубым.Я думаю, что может быть какой-то способ разрезания колоды и повторной укладки таким образом, чтобы она сортировалась с небольшим количеством разрезов.Но прежде чем идти по этому пути, я хочу: 1) убедиться, что нет функции numpy или collections, которая уже делает это.2) Знайте, что нет хитрого гениального способа использовать numpy .sort() (или подобный) для этого.3) Найдите, является ли это обычной задачей, и существует ли алгоритм, который это делает.(«О, это алгоритм Блюмена-Функе!»)

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

def shuffled(N=12, ans=1):
    '''returns is now the unsorted test array'''
    r = range(N)
    random.shuffle(r)
    l = []
    for i in range(N):
        l.append((r[i-1], r[i]))
    random.shuffle(l)
    return np.array(l)[ans+1:]

# step 2: ???

def test_ordered(a):
    '''checks if generated array has been sorted'''
    c0 = a[1:,0]==a[:-1,0]
    c1 = a[1:,0]==a[:-1,1]
    c2 = a[1:,1]==a[:-1,0]
    c3 = a[1:,1]==a[:-1,1]
    cond = c0+c1+c2+c3
    ans = sum(numpy.logical_not(cond))
    # when sorted this should return the same number input into
    # shuffled() as 'ans':
    return ans

(Это субъективный вопрос? IМеня предупреждают, что это так.)

Результаты:

Большое спасибо за вашу помощь.Решение Свена было примерно на 20% быстрее, чем у Пола, и, к счастью, оба они работают в линейном времени, ответ Дуга не решил проблему.Существовала высокая, но в значительной степени линейная зависимость производительности от количества «разрывов» или «разрывов» во входных данных.Смотрите сюжет ниже.Ось с магнитудой 10000 равна N. Ось 0.5 - это процент разрывов.Ось Z - производительность в секундах.

Еще раз спасибо!

Answer 1

Вы описали график, где вершины - это числа, а ребра - ваши пары.

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

• [Линия существует] Если возможно, выберите число со степенью 1 (то есть, оно появляется в списке только один раз). Следуйте цепочке пар, насколько это возможно, добавляя их к выходным данным и удаляя пройденные вершины из вашего графика.
• [Цикл существует] Если не было числа с степенью 1, это означает, что все компоненты являются циклами. Выберите любую вершину (она будет иметь степень 2). Следуйте парам, как и раньше, добавляя их к выходным данным и удаляя пройденные вершины, но на этот раз остановитесь, когда достигнете своего исходного числа.
• Повторяйте, пока не израсходуете все вершины графа.

Вы можете эффективно запустить этот алгоритм: сохранить набор вершин степени 1, а другой - степени 2. Когда вы используете ребро (пару в исходном списке), измените наборы соответствующим образом: удалите конечную точку степени 1 из первый набор, и переместите конечную точку из установленной степени 2 в набор степени 1. Или используйте очередь с приоритетами.

Вам также понадобится эффективный поиск ваших пар: создайте диктат из вершины в список смежных вершин.

Используя эти идеи, вы можете найти лучший порядок в линейном времени (при условии реализации O (1) set и dict).

Вот несколько неуклюжая реализация.

import collections

def handle_vertex(v, vs):
  if v in vs[0]:
    vs[0].remove(v)
  elif v in vs[1]:
    vs[0].add(v)
    vs[1].remove(v)

def follow(edgemap, start, vs):
  """Follow a path in the graph, yielding the edges."""
  v0 = start
  last = None
  while True:
    # All vertices that we can go to next.
    next_v = [v for v in edgemap[v0] if v != last]
    if not next_v:
      # We've reached the end (we must have been a line).
      return
    assert len(next_v) == 1 or (v0 == start and len(next_v) == 2)
    next_v = next_v[0]
    # Remove the endpoints from the vertex-degree sets.
    handle_vertex(v0, vs)
    handle_vertex(next_v, vs)
    yield v0, next_v
    if next_v == start:
      # We've got back to the start (we must have been a cycle).
      return
    v0, last = next_v, v0

def pairsort(edges):
  edgemap = collections.defaultdict(list)
  original_edges = {}
  for a, b in edges:
    # Build the adjacency table.
    edgemap[a].append(b)
    edgemap[b].append(a)
    # Keep a map to remember the original order pairs appeared in
    # so we can output edges correctly no matter which way round
    # we store them.
    original_edges[a, b] = [a, b]
    original_edges[b, a] = [a, b]
  # Build sets of degree 1 and degree 2 vertices.
  vs = [set(), set()]
  for k, v in edgemap.iteritems():
    vs[len(v) - 1].add(k)
  # Find all components that are lines.
  while vs[0]:
    v0 = vs[0].pop()
    for e in follow(edgemap, v0, vs):
      yield original_edges[e]
  # Find all components that are cycles.
  while vs[1]:
    v0 = vs[1].pop()
    for e in follow(edgemap, v0, vs):
      yield original_edges[e]

input = [
    [ 4, 10],
    [ 4,  2],
    [ 0,  7],
    [ 5, 11],
    [ 6,  8],
    [ 3,  6],
    [ 9,  7],
    [ 2, 11],
    [ 9,  5],
    [ 8,  1]]

print list(pairsort(input))

Answer 2

Я не уверен, что понимаю каждую деталь в вашем вопросе;но если я это сделал, то это должно делать то, что вы хотите.

Основная идея очень проста: для двух одномерных массивов вы можете циклически проходить все попарные комбинации, выстраивая их в ряд, удерживая одну неподвижную и катится второй вперед на один шаг за раз .Если вы используете функцию roll в NumPy, то значения, которые выпадают из конца массива при его движении вперед, просто возвращаются назад, как беговая дорожка.

После того, как это настроено, просто разведите два вектора вдоль правильной оси и сложите 0.Отслеживайте эти суммы ( tx , ниже), затем получите индекс, соответствующий максимальному значению этих сумм, NP.argmax (tx) .

import numpy as NP

# create some data:
c1 = NP.random.randint(0, 10, 15)
c2 = NP.random.randint(0, 10, 15)
c12 = NP.concatenate((c1, c2)).reshape(15, 2)

tx = []    # to hold the indices of the various orderings

for i in range(15) :
    v = NP.diff(c12, axis=0)
    num_equal_neighbors = NP.sum( NP.sum(v==0, axis=0) )
    tx.append(num_equal_neighbors)
    c2 = NP.roll(c2, 1)
    c12[:,1] = c2

Теперь определите, какой порядок двух векторов дает наиболее «парные» совпадения:

best_order = NP.argmax(tx)

, поэтому желаемое упорядочение происходит, когда два одномерных массива расположены так, чтовторой массив свернут * best_order * количество мест (и первый массив оставлен как есть)

Answer 3

Вот более простая реализация в основном того же алгоритма, описанного в Ответ Пола Ханкина , с использованием различных структур данных. Он также работает за линейное время.

edges = [[4, 10], [4,  2], [0,  7], [5, 11], [6,  8],
         [3,  6], [9,  7], [2, 11], [9,  5], [8,  1]]

def add_edge(vertex, adj):
    edge = edges[adj[0]][:]
    ordered_edges.append(edge[:])
    edge.remove(vertex)
    new_vertex = edge[0]
    new_adj = adj_edges[new_vertex]
    new_adj.remove(adj[0])
    del adj[0]
    return new_vertex, new_adj

adj_edges = {}
for i, edge in enumerate(edges):
    for vertex in edge:
        adj_edges.setdefault(vertex, []).append(i)
ordered_edges = []
for vertex, adj in adj_edges.iteritems():
    while len(adj) == 1:
        vertex, adj = add_edge(vertex, adj)
for vertex, adj in adj_edges.iteritems():
    while adj:
        vertex, adj = add_edge(vertex, adj)

Answer 4

Смотри также проблема самого длинного пути : NP завершено для общих графов или кратчайший путь с весами, аннулированными для ациклического. Кроме того, попробуйте график, показанный в Остовное дерево : самый длинный труднее, чем просто длинный.