Как создать отсортированный список элементов на основе нескольких списков отсортированных элементов?

Question

Я пытаюсь получить отсортированный основной список из небольших списков.Это может быть в Python или R.

в R, у меня есть

l1<-c("a","c","d")
l2<-c("a","b","e")
l3<-c("a","c","e")
l4<-c("a","b","c","e")
l5<-c("b","c","d")

m<-unique(c(l1,l2,l3,l4,l5))

Результат, который я ожидал, равен a,b,c,d,e.

В python

l1=["a","c","d"]
l2=["a","b","e"]
l3=["a","c","e"]
l4=["a","b","c","e"]
l5=["b","c","d"]

ожидаемый результат - ["a","b","c","d","e"] Я начал с создания набора, просмотра каждого списка и проверки по индексу, но он стал сложным.

Спасибо за помощь.

РЕДАКТИРОВАТЬ: Я думаю, что я перепутал вас с сортировкой по алфавиту.Эти элементы списка могут быть случайными.реальный заказ не может быть a,b,c,d,e.

l1=["e","a"]
l2=["e","b","d"]
l3=["b","d","a"]

в этом случае ожидаемый порядок: ["e","b","d","a"], а не ["a","b","d","e"]

, для большей ясности, подумайте о том, как мало людей пытаются назвать штаты США с востока на запад.

person 1 says, Florida, Louisiana, Nevada,California. 
person 2 says  Alabama, Mississippi, Louisiana, new Mexico, Nevada 
person 3 says Florida, Alabama, Texas, New Mexico, California
person 4 says Alabama, Mississippi, Texas, Nevada
person 5 says Mississippi Louisiana, Nevada

и я пытаюсь получить правильный порядок из информации выше.

Итак, здесь мы начнем с Florida, Louisiana, Nevada, California.Теперь, добавив второе, это будет (Alabama, Florida),Louisiana,New Mexico, Nevada, California. Добавление 3-го (разрывает связь Алабама / Флорида) Florida, Alabama, Louisiana, Texas, New Mexico, Nevada, California и добавление 4-го делает Florida, Alabama, (Mississippi/Louisiana), Texas, New Mexico, Nevada, California.добавив 5-й перерыв связать Миссисипи и Луизианы.

Answer 1

Ааа а фактический ответ: https://www.python.org/doc/essays/graphs/

Удачной охоты!: D

Это должно сделать это для вашего исходного вопроса:

l1=["a","c","d"]
l2=["a","b","e"]
l3=["a","c","e"]
l4=["a","b","c","e"]
l5=["b","c","d"]

s = set()
s.update(l1, l2, l3, l4, l5)
l = sorted(s)
l
#['a', 'b', 'c', 'd', 'e']

Для вашего отредактированного вопроса, давайте рассмотрим небольшое изменение вашего второго примера:

l1=["e","a"]
l2=["e","b","d"]
l3=["b","c","a"]

(Squint at l3.) В этом случае набор списков недоопределен, так как не существует уникального порядка между d и c.Без правила определения связей никакой алгоритм невозможен.

Answer 2

Для Python:

# Create list of lists
lsts = [l1, l2, l3, l4, l5]
s = set()

# Add lists to set
for lst in lsts:
  s.update(lst)

# Sort set
sorted(s)

Редактировать После обновления OP:

def sort_lists(lsts):
  list_of_hashes = []
  for lst in lsts:
    list_of_hashes.append({k: v for v, k in enumerate(lst)})

  result_hash = dict()
  for hash_item in list_of_hashes:
    for key, value in hash_item.items():
      if result_hash.get(key):
        result_hash[key] += value
      else:
        result_hash[key] = value
  print(result_hash)
  sorted_results = sorted(result_hash.items(), key=lambda kv: kv[1])
  print(sorted_results)
  return [tup[0] for tup in sorted_results]

# Test Case 1
l1=["e","a"]
l2=["e","b","d"]
l3=["b","d","a"]

print(sort_lists([l1,l2,l3]))
>> ['e', 'd', 'b', 'a']

# Test Case 2
s1 = ['Florida', 'Louisiana', 'Nevada', 'California']
s2 = ['Alabama', 'Mississippi', 'Louisiana', 'New Mexico', 'Nevada']
s3 = ['Florida', 'Alabama', 'Texas', 'New Mexico', 'California']
s4 = ['Alabama', 'Mississippi', 'Texas', 'Nevada']
s5 = ['Mississippi', 'Louisiana', 'Nevada']
print(sort_lists([s1,s2,s3,s4,s5]))
>> ['Florida', 'Alabama', 'Mississippi', 'Louisiana', 'Texas', 'New Mexico', 'California', 'Nevada']

Answer 3

Вот подход в R, который превращает векторы в ориентированный ациклический граф с использованием tidygraph, а затем использует node_topo_order для получения подразумеваемого порядка узлов.Используя ваш пример состояния с востока на запад:

l1 <- c("Florida", "Louisiana", "Nevada", "California")
l2 <- c("Alabama", "Mississippi", "Louisiana", "New Mexico", "Nevada" )
l3 <- c("Florida", "Alabama", "Texas", "New Mexico", "California")
l4 <- c("Alabama", "Mississippi", "Texas", "Nevada")
l5 <- c("Mississippi", "Louisiana", "Nevada")

library(tidyverse)
library(tidygraph)
ew_graph <- list(l1, l2, l3, l4, l5) %>%
  map_dfr(~tibble(east = ., west = lead(.))) %>% # turn vectors into edge table
  filter(!is.na(west)) %>%
  as_tbl_graph()

ew_graph %>%  # Now we can order nodes and extract their names as output
  arrange(node_topo_order()) %>%
  pull(name)
#> [1] "Florida"     "Alabama"     "Mississippi" "Louisiana"   "Texas"      
#> [6] "New Mexico"  "Nevada"      "California"

Обратите внимание, что может быть более одного правильного ордера, и это вернет только один из них.Если мы хотим, мы можем также построить график, чтобы увидеть отношения более четко, что показывает, что в этих данных у нас есть связь между Луизианой и Техасом (вы не можете проследить от одного к другому), которую вы пропустили при построениипример.Просто так получается, что у нас они в «истинном» порядке.Если вам необходимо определить отдельный способ разрыва связей, этот подход потребует некоторого взлома.

library(ggraph)
ggraph(ew_graph) +
  geom_node_label(aes(label = name)) +
  geom_edge_link(
    mapping = aes(start_cap = label_rect(node1.name),
                  end_cap = label_rect(node2.name)),
    arrow = arrow(length = unit(4, 'mm'))
  )

^{Создано в 2019-05-28 пользователем представляет пакет (v0.3.0)}

Answer 4

Мое решение имеет сложность O (n) . Другие решения могут иметь O (n log n):

Python: (для R это похоже)

l1=["a","c","d"]
l2=["a","b","e"]
l3=["a","c","e"]
l4=["a","b","c","e"]
l5=["b","c","d"]

lsts = [l1, l2, l3, l4, l5]

solve = []
for p in range(130):
    solve.append(0)

for lst in lsts:
    for p in lst:
        solve[ord(p)] += 1

for idx, value in enumerate(solve):
    if value != 0:
        print chr(idx)

Это решение основано на значениях из таблицы ascii.

Для вашего обновления:

l1=["z","c","d"]
l2=["a","b","e"]
l3=["a","c","e"]
l4=["a","b","c","e"]
l5=["b","c","d"]

mySet = set()

mySet.update(l1, l2, l3, l4, l5)

result = sorted(mySet)
print(result)