Код гольф: объединение нескольких отсортированных списков в один отсортированный список - PullRequest
Новая
       75

Код гольф: объединение нескольких отсортированных списков в один отсортированный список

9 голосов
/ 21 января 2009

Реализовать алгоритм для объединения произвольного количества отсортированных списков в один отсортированный список. Цель состоит в том, чтобы создать самую маленькую рабочую программу на любом языке, который вам нравится.

Например: 

input:  ((1, 4, 7), (2, 5, 8), (3, 6, 9))
output: (1, 2, 3, 4, 5, 6, 7, 8, 9)

input:  ((1, 10), (), (2, 5, 6, 7))
output: (1, 2, 5, 6, 7, 10)

Примечание : решения, которые объединяют входные списки, а затем используют предоставляемую языком функцию сортировки, не соответствуют духу гольфа и не будут приняты: 

sorted(sum(lists,[])) # cheating: out of bounds!

Помимо всего прочего, ваш алгоритм должен быть (но не должен быть) намного быстрее!

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

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

РЕДАКТИРОВАТЬ : если бы я снова отправлял этот вопрос, я бы расширил правило «сортировка без языка», чтобы «не объединять все списки, а сортировать результат». Существующие записи, которые выполняют конкатенацию-затем-сортировку, на самом деле очень интересны и компактны, поэтому я не буду активно вводить правило, которое они нарушают, но не стесняюсь работать с более ограничительной спецификацией в новых представлениях.

Вдохновлен Объединение двух отсортированных списков в Python

Ответы [ 26 ]

0 голосов
/ 22 февраля 2010
0 голосов
/ 20 июня 2009

Системные скрипты GNU (я полагаю, это обман, но тоже приятно знать). 

sort -m file1 file2 file3 ...
0 голосов
/ 21 января 2009

Не думаю, что вы можете стать намного лучше, чем ответ @ Sykora , здесь , для Python.

Изменено для обработки ваших входов: 

import heapq
def m(i): 
    return list(heapq.merge(*i))

print m(((1, 4, 7), (2, 5, 8), (3, 6, 9)))

Для действительной функции, 59 символов или 52 в сокращенной версии: 

import heapq
def m(i): return list(heapq.merge(*i))

Это также дает преимущество использования проверенной и настоящей реализации, встроенной в Python

Редактировать: Удалены точки с запятой (спасибо @ Дуглас ).

0 голосов
/ 29 января 2009

Даже если это может нарушить правила. Вот хорошая и короткая запись c ++ :

13 символов 

l1.merge(l2); // Removes the elements from the argument list, inserts 
              // them into the target list, and orders the new, combined 
              // set of elements in ascending order or in some other 
              // specified order.
0 голосов
/ 27 января 2009

VB

Настройка: 

Sub Main()
    f(New Int32() {1, 4, 7}, _
      New Int32() {2, 5, 8}, _
      New Int32() {3, 6, 9})
End Sub

Выход: 

Sub f(ByVal ParamArray b As Int32()())
    Dim l = New List(Of Int32)
    For Each a In b
        l.AddRange(a)
    Next
    For Each a In l.OrderBy(Function(i) i)
        Console.WriteLine(a)
    Next
End Sub
0 голосов
/ 25 января 2009

Python, 181 символ 

from heapq import *
def m(l):
 r=[]
 h=[]
 for x in l:
  if x:
   heappush(h, (x[0], x[1:]))
 while h:
  e,f=heappop(h)
  r.append(e)
  if f:
   heappush(h, (f.pop(0),f))
 return r

Это выполняется за время O (NlgM), где N - общее количество элементов, а M - количество списков.

Страница:
...