code高尔夫：多重排序的列表合并成一个单一的排序列表 [英] Code golf: combining multiple sorted lists into a single sorted list

问题描述

实施一种算法来合并排序的列表的任意数量成一个有序表。这样做的目的是创造最小的工作程序，在任何一种语言，你喜欢的。

Implement an algorithm to merge an arbitrary number of sorted lists into one sorted list. The aim is to create the smallest working programme, in whatever language you like.

例如：

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)

注意：这串联输入列表，然后使用一种语言提供的排序功能的解决方案不在，符合高尔夫运动的精神，将不被接受：

Note: solutions which concatenate the input lists then use a language-provided sort function are not in-keeping with the spirit of golf, and will not be accepted:

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

二话不说，你的算法的应该的（但不一定是）快了很多！

Apart from anything else, your algorithm should be (but doesn't have to be) a lot faster!

清楚地说明了语言，任何弱点和字符计数。只有包括在计数有意义的角色，但随意添加空格到code的艺术/可读性目的。

Clearly state the language, any foibles and the character count. Only include meaningful characters in the count, but feel free to add whitespace to the code for artistic / readability purposes.

要保持整洁，提出改进意见，或通过编辑答案在适当情况下，而不是创建一个新的答案为每一个修订版本。

To keep things tidy, suggest improvement in comments or by editing answers where appropriate, rather than creating a new answer for each "revision".

修改：如果我再次提交这个问题，我会在之类没有提供语言的规则是不串接所有列表，然后对结果进行分类展开。这做现有条目串联，然后排序实际上是非常有趣和紧凑，所以我不会复古，积极引进他们打破规则，但随时合作，在新提交的更严格的规范。

EDIT: if I was submitting this question again, I would expand on the "no language provided sort" rule to be "don't concatenate all the lists then sort the result". Existing entries which do concatenate-then-sort are actually very interesting and compact, so I won't retro-actively introduce a rule they break, but feel free to work to the more restrictive spec in new submissions.

---

灵感<一href="http://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python">http://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python

推荐答案

Common Lisp中已经有一个合并函数的语言标准通用序列，但它仅适用于两个序列。对于数字的多个列表排序ascendingly，它可以在下面的功能可以使用（97必需字符）。

Common Lisp already has a merge function for general sequences in the language standard, but it only works on two sequences. For multiple lists of numbers sorted ascendingly, it can be used in the following function (97 essential characters).

(defun m (&rest s)
  (if (not (cdr s))
      (car s)
      (apply #'m
             (cons (merge 'list (car s) (cadr s) #'<)
                   (cddr s))))) 

修改的：经过一段时间重温：这可以在同一行中完成的：

edit: Revisiting after some time: this can be done in one line:

(defun multi-merge (&rest lists)
  (reduce (lambda (a b) (merge 'list a b #'<)) lists))

这有79有意义的名称本质特征，减少这些单个字母，它出来的61：

This has 79 essential characters with meaningful names, reducing those to a single letter, it comes out at 61:

(defun m(&rest l)(reduce(lambda(a b)(merge 'list a b #'<))l))

这篇关于code高尔夫：多重排序的列表合并成一个单一的排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！