实现一种算法,将任意数量的排序列表合并到一个排序列表中。目的是创建您喜欢的任何语言的最小的工作程序。
例如:
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!
除了其他方面,您的算法应该(但不必一定要)快很多!
清楚地说明语言,任何寓言和字符数。仅在计数中包含有意义的字符,但出于艺术性/可读性的目的,可以随意在代码中添加空格。
为了使内容整洁,建议在评论中进行改进或在适当的地方通过编辑答案,而不是为每个“修订”创建新的答案。
编辑:如果我再次提交此问题,我将扩展“不提供语言排序”规则,即“不要将所有列表连接在一起,然后对结果进行排序”。现有的可以进行“先连接后排序”的条目实际上非常有趣且紧凑,因此,我不会追溯地介绍它们被打破的规则,但可以随意处理新提交的内容中的限制性更强的规范。
灵感来自Combining two sorted lists in Python
最佳答案
Common Lisp在语言标准中已经具有用于常规序列的merge
函数,但仅适用于两个序列。对于升序排列的多个数字列表,可以在以下功能中使用它(97个基本字符)。
(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:
(defun m(&rest l)(reduce(lambda(a b)(merge 'list a b #'<))l))