code_junkie

Code golf: combining multiple sorted lists into a single sorted list

Nov 13th, 2011
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.06 KB | None | 0 0
  1. input: ((1, 4, 7), (2, 5, 8), (3, 6, 9))
  2. output: (1, 2, 3, 4, 5, 6, 7, 8, 9)
  3.  
  4. input: ((1, 10), (), (2, 5, 6, 7))
  5. output: (1, 2, 5, 6, 7, 10)
  6.  
  7. sorted(sum(lists,[])) # cheating: out of bounds!
  8.  
  9. (defun multi-merge (&rest lists)
  10. (reduce (lambda (a b) (merge 'list a b #'<)) lists))
  11.  
  12. (defun multi-merge (&rest lists)
  13. (reduce (lambda (a b) (merge 'list a b #'<)) lists))
  14.  
  15. (defun m(&rest l)(reduce(lambda(a b)(merge 'list a b #'<))l))
  16.  
  17. let f=List.fold_left(List.merge compare)[]
  18.  
  19. def m(i)
  20. a=[]
  21. i.each{|s|s.each{|n|a.insert((a.index(a.select{|j|j>n}.last)||-1)+1,n)}}
  22. a.reverse
  23. end
  24.  
  25. def sorted_join(numbers)
  26. sorted_numbers=[]
  27.  
  28. numbers.each do |sub_numbers|
  29. sub_numbers.each do |number|
  30. bigger_than_me = sorted_numbers.select { |i| i > number }
  31. if bigger_than_me.last
  32. pos = sorted_numbers.index(bigger_than_me.last) + 1
  33. else
  34. pos = 0
  35. end
  36.  
  37. sorted_numbers.insert(pos, number)
  38. end
  39. end
  40.  
  41. sorted_numbers.reverse
  42. end
  43.  
  44. a = [[1, 4, 7], [2, 4, 8], [3, 6, 9]]
  45. n = 50000
  46. Benchmark.bm do |b|
  47. b.report { n.times { m(a) } }
  48. b.report { n.times { a.flatten.sort } }
  49. end
  50.  
  51. user system total real
  52. 2.940000 0.380000 3.320000 ( 7.573263)
  53. 0.380000 0.000000 0.380000 ( 0.892291)
  54.  
  55. def m(i):
  56. y=[];x=sum(i,[])
  57. while x:n=min(x);y+=[n];x.remove(n)
  58. return y
  59.  
  60. >>> m([[1,5],[6,3]])
  61. [1, 3, 5, 6]
  62.  
  63. def m(c,l):
  64. try:
  65. c += [l[min((m[0], i) for i,m in enumerate(l) if m)[1]].pop(0)]
  66. return m(c,l)
  67. except:
  68. return c
  69.  
  70. # called as:
  71. >>> m([], [[1,4], [2,6], [3,5]])
  72. [1, 2, 3, 4, 5, 6]
  73.  
  74. max_ = 2**31-1
  75. def f(N):
  76. L = random.sample(xrange(max_), n)
  77. L.sort()
  78. return L
  79. f.__name__ = "sorted_random_%d" % max_
  80.  
  81. $ git clone git://gist.github.com/51074.git
  82.  
  83. m l|all null l=[]
  84. |True=x:(m$a++(xs:b))
  85. where
  86. n=filter(not.null)l
  87. (_,min)=minimum$zip(map head n)[0..]
  88. (a,((x:xs):b))=splitAt min n
  89.  
  90. L[99][99];N;n[99];m[99];i;I;b=0;main(char t){while(scanf("%d%c",L[i]+I,&t)+1){++
  91. I;if(t==10){n[i++]=I;I=0;}}if(I)n[i++] = I;N=i;while(b+1){b=-1;for(i=0;i<N;++i){
  92. I=m[i];if(I-n[i])if(b<0||L[i][I]<L[b][m[b]])b=i;}if(b<0)break;printf("%d ",L[b][
  93. m[b]]);++m[b];}puts("");}
  94.  
  95. 1 4 7
  96. 2 5 8
  97. 3 6 9
  98. (EOF)
  99.  
  100. let p l=
  101. let f a b=List.filter(a b) in
  102. let rec s=function[]->[]|x::y->s(f(>)x y)@[x]@s(f(<=)x y) in
  103. [for a in l->>a]|>s
  104.  
  105. let golf l=
  106. // filters my list with a specified filter operator
  107. // uses built-in F# function
  108. // ('a -> 'b -> bool) -> 'a -> ('b list -> 'b list)
  109. let filter a b = List.filter(a b)
  110.  
  111. // quicksort algorithm
  112. // ('a list -> 'a list)
  113. let rec qsort =function
  114. | []->[]
  115. | x :: y -> qsort ( filter (>) x y) @ [x] @ qsort ( filter (<=) x y)
  116.  
  117. // flattens list
  118. [for a in l ->> a ] |> qsort
  119.  
  120. function merge(a) {
  121. var r=[], p;
  122. while(a.length>0) {
  123. for (var i=0,j=0; i<a.length && p!=a[j][0]; i++)
  124. if (a[i][0]<a[j][0])
  125. j = i;
  126.  
  127. r.push(p = a[j].shift());
  128.  
  129. if (!a[j].length)
  130. a.splice(j, 1);
  131. }
  132. return r;
  133. }
  134.  
  135. var arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]​;
  136. alert(merge(arr));
  137.  
  138. Dim m1 As List(Of Integer) = New List(Of Integer)
  139. Dim m2 As List(Of Integer) = New List(Of Integer)
  140. Dim m3 As List(Of Integer) = New List(Of Integer)
  141. Dim m4 As List(Of Integer) = New List(Of Integer)
  142.  
  143. m1.Add(1)
  144. m1.Add(2)
  145. m1.Add(3)
  146.  
  147. m2.Add(4)
  148. m2.Add(5)
  149. m2.Add(6)
  150.  
  151. m3.Add(7)
  152. m3.Add(8)
  153. m3.Add(9)
  154.  
  155. Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
  156. m5.Add(m1)
  157. m5.Add(m2)
  158. m5.Add(m3)
  159.  
  160. While m5.Count > 0
  161. Dim idx As Integer = 0
  162. Dim min As Integer = Integer.MaxValue
  163. For k As Integer = 0 To m5.Count - 1
  164. If m5(k)(0) < min Then min = m5(k)(0) : idx = k
  165. Next
  166. m4.Add(min) : m5(idx).RemoveAt(0)
  167. If m5(idx).Count = 0 Then m5.RemoveAt(idx)
  168. End While
  169.  
  170. Private Function Comp(ByVal l1 As List(Of Integer), ByVal l2 As List(Of Integer)) As Integer
  171. Return l1(0).CompareTo(l2(0))
  172. End Function
  173. .
  174. .
  175. .
  176. While m5.Count > 0
  177. m5.Sort(AddressOf Comp)
  178. m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
  179. If m5(0).Count = 0 Then m5.RemoveAt(0)
  180. End While
  181.  
  182. Dim rand As New Random
  183. Dim m1 As List(Of Integer) = New List(Of Integer)
  184. Dim m2 As List(Of Integer) = New List(Of Integer)
  185. Dim m3 As List(Of Integer) = New List(Of Integer)
  186. Dim m4 As List(Of Integer) = New List(Of Integer)
  187. Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
  188. m5.Add(m1)
  189. m5.Add(m2)
  190. m5.Add(m3)
  191.  
  192. For Each d As List(Of Integer) In m5
  193. For i As Integer = 0 To 100000
  194. d.Add(rand.Next())
  195. Next
  196. d.Sort()
  197. Next
  198.  
  199. Dim sw As New Stopwatch
  200. sw.Start()
  201. While m5.Count > 0
  202. Dim idx As Integer = 0
  203. Dim min As Integer = Integer.MaxValue
  204. For k As Integer = 0 To m5.Count - 1
  205. If m5(k)(0) < min Then min = m5(k)(0) : idx = k
  206. Next
  207. m4.Add(min) : m5(idx).RemoveAt(0)
  208. If m5(idx).Count = 0 Then m5.RemoveAt(idx)
  209. End While
  210. sw.Stop()
  211.  
  212. 'Dim sw As New Stopwatch
  213. 'sw.Start()
  214. 'While m5.Count > 0
  215. ' m5.Sort(AddressOf Comp)
  216. ' m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
  217. ' If m5(0).Count = 0 Then m5.RemoveAt(0)
  218. 'End While
  219. 'sw.Stop()
  220.  
  221. Console.WriteLine(sw.Elapsed)
  222. Console.ReadLine()
  223.  
  224. def merge_sort(arrs)
  225. o = Array.new
  226. arrs.each do |a|
  227. o = o | a
  228. end
  229. o.sort!
  230. end
  231.  
  232. arrs = [ [ 90, 4, -2 ], [ 5, 6, -100 ], [ 5, 7, 2 ] ]
  233. merge_sort(arrs)
  234.  
  235. static void f(params int[][] b)
  236. {
  237. var l = new List<int>();
  238. foreach(var a in b)l.AddRange(a);
  239. l.OrderBy(i=>i).ToList().ForEach(Console.WriteLine);
  240. }
  241. static void Main()
  242. {
  243. f(new int[] { 1, 4, 7 },
  244. new int[] { 2, 5, 8 },
  245. new int[] { 3, 6, 9 });
  246. }
  247.  
  248. let f x=List.sort(List.concat x)
  249.  
  250. let f x=List.sort(Seq.toList(seq{for l in x do yield!l}))
  251.  
  252. import heapq
  253. def m(i):
  254. return list(heapq.merge(*i))
  255.  
  256. print m(((1, 4, 7), (2, 5, 8), (3, 6, 9)))
  257.  
  258. import heapq
  259. def m(i): return list(heapq.merge(*i))
  260.  
  261. sub a{sort map{@$_}@_}
  262.  
  263. my @sorted = a([1, 2, 3], [5, 6, 89], [13, -1, 3]);
  264. print "@sorted" # prints -1, 1, 1, 2, 3, 3, 5, 6, 89
  265.  
  266. l1.merge(l2); // Removes the elements from the argument list, inserts
  267. // them into the target list, and orders the new, combined
  268. // set of elements in ascending order or in some other
  269. // specified order.
  270.  
  271. sort -m file1 file2 file3 ...
  272.  
  273. # This merges two lists together
  274. m(){
  275. [[ -z $1 ]] && echo $2 && return;
  276. [[ -z $2 ]] && echo $1 && return;
  277. A=($1); B=($2);
  278. if (( ${A[0]} > ${B[0]} ));then
  279. echo -n ${B[0]} ;
  280. unset B[0];
  281. else
  282. echo -n ${A[0]} ;
  283. unset A[0];
  284. fi;
  285. m "${A[*]}" "${B[*]}";
  286. }
  287. # This merges multiple lists
  288. M(){
  289. A=$1;
  290. shift;
  291. for x in $@; do
  292. A=`m "$A" "$x"`
  293. done
  294. echo $A
  295. }
  296.  
  297. $ M '1 4 7' '2 5 8' '3 6 9'
  298. 1 2 3 4 5 6 7 8 9
  299.  
  300. Function s(i)
  301.  
  302. s=New List(Of Byte)
  303.  
  304. Dim m,c
  305. Dim N=Nothing
  306.  
  307. Do
  308. m=N
  309. For Each l In i:
  310. If l.Count AndAlso(l(0)<m Or m=N)Then m=l(0):c=l
  311.  
  312. Next
  313.  
  314. If m<>N Then s.Add(m):c.Remove(m)
  315.  
  316. Loop Until m=N
  317.  
  318. End Function
  319.  
  320. def f(l):
  321. n=[]
  322. for t in l:
  323. for i in t: n+=[t]
  324. s=[]
  325. while n: s.+=[min(n)]; n.remove(min(n))
  326. return s
  327.  
  328. Sub Main()
  329. f(New Int32() {1, 4, 7}, _
  330. New Int32() {2, 5, 8}, _
  331. New Int32() {3, 6, 9})
  332. End Sub
  333.  
  334. Sub f(ByVal ParamArray b As Int32()())
  335. Dim l = New List(Of Int32)
  336. For Each a In b
  337. l.AddRange(a)
  338. Next
  339. For Each a In l.OrderBy(Function(i) i)
  340. Console.WriteLine(a)
  341. Next
  342. End Sub
  343.  
  344. from heapq import *
  345. def m(l):
  346. r=[]
  347. h=[]
  348. for x in l:
  349. if x:
  350. heappush(h, (x[0], x[1:]))
  351. while h:
  352. e,f=heappop(h)
  353. r.append(e)
  354. if f:
  355. heappush(h, (f.pop(0),f))
  356. return r
Add Comment
Please, Sign In to add comment