Common sorted list

Common sorted list is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given an integer array nums, the goal is create common sorted list with unique elements.

Example

nums = [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]

output = [1,3,4,5,7,8,9]

AppleScript

<lang applescript>use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later use framework "Foundation"

local nums, output

set nums to current application's class "NSArray"'s arrayWithArray:({{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}}) set output to (nums's valueForKeyPath:("@distinctUnionOfArrays.self"))'s sortedArrayUsingSelector:("compare:") return output as list</lang>

Output:

<lang applescript>{1, 3, 4, 5, 7, 8, 9}</lang>

Or, as a composition of slightly more commonly-used generic functions (given that distinctUnionOfArrays is a relatively specialised function, while concat/flatten and nub/distinct are more atomic, and more frequently reached for):

<lang applescript>use AppleScript version "2.4" use framework "Foundation"

---

COMMON SORTED ARRAY ------------------

on run

   sort(nub(concat({¬
       {5, 1, 3, 8, 9, 4, 8, 7}, ¬
       {3, 5, 9, 8, 4}, ¬
       {1, 3, 7, 9}})))

end run

---

GENERIC FUNCTIONS -------------------

-- concat :: a -> [a] on concat(xs)

   ((current application's NSArray's arrayWithArray:xs)'s ¬
       valueForKeyPath:"@unionOfArrays.self") as list

end concat

-- nub :: [a] -> [a] on nub(xs)

   ((current application's NSArray's arrayWithArray:xs)'s ¬
       valueForKeyPath:"@distinctUnionOfObjects.self") as list

end nub

-- sort :: Ord a => [a] -> [a] on sort(xs)

   ((current application's NSArray's arrayWithArray:xs)'s ¬
       sortedArrayUsingSelector:"compare:") as list

end sort</lang>

Output:

{1, 3, 4, 5, 7, 8, 9}

AutoHotkey

<lang AutoHotkey>Common_sorted_list(nums){

   elements := [], output := []
   for i, num in nums
       for j, d in num
           elements[d] := true
   for val, bool in elements
       output.push(val)
   return output

}</lang> Examples:<lang AutoHotkey>nums := [[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]] output := Common_sorted_list(nums) return</lang>

Output:

[1, 3, 4, 5, 6, 7, 9]

AWK

<lang AWK>

1. syntax: GAWK -f COMMON_SORTED_LIST.AWK

BEGIN {

   PROCINFO["sorted_in"] = "@ind_num_asc"
   nums = "[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9]"
   printf("%s : ",nums)
   n = split(nums,arr1,"],?") - 1
   for (i=1; i<=n; i++) {
     gsub(/[\[\]]/,"",arr1[i])
     split(arr1[i],arr2,",")
     for (j in arr2) {
       arr3[arr2[j]]++
     }
   }
   for (j in arr3) {
     printf("%s ",j)
   }
   printf("\n")
   exit(0)

} </lang>

Output:

[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9] : 1 3 4 5 7 8 9

F#

<lang fsharp> // Common sorted list. Nigel Galloway: February 25th., 2021 let nums=[|[5;1;3;8;9;4;8;7];[3;5;9;8;4];[1;3;7;9]|] printfn "%A" (nums|>Array.reduce(fun n g->n@g)|>List.distinct|>List.sort) </lang>

Output:

[1; 3; 4; 5; 7; 8; 9]

Factor

Note: in older versions of Factor, union-all is called combine.

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: formatting kernel sets sorting ;

{ { 5 1 3 8 9 4 8 7 } { 3 5 9 8 4 } { 1 3 7 9 } } dup union-all natural-sort "Sorted union of %u is:\n%u\n" printf</lang>

Output:

Sorted union of { { 5 1 3 8 9 4 8 7 } { 3 5 9 8 4 } { 1 3 7 9 } } is:
{ 1 3 4 5 7 8 9 }

Go

Translation of: Wren

<lang go>package main

import (

   "fmt"
   "sort"

)

func distinctSortedUnion(ll [][]int) []int {

   var res []int
   for _, l := range ll {
       res = append(res, l...)
   }
   set := make(map[int]bool)
   for _, e := range res {
       set[e] = true
   }
   res = res[:0]
   for key := range set {
       res = append(res, key)
   }
   sort.Ints(res)
   return res

}

func main() {

   ll := [][]int{{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}}
   fmt.Println("Distinct sorted union of", ll, "is:")
   fmt.Println(distinctSortedUnion(ll))

}</lang>

Output:

Distinct sorted union of [[5 1 3 8 9 4 8 7] [3 5 9 8 4] [1 3 7 9]] is:
[1 3 4 5 7 8 9]

Julia

<lang julia> julia> sort(union([5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9])) 7-element Array{Int64,1}:

1
3
4
5
7
8
9

julia> sort(union([2, 3, 4], split("3.14 is not an integer", r"\s+")), lt=(x, y) -> "$x" < "$y") 8-element Array{Any,1}:

2
3
 "3.14"
4
 "an"
 "integer"
 "is"
 "not"

</lang>

Perl

<lang perl>@c{@$_}++ for [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]; print join ' ', sort keys %c; @c{@$_}++ for [qw<not all is integer ? is not ! 4.2>]; print join ' ', sort keys %c;</lang>

Output:

1 3 4 5 7 8 9
! 1 3 4 4.2 5 7 8 9 ? all integer is not

Phix

<lang Phix>?unique(join({{5,1,3,8,9,4,8,7}, {3,5,9,8,4}, {1,3,7,9}, split("not everything is an integer")},{}))</lang> Note the join(x,{}): the 2nd param is needed to prevent it putting 32 (ie the acsii code for a space) in the output.

Output:

(Unexpectedly rather Yoda-esque)

{1,3,4,5,7,8,9,"an","everything","integer","is","not"}

Python

<lang python>Common sorted list

from itertools import chain

1. ------------------------- TEST -------------------------
2. main :: IO ()

def main():

   Sorted union of lists

   print(
       sorted(nub(concat(
           [
               [5, 1, 3, 8, 9, 4, 8, 7],
               [3, 5, 9, 8, 4],
               [1, 3, 7, 9]
           ]
       )))
   )

1. ----------------------- GENERIC ------------------------

1. concat :: a -> [a]
2. concat :: [String] -> String

def concat(xs):

   The concatenation of all the elements in a list.
   
   return list(chain(*xs))

1. nub :: [a] -> [a]

def nub(xs):

   A list containing the same elements as xs,
      without duplicates, in the order of their
      first occurrence.
   
   return list(dict.fromkeys(xs))

1. MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

[1, 3, 4, 5, 7, 8, 9]

Raku

<lang perl6>put sort keys [∪] [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]; put sort keys [∪] [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9], [<not everything is an integer so why not avoid special cases # ~ 23 4.2>];</lang>

Output:

1 3 4 5 7 8 9
# 1 3 4 4.2 5 7 8 9 23 an avoid cases everything integer is not so special why ~

REXX

<lang rexx>/*REXX pgm creates and displays a common sorted list of a specified collection of sets*/ parse arg a /*obtain optional arguments from the CL*/ if a= | a="," then a= '[5,1,3,8,9,4,8,7] [3,5,9,8,4] [1,3,7,9]' /*default sets.*/ x= translate(a, ,'],[') /*extract elements from collection sets*/ se= words(x)

1. = 0; $= /*#: number of unique elements; $: list*/

$= /*the list of common elements (so far).*/

   do j=1  for se;  _= word(x, j)               /*traipse through all elements in sets.*/
   if wordpos(_, $)>0  then iterate             /*Is element in the new list? Yes, skip*/
   $= $ _;   #= # + 1;    @.#= _                /*add to list; bump counter; assign──►@*/
   end   /*j*/

$= call eSort # /*use any short (small) exchange sort.*/

                do k=1  for #;   $= $  @.k      /*rebuild the $ list, it's been sorted.*/
                end   /*k*/

say 'the list of sorted common elements in all sets: ' "["translate(space($), ',', " ")']' exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ eSort: procedure expose @.; arg h 1 z; do while h>1; h= h%2; do i=1 for z-h; j= i; k= h+i

       do while @.k<@.j; t=@.j; @.j=@.k; @.k=t; if h>=j then leave; j=j-h; k=k-h; end;end
       end;     return                          /*this sort was used 'cause of brevity.*/</lang>

output   when using the default inputs:

the list of sorted common elements in all sets:  [1,3,4,5,7,8,9]

Ring

<lang ring> nums = [[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9]] sumNums = []

for n = 1 to len(nums)

   for m = 1 to len(nums[n])
       add(sumNums,nums[n][m])
   next

next

sumNums = sort(sumNums) for n = len(sumNums) to 2 step -1

   if sumNums[n] = sumNums[n-1]
      del(sumNums,n)
   ok

next

sumNums = sort(sumNums)

see "common sorted list elements are: " showArray(sumNums)

func showArray(array)

    txt = ""
    see "["
    for n = 1 to len(array)
        txt = txt + array[n] + ","
    next
    txt = left(txt,len(txt)-1)
    txt = txt + "]"
    see txt

</lang>

Output:

common sorted list elements are: [1,3,4,5,7,8,9]

Wren

Library: Wren-seq

Library: Wren-sort

<lang ecmascript>import "/seq" for Lst import "/sort" for Sort

var distinctSortedUnion = Fn.new { |ll|

   var res = ll.reduce([]) { |acc, l| acc + l }
   res = Lst.distinct(res)
   Sort.insertion(res)
   return res

}

var ll = [[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]] System.print("Distinct sorted union of %(ll) is:") System.print(distinctSortedUnion.call(ll))</lang>

Output:

Distinct sorted union of [[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]] is:
[1, 3, 4, 5, 7, 8, 9]