Common sorted list: Difference between revisions

Content added Content deleted

Inline

Revision as of 00:22, 25 November 2021

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]

11l

<lang 11l>F csl(nums)

  Set[Int] r
  L(num) nums
     r.update(num)
  R sorted(Array(r))

print(csl([[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]]))</lang>

Output:

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

Action!

Library: Action! Tool Kit

<lang Action!>INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit

DEFINE PTR="CARD"

PROC PrintArray(BYTE ARRAY a BYTE len)

 BYTE i

 Print("  [")
 IF len>0 THEN
   FOR i=0 TO len-1
   DO
     PrintB(a(i))
     IF i<len-1 THEN Put(' ) FI
   OD
 FI
 PrintE("]")

RETURN

BYTE FUNC Contains(BYTE ARRAY a BYTE len,value)

 BYTE i

 IF len>0 THEN
   FOR i=0 TO len-1
   DO
     IF a(i)=value THEN RETURN(1) FI
   OD
 FI

RETURN (0)

PROC CommonListElements(PTR ARRAY arrays

 BYTE ARRAY lengths BYTE count
 BYTE ARRAY res BYTE POINTER resLen)
 
 BYTE ARRAY a
 BYTE i,j,len,value,cnt,maxcnt

 resLen^=0
 IF count=0 THEN
   RETURN
 ELSEIF count=1 THEN
   MoveBlock(res,a,len) RETURN
 FI

 FOR i=0 TO count-1
 DO
   a=arrays(i) len=lengths(i)
   IF len>0 THEN
     FOR j=0 TO len-1
     DO
       value=a(j)
       IF Contains(res,resLen^,value)=0 THEN
         res(resLen^)=value resLen^==+1
       FI
     OD
   FI
 OD
 SortB(res,resLen^,0)

RETURN

PROC Test(PTR ARRAY arrays BYTE ARRAY lengths BYTE count)

 BYTE ARRAY res(100)
 BYTE len,i

 CommonListElements(arrays,lengths,count,res,@len)
 PrintE("Input:")
 FOR i=0 TO count-1
 DO
   PrintArray(arrays(i),lengths(i))
 OD
 PrintE("Output:")
 PrintArray(res,len) PutE()

RETURN

PROC Main()

 PTR ARRAY arrays(3)
 BYTE ARRAY
   lengths(3)=[8 5 4],
   a1(8)=[5 1 3 8 9 4 8 7],
   a2(5)=[3 5 9 8 4],
   a3(4)=[1 3 7 9],
   a4(8)=[5 1 1 1 9 9 8 7],
   a5(5)=[5 5 9 9 9],
   a6(4)=[1 7 7 9]
 BYTE len

 Put(125) PutE() ;clear the screen
 
 arrays(0)=a1 arrays(1)=a2 arrays(2)=a3
 Test(arrays,lengths,3)

 arrays(0)=a4 arrays(1)=a5 arrays(2)=a6
 Test(arrays,lengths,3)

 lengths(0)=0
 Test(arrays,lengths,3)

RETURN</lang>

Output:

Screenshot from Atari 8-bit computer

Input:
  [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]

Input:
  [5 1 1 1 9 9 8 7]
  [5 5 9 9 9]
  [1 7 7 9]
Output:
  [1 5 7 8 9]

Input:
  []
  [5 5 9 9 9]
  [1 7 7 9]
Output:
  [1 5 7 9]

Ada

<lang Ada>with Ada.Text_Io; with Ada.Containers.Vectors;

procedure Sorted is

  package Integer_Vectors is
    new Ada.Containers.Vectors (Index_Type   => Positive,
                                Element_Type => Integer);
  use Integer_Vectors;

  package Vector_Sorting is
    new Integer_Vectors.Generic_Sorting;
  use Vector_Sorting;

  procedure Unique (Vec : in out Vector) is
     Res : Vector;
  begin
     for E of Vec loop
        if Res.Is_Empty or else Res.Last_Element /= E then
           Res.Append (E);
        end if;
     end loop;
     Vec := Res;
  end Unique;

  procedure Put (Vec : Vector) is
     use Ada.Text_Io;
  begin
     Put ("[");
     for E of Vec loop
        Put (E'Image);  Put (" ");
     end loop;
     Put ("]");
     New_Line;
  end Put;

  A : constant Vector := 5 & 1 & 3 & 8 & 9 & 4 & 8 & 7;
  B : constant Vector := 3 & 5 & 9 & 8 & 4;
  C : constant Vector := 1 & 3 & 7 & 9;
  R : Vector          := A & B & C;

begin

  Sort (R);
  Unique (R);
  Put (R);

end Sorted;</lang>

Output:

[ 1  3  4  5  7  8  9 ]

APL

Works with: Dyalog APL

Output:

      csl (5 1 3 8 9 4 8 7)(3 5 9 8 4)(1 3 7 9)
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:

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

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

C

<lang c>#include <stdio.h>

include <stdlib.h>
include <string.h>

define COUNTOF(a) (sizeof(a)/sizeof(a[0]))

void fatal(const char* message) {

   fprintf(stderr, "%s\n", message);
   exit(1);

}

void* xmalloc(size_t n) {

   void* ptr = malloc(n);
   if (ptr == NULL)
       fatal("Out of memory");
   return ptr;

}

int icompare(const void* p1, const void* p2) {

   const int* ip1 = p1;
   const int* ip2 = p2;
   return (*ip1 < *ip2) ? -1 : ((*ip1 > *ip2) ? 1 : 0);

}

size_t unique(int* array, size_t len) {

   size_t out_index = 0;
   int prev;
   for (size_t i = 0; i < len; ++i) {
       if (i == 0 || prev != array[i])
           array[out_index++] = array[i];
       prev = array[i];
   }
   return out_index;

}

int* common_sorted_list(const int** arrays, const size_t* lengths, size_t count, size_t* size) {

   size_t len = 0;
   for (size_t i = 0; i < count; ++i)
       len += lengths[i];
   int* array = xmalloc(len * sizeof(int));
   for (size_t i = 0, offset = 0; i < count; ++i) {
       memcpy(array + offset, arrays[i], lengths[i] * sizeof(int));
       offset += lengths[i];
   }
   qsort(array, len, sizeof(int), icompare);
   *size = unique(array, len);
   return array;

}

void print(const int* array, size_t len) {

   printf("[");
   for (size_t i = 0; i < len; ++i) {
       if (i > 0)
           printf(", ");
       printf("%d", array[i]);
   }
   printf("]\n");

}

int main() {

   const int a[] = {5, 1, 3, 8, 9, 4, 8, 7};
   const int b[] = {3, 5, 9, 8, 4};
   const int c[] = {1, 3, 7, 9};
   size_t len = 0;
   const int* arrays[] = {a, b, c};
   size_t lengths[] = {COUNTOF(a), COUNTOF(b), COUNTOF(c)};
   int* sorted = common_sorted_list(arrays, lengths, COUNTOF(arrays), &len);
   print(sorted, len);
   free(sorted);
   return 0;

}</lang>

Output:

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

C++

<lang cpp>#include <iostream>

include <vector>
include <set>
include <algorithm>

template<typename T> std::vector<T> common_sorted_list(const std::vector<std::vector<T>>& ll) {

   std::set<T> resultset;
   std::vector<T> result;
   for (auto& list : ll)
       for (auto& item : list)
           resultset.insert(item);
   for (auto& item : resultset)
       result.push_back(item);
   
   std::sort(result.begin(), result.end());
   return result;

}

int main() {

   std::vector<int> a = {5,1,3,8,9,4,8,7};
   std::vector<int> b = {3,5,9,8,4};
   std::vector<int> c = {1,3,7,9};
   std::vector<std::vector<int>> nums = {a, b, c};
   
   auto csl = common_sorted_list(nums);
   for (auto n : csl) std::cout << n << " ";
   std::cout << std::endl;
   
   return 0;

}</lang>

Output:

1 3 4 5 7 8 9

Excel

LAMBDA

Binding the name COMMONSORTED to the following lambda expression in the Name Manager of the Excel WorkBook:

(See LAMBDA: The ultimate Excel worksheet function)

Works with: Office 365 betas 2021

<lang lisp>COMMONSORTED =LAMBDA(grid,

   SORT(
       UNIQUE(
           CONCATCOLS(grid)
       )
   )

)</lang>

and also assuming the following generic bindings in the Name Manager for the WorkBook:

<lang lisp>CONCATCOLS =LAMBDA(cols,

   LET(
       nRows, ROWS(cols),
       ixs, SEQUENCE(
           COLUMNS(cols) * nRows, 1,
           1, 1
       ),

       FILTERP(
           LAMBDA(x, 0 < LEN("" & x))
       )(
           INDEX(cols,
               LET(
                   r, MOD(ixs, nRows),

                   IF(0 = r, nRows, r)
               ),
               1 + QUOTIENT(ixs - 1, nRows)
           )
       )
   )

)

FILTERP =LAMBDA(p,

   LAMBDA(xs,
       FILTER(xs, p(xs))
   )

)</lang>

The formula in cell B2 defines a dynamic array of values, additionally populating further cells in column B.

Output:

	fx	=COMMONSORTED(C2:E9)
	A	B	C	D	E
1		Common sorted
2		1	5	3	1
3		3	1	5	3
4		4	3	9	7
5		5	8	8	9
6		7	9	4
7		8	4
8		9	8
9			7

F#

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]

Haskell

<lang haskell>import Data.List (nub, sort)

COMMON SORTED LIST ------------------

commonSorted :: Ord a => a -> [a] commonSorted = sort . nub . concat

TEST -------------------------

main :: IO () main =

 print $
   commonSorted
     [ [5, 1, 3, 8, 9, 4, 8, 7],
       [3, 5, 9, 8, 4],
       [1, 3, 7, 9]
     ]</lang>

Output:

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

J

Output:

   nums =: 5 1 3 8 9 4 8 7;3 5 9 8 4;1 3 7 9
   csl nums
1 3 4 5 7 8 9

JavaScript

<lang javascript>(() => {

   "use strict";

   // --------------- COMMON SORTED LIST ----------------

   // commonSorted :: Ord a => a -> [a]
   const commonSorted = xs =>
       sort(nub(concat(xs)));

   // ---------------------- TEST -----------------------
   const main = () =>
       commonSorted([
           [5, 1, 3, 8, 9, 4, 8, 7],
           [3, 5, 9, 8, 4],
           [1, 3, 7, 9]
       ]);

   // --------------------- GENERIC ---------------------

   // concat :: a -> [a]
   const concat = xs => [].concat(...xs);

   // nub :: [a] -> [a]
   const nub = xs => [...new Set(xs)];

   // sort :: Ord a => [a] -> [a]
   const sort = xs =>
       // An (ascending) sorted copy of xs.
       xs.slice().sort();

   return main();

})();</lang>

Output:

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

jq

Works with: jq

Works with gojq, the Go implementation of jq

Assuming the input is a single array of arrays, we can simply chain the `add` and `unique` filters: <lang jq>jq -nc '[[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]] | add | unique'</lang>

Output:

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

If the arrays are presented individually in an external stream, we could use the `-s` command-line option.

Alternatively, here's a stream-oriented version of `add` that could be used: <lang jq>def add(s): reduce s as $x (null; . + $x);</lang> For example: <lang jq>jq -nc '

   def add(s): reduce s as $x (null; . + $x);
   add(inputs) | unique' <<< '[5,1,3,8,9,4,8,7] [3,5,9,8,4] [1,3,7,9]'</lang>

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}:

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>

Mathematica/Wolfram Language

<lang Mathematica>Union[{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}]</lang>

Output:

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

Nim

We could use a HashSet or an IntSet to deduplicate. We have rather chosen to use the procedure deduplicate from module sequtils applied to the sorted list.

<lang Nim>import algorithm, sequtils

proc commonSortedList(list: openArray[seq[int]]): seq[int] =

 sorted(concat(list)).deduplicate(true)

echo commonSortedList([@[5,1,3,8,9,4,8,7], @[3,5,9,8,4], @[1,3,7,9]])</lang>

Output:

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

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

Library: Phix/basics

?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")},{}))

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

------------------------- TEST -------------------------
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]
       ])))
   )

----------------------- GENERIC ------------------------

concat :: a -> [a]
concat :: [String] -> String

def concat(xs):

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

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))

MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

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

Quackery

uniquewith is defined at Remove duplicate elements#Quackery.

<lang Quackery> ' [ [ 5 1 3 8 9 4 8 7 ]

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

 [] swap witheach [ witheach join ]
 uniquewith > echo</lang>

Output:

[ 1 3 4 5 7 8 9 ]

Raku

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)

= 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

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

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]

Ruby

<lang ruby>nums = [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9] p nums.inject(:+).sort.uniq </lang>

Output:

[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]