Order two numerical lists

From Rosetta Code
Task
Order two numerical lists
You are encouraged to solve this task according to the task description, using any language you may know.

Write function that orders two lists or arrays filled with numbers. The function should accept two lists as arguments and return true if the first list should be ordered before the second, and false otherwise.

The order is determined by lexicographic order: Comparing the first element of each list. If the first elements are equal, then the second elements should be compared, and so on, until one of the list has no more elements. If the first list runs out of elements the result is true. if the second list or both run out of elements the result is false.

ACL2

The built-in lexorder does this.

ACL2 !>(lexorder '(1 2 3) '(1 2 3 4))
T
ACL2 !>(lexorder '(1 2 4) '(1 2 3))
NIL

Ada

This is already implemented in the built-in comparison operators for arrays of types that have a direct ordering. This also includes arrays of user defined types, using the type definition order from smallest to largest. Demonstrated in the program below: <lang Ada> with Ada.Text_IO; use Ada.Text_IO; procedure Order is

  type IntArray is array (Positive range <>) of Integer;
  List1 : IntArray := (1, 2, 3, 4, 5);
  List2 : IntArray := (1, 2, 1, 5, 2, 2);
  List3 : IntArray := (1, 2, 1, 5, 2);
  List4 : IntArray := (1, 2, 1, 5, 2);
  type Animal is (Rat, Cat, Elephant);
  type AnimalArray is array (Positive range <>) of Animal;
  List5 : AnimalArray := (Cat, Elephant, Rat, Cat);
  List6 : AnimalArray := (Cat, Elephant, Rat);
  List7 : AnimalArray := (Cat, Cat, Elephant);

begin

  Put_Line (Boolean'Image (List1 > List2)); --  True
  Put_Line (Boolean'Image (List2 > List3)); --  True
  Put_Line (Boolean'Image (List3 > List4)); --  False, equal
  Put_Line (Boolean'Image (List5 > List6)); --  True
  Put_Line (Boolean'Image (List6 > List7)); --  True

end Order; </lang> Output:

TRUE
TRUE
FALSE
TRUE
TRUE


AutoHotkey

Works with: AutoHotkey_L

The function is overkill as we can just compare the list's ObjMaxIndex() <lang AHK>List1 := [1,2,1,3,2] List2 := [1,2,0,4,4,0,0,0] MsgBox % order(List1, List2)

order(L1, L2){ return L1.MaxIndex() < L2.MaxIndex() }</lang>

Bracmat

When evaluating a sum or a product, Bracmat creates an expression with a canonical order, which happens to be compatible with the order defined in this task. In a pattern, only a sum or product on the left hand side (lhs) of the match (:) operator is evaluated. In the solution below we match a composition of the two function arguments into a sum of two terms with itself. If the match expression succeeds, the lhs must already have been in canonical order before evaluation, which means that the first argument is smaller than the second argument. In that case the function outputs FALSE. Notice that if the arguments are the same, evaluation of the sum produces the product of one of the terms and a factor two. This complicates the pattern a bit. <lang bracmat>( 1 2 3 4 5:?List1 & 1 2 1 5 2 2:?List2 & 1 2 1 5 2:?List3 & 1 2 1 5 2:?List4 & Cat Elephant Rat Cat:?List5 & Cat Elephant Rat:?List6 & Cat Cat Elephant:?List7 & ( gt

 =   first second
   .   !arg:(?first,?second)
     &   out
       $ (     (.!first)+(.!second)
             : ((.!first)+(.!second)|2*(.!first))
           & FALSE
         | TRUE
         )
 )

& gt$(!List1,!List2) & gt$(!List2,!List3) & gt$(!List3,!List4) & gt$(!List4,!List5) & gt$(!List5,!List6) & gt$(!List6,!List7) );</lang> Output:

TRUE
TRUE
FALSE
FALSE
TRUE
TRUE

C

<lang c>int list_cmp(int *a, int la, int *b, int lb) { int i, l = la; if (l > lb) l = lb; for (i = 0; i < l; i++) { if (a[i] == b[i]) continue; return (a[i] > b[i]) ? 1 : -1; } if (la == lb) return 0; return la > lb ? 1 : -1; }</lang> This funciton returns one of three states, not a boolean. One can define boolean comparisons, such as list_less_or_eq, based on it:<lang c>#define list_less_or_eq(a,b,c,d) (list_cmp(a,b,c,d) != 1)</lang>

C++

The built-in comparison operators already do this: <lang cpp>#include <iostream>

  1. include <vector>

int main() {

 std::vector<int> a;
 a.push_back(1);
 a.push_back(2);
 a.push_back(1);
 a.push_back(3);
 a.push_back(2);
 std::vector<int> b;
 b.push_back(1);
 b.push_back(2);
 b.push_back(0);
 b.push_back(4);
 b.push_back(4);
 b.push_back(0);
 b.push_back(0);
 b.push_back(0);
 std::cout << std::boolalpha << (a < b) << std::endl; // prints "false"
 return 0;

}</lang>

clojure

<lang clojure> (defn lex? [a b]

 (reduce = 
   (map (fn a b (<= (compare a b) 0) )
     (map vector a b))))

</lang>

Common Lisp

<lang Lisp>(defun list< (a b)

 (cond ((not b) nil)
       ((not a) t)
       ((= (first a) (first b))
        (list< (rest a) (rest b)))
       (t (< (first a) (first b)))))</lang>

Alternate version

<lang Lisp>(defun list< (a b)

 (let ((x (find-if-not #'zerop (mapcar #'- a b))))
   (if x (minusp x) (< (length a) (length b)))))</lang>

D

The built-in comparison operators already do this: <lang d>void main() {

   assert([1,2,1,3,2] >= [1,2,0,4,4,0,0,0]);

}</lang>

Ela

<lang ela>[] <. _ = true _ <. [] = false (x::xs) <. (y::ys) | x == y = xs <. ys

                  | else   = x < y

[1,2,1,3,2] <. [1,2,0,4,4,0,0,0]</lang>

Factor

All sequences respond to words in the math.order vocabulary.

IN: scratchpad { 2 3 } { 2 5 } before? .
t

Go

<lang go>package main

import "fmt"

// If your numbers happen to be in the range of Unicode code points (0 to 0x10ffff), this function // satisfies the task: func lessRune(a, b []rune) bool {

   return string(a) < string(b) // see also bytes.Compare

}

// Otherwise, the following function satisfies the task for all integer // and floating point types, by changing the type definition appropriately. type numericType int

func lessNT(a, b []numericType) bool {

   l := len(a)
   if len(b) < l {
       l = len(b)
   }
   for i := 0; i < l; i++ {
       if a[i] != b[i] {
           return a[i] < b[i]
       }
   }
   return l < len(b)

}

var testCases = [][][]numericType{

   {{0}, {}},
   {{}, {}},
   {{}, {0}},
   {{-1}, {0}},
   {{0}, {0}},
   {{0}, {-1}},
   {{0}, {0, -1}},
   {{0}, {0, 0}},
   {{0}, {0, 1}},
   {{0, -1}, {0}},
   {{0, 0}, {0}},
   {{0, 0}, {1}},

}

func main() {

   // demonstrate the general function
   for _, tc := range testCases {
       fmt.Printf("order %6s before %6s : %t\n",
           fmt.Sprintf("%v", tc[0]),
           fmt.Sprintf("%v", tc[1]),
           lessNT(tc[0], tc[1]))
   }
   fmt.Println()
   // demonstrate that the byte specific function gives identical results
   // by offsetting test data to a printable range of characters.
   for _, tc := range testCases {
       a := toByte(tc[0])
       b := toByte(tc[1])
       fmt.Printf("order %6q before %6q : %t\n",
           string(a),
           string(b),
           lessByte(a, b))
   }

}

func toByte(a []numericType) []byte {

   b := make([]byte, len(a))
   for i, n := range a {
       b[i] = 'b' + byte(n)
   }
   return b

}</lang> Output:

order    [0] before     [] : false
order     [] before     [] : false
order     [] before    [0] : true
order   [-1] before    [0] : true
order    [0] before    [0] : false
order    [0] before   [-1] : false
order    [0] before [0 -1] : true
order    [0] before  [0 0] : true
order    [0] before  [0 1] : true
order [0 -1] before    [0] : false
order  [0 0] before    [0] : false
order  [0 0] before    [1] : true

order    "b" before     "" : false
order     "" before     "" : false
order     "" before    "b" : true
order    "a" before    "b" : true
order    "b" before    "b" : false
order    "b" before    "a" : false
order    "b" before   "ba" : true
order    "b" before   "bb" : true
order    "b" before   "bc" : true
order   "ba" before    "b" : false
order   "bb" before    "b" : false
order   "bb" before    "c" : true

Groovy

Solution: <lang groovy>class CList extends ArrayList implements Comparable {

   CList() { }
   CList(Collection c) { super(c) }
   int compareTo(Object that) {
       assert that instanceof List
       def n = [this.size(), that.size()].min()
       def comp = [this[0..<n], that[0..<n]].transpose().find { it[0] != it[1] }
       comp ? comp[0] <=> comp[1] : this.size() <=> that.size()
   }

}</lang>

Test: <lang groovy>CList a, b; (a, b) = [[], []]; assert ! (a < b) b = [1] as CList; assert (a < b) a = [1] as CList; assert ! (a < b) b = [2] as CList; assert (a < b) a = [2, -1, 0] as CList; assert ! (a < b) b = [2, -1] as CList; assert ! (a < b) b = [2, -1, 0] as CList; assert ! (a < b) b = [2, -1, 0, -17] as CList; assert (a < b) a = [2, 8, 0] as CList; assert ! (a < b)</lang>

Haskell

The built-in comparison operators already do this: <lang haskell>Prelude> [1,2,1,3,2] < [1,2,0,4,4,0,0,0] False</lang>

Icon and Unicon

List_llt is written in the style of all Icon/Unicon relational operators returning its right argument if successful and signaling failure otherwise.

<lang Icon>procedure main()

  write( if list_llt([1,2,1,3,2],[1,2,0,4,4,0,0,0]) then "true" else "false" ) 

end


procedure list_llt(L1,L2) #: returns L2 if L1 lexically lt L2 or fails every i := 1 to min(*L1,*L2) do

  if L1[i] << L2[i] then return L2 
  else if L1[i] >> L2[i] then fail

if *L1 < *L2 then return L2 end</lang>

J

This is not a built-in in J.

<lang j>before=: -.@(-: /:~)@,&<~</lang>

Example use:

<lang j> (,0) before 0

    before 

0

    before ,0

1

   (,_1) before ,0

1

   (,0) before ,0

0

   (,0) before ,_1

0

   (,0) before 0 _1

1

   (,0) before 0 0

1

   (,0) before 0 1

1

   0 _1 before ,0

0

   0 0 before ,0

0

   0 0 before ,1

1

   (,'b') before 

0

    before 

0

    before ,'b'

1

   (,'a') before ,'b'

1

   (,'b') before ,'b'

0

   (,'b') before ,'a'

0

   (,'b') before 'ba'

1

   (,'b') before 'bb'

1

   (,'b') before 'bc'

1

   'ba' before ,'b'

0

   'bb' before ,'b'

0

   'bb' before ,'c'

1</lang>


Java

Works with: Java version 1.5+
Translation of: Common Lisp

There are a few methods here. The method named "ordered" which works on arrays is a translation of Common Lisp. The other two are loose translations of Tcl (some tweaks were needed to get the length checks to work out) and are probably better options. <lang java5>import java.util.Arrays; import java.util.List;

public class ListOrder{ public static boolean ordered(double[] first, double[] second){ if(first.length == 0) return true; if(second.length == 0) return false; if(first[0] == second[0]) return ordered(Arrays.copyOfRange(first, 1, first.length), Arrays.copyOfRange(second, 1, second.length)); return first[0] < second[0]; }

public static <T extends Comparable<? super T>> boolean ordered(List<T> first, List<T> second){ int i = 0; for(; i < first.size() && i < second.size();i++){ int cmp = first.get(i).compareTo(second.get(i)); if(cmp == 0) continue; if(cmp < 0) return true; return false; } return i == first.size(); }

public static boolean ordered2(double[] first, double[] second){ int i = 0; for(; i < first.length && i < second.length;i++){ if(first[i] == second[i]) continue; if(first[i] < second[i]) return true; return false; } return i == first.length; } }</lang>

Joy

<lang Joy> DEFINE order == [equal] [false] [[[[size] dip size <=] [[<=] mapr2 true [and] fold]] [i] map i and] ifte. </lang>

Using it:

[1 2] [1 2 3] order. # true
[1 2] [1 3] order.   # true
[1 2] [1 2] order.   # false
[1 3] [1 2] order.   # false
[1 2 3] [1 2] order. # false

LabVIEW

Translation of: AutoHotkey

This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.

Mathematica

This example is incorrect. Please fix the code and remove this message.
Details: For lexicographic order, it's not enough to compare lengths.

<lang Mathematica>order[L1_, L2_] := Length [L1] < Length [L2]</lang>

Example use:
List1 = {1, 2, 1, 3, 2}; List2 = {1, 2, 0, 4, 4, 0, 0, 0};
order[List1, List2]
->True

Mercury

For a particular numerical type, you can get away with

<lang Mercury>:- pred lt(list(int)::in, list(int)::in) is semidet. lt([], [_|_]). lt([H1|T1], [H2|T2]) :- H1 =< H2, T1 `lt` T2.</lang>

For a list of any numerical type, one way would be to use a typeclass:

<lang Mercury>:- pred lt(list(T)::in, list(T)::in) is semidet <= comparable(T). lt([], [_|_]). lt([H1|T1], [H2|T2]) :- H1 =< H2, T1 `lt` T2.</lang>

... which you would have to create:

<lang Mercury>:- module comparable.

- interface.
- import_module int, float, integer, list.
- typeclass comparable(T) where [
       pred '<'(T::in, T::in) is semidet,
       pred '=<'(T::in, T::in) is semidet

].

- instance comparable(int).
- instance comparable(float).
- instance comparable(integer).
- instance comparable(list(T)) <= comparable(T).
- implementation.
- instance comparable(int) where [
       pred('<'/2) is int.(<),
       pred('=<'/2) is int.(=<) 

]. % likewise for float and integer...

- instance comparable(list(T)) <= comparable(T) where [
       pred('<'/2) is lt,   % the 'lt' above.
       pred('=<'/2) is lte  % 'lt' with: lte([], []).

].

% pred lt % pred lte</lang>

Which would be used in this way - note the typeclass and the comparison operator.

<lang Mercury>:- pred test(list(T), list(T), io, io) <= comparable(T).

- mode test(in, in, di, uo) is det.

test(A, B) -->

       io.write(A), io.write_string(" < "), io.write(B),
       io.write_string(" : "), io.write_string(S), io.nl,
       { A < B -> S = "yes" ; S = "no" }.</lang>

OCaml

The built-in comparison operators already do this: <lang ocaml># [1;2;1;3;2] < [1;2;0;4;4;0;0;0];; - : bool = false</lang>

But we could write it explicitly this way:

<lang ocaml>let rec ordered_lists = function

 | x1::tl1, x2::tl2 ->
     (match compare x1 x2 with
     | 0 -> ordered_lists (tl1, tl2)
     | 1 -> false
     | _ -> true)
 | [], _ -> true
 | _ -> false</lang>

Here is a small script to test this function:

<lang ocaml>(* copy-paste the code of ordered_lists here *)

let make_num_list p n =

 let rec aux acc =
   if Random.int p = 0 then acc
   else aux (Random.int n :: acc)
 in
 aux []

let print_num_list lst =

 List.iter (Printf.printf " %d") lst;
 print_newline()

let () =

 Random.self_init();
 let lst1 = make_num_list 8 5 in
 let lst2 = make_num_list 8 5 in
 print_num_list lst1;
 print_num_list lst2;
 Printf.printf "ordered: %B\n" (ordered_lists (lst1, lst2))</lang>

Sample execution:

$ ocaml ordered_lists.ml
 1 2 1 3 2
 1 2 0 4 4 0 0 0
ordered: false

Also notice that the function ordered_lists will work with anything the function Pervasives.compare is able to compare (most OCaml types and structures made from the base types). In the prototype of this function below 'a list means a list of anything:

<lang ocaml>val ordered_lists : 'a list * 'a list -> bool</lang>

PARI/GP

<lang parigp>lex(u,v)<1</lang>

Perl

<lang Perl>#!/usr/bin/perl -w use strict ;

sub orderlists {

  my $firstlist = shift ;
  my $secondlist = shift ;
  my $first = shift @{$firstlist } if @{$firstlist} ;
  my $second ;
  1. keep stripping elements from the first list as long as there are any
  2. or until the second list is used up!
  while ( @{$firstlist} ) {
     if ( @{$secondlist} ) { #second list is not used up yet!

$second = shift @{$secondlist} ; if ( $first < $second ) { return 1 ; } if ( $first > $second ) { return 0 ; }

     }
     else {                  #second list used up, defined to return false

return 0 ;

     }
     $first = shift @{$firstlist} ;
  }
  return 0 ;                 #in all remaining cases return false

}

my @firstnumbers = ( 43 , 33 , 2 ) ; my @secondnumbers = ( 45 ) ; if ( orderlists( \@firstnumbers , \@secondnumbers ) ) {

  print "The first list comes before the second list!\n" ;

} else {

  print "The first list does not come before the second list!\n" ;

} </lang>

Perl 6

<lang perl6>sub order_array(@a, @b) {

   # zip the lists together and compare
   for @a Z @b -> $i, $j {
       return $i < $j if $i != $j;
   }
   # if it reach here, the lists are so far equal
   @a < @b; # order by number of elements

}

my @a = <1 2 4>; my @b = <0 1 3>;

say order_array(@a,@b); # false

@b[0] = 10;

say order_array(@a,@b); # true </lang>

PicoLisp

The built-in comparison functions already do this (not only for lists of numbers, but for any arbitrary data type). <lang PicoLisp>: (> (1 2 0 4 4 0 0 0) (1 2 1 3 2)) -> NIL</lang>

Pike

<lang Pike>int(0..1) order_array(array a, array b) {

 if (!sizeof(a)) return true;
 if (!sizeof(b)) return false;
 if (a[0] == b[0])
   return order_array(a[1..], b[1..]);
 return a[0] < b[0];

}</lang> Pikes Array.sort_array() function can sort an array of arrays using the < operator, but it will sort longer arrays before shorter ones. Therefore the above function is still needed if the intent is to use the comparison for a sort operation.

If the numbers are in 32bit signed integer range, the following works too: <lang Pike>(string)a < (string)b;</lang>

PureBasic

<lang purebasic>DataSection

 Array_1:
 Data.i 5              ;element count
 Data.i 1, 2, 3, 4, 5  ;element data
 Array_2:
 Data.i 6
 Data.i 1, 2, 1, 5, 2, 2
 Array_3:
 Data.i 5
 Data.i 1, 2, 1, 5, 2
 Array_4:
 Data.i 5
 Data.i 1, 2, 1, 5, 2
 Array_5:
 Data.i 4
 Data.i 1, 2, 1, 6
 Array_6:
 Data.i 5
 Data.i 1, 2, 1, 6, 2

EndDataSection

  1. False = 0
  2. True = 1
helper subrountine to initialize a dataset, *dataPtr points to the elementcount followed by the element data

Procedure initArrayData(Array a(1), *dataPtr)

 Protected elementCount = PeekI(*dataPtr)
 
 Dim a(elementCount - 1)
 For i = 0 To elementCount - 1
   *dataPtr + SizeOf(Integer)
   a(i) = PeekI(*dataPtr)
 Next

EndProcedure

helper subroutine that returns 'True' or 'False' for a boolean input

Procedure.s booleanText(b)

 If b: ProcedureReturn "True": EndIf
 ProcedureReturn "False"

EndProcedure

Procedure order(Array a(1), Array b(1))

 Protected len_a = ArraySize(a()), len_b = ArraySize(b()), elementIndex
 While elementIndex <= len_a And elementIndex <= len_b And a(elementIndex) = b(elementIndex)
   elementIndex + 1
 Wend
 
 If (elementIndex > len_a  And elementIndex <= len_b) Or (elementIndex <= len_b And a(elementIndex) <= b(elementIndex))
   ProcedureReturn #True
 EndIf

EndProcedure

Dim A_1(0): initArrayData(A_1(), ?Array_1) Dim A_2(0): initArrayData(A_2(), ?Array_2) Dim A_3(0): initArrayData(A_3(), ?Array_3) Dim A_4(0): initArrayData(A_4(), ?Array_4) Dim A_5(0): initArrayData(A_5(), ?Array_5) Dim A_6(0): initArrayData(A_6(), ?Array_6)

If OpenConsole()

 PrintN(booleanText(order(A_1(), A_2()))) ;False
 PrintN(booleanText(order(A_2(), A_3()))) ;False
 PrintN(booleanText(order(A_3(), A_4()))) ;False
 PrintN(booleanText(order(A_4(), A_5()))) ;True
 PrintN(booleanText(order(A_5(), A_6()))) ;True
 
 Print(#crlf$ + #crlf$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf

 </lang>

Sample output:

False
False
False
True
True

Python

The built-in comparison operators already do this: <lang python>>>> [1,2,1,3,2] < [1,2,0,4,4,0,0,0] False</lang>

Rascal

The built-in comparison operator already does this: <lang rascal>rascal>[2,1,3] < [5,2,1,3] bool: true</lang>

Ruby

The built-in <=> operator already does this: <lang ruby>>> ([1,2,1,3,2] <=> [1,2,0,4,4,0,0,0]) < 0 => false</lang>

Standard ML

<lang sml>- List.collate Int.compare ([1,2,1,3,2], [1,2,0,4,4,0,0,0]) = LESS; val it = false : bool</lang>

Tcl

<lang tcl>proc numlist< {A B} {

   foreach a $A b $B {
       if {$a<$b} {
           return 1
       } elseif {$a>$b} {
           return 0
       }
   }
   return 0

}</lang>