Order two numerical lists

Order two numerical lists 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.

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.

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>

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>

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>

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>

Go

<lang go>package main

import "fmt"

// If your numbers happen to be in the range 0 to 255, this function // satisfies the task: func lessByte(a, b []byte) bool {

   return string(a) < string(b)

}

// 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 ofsetting 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

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>

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>

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>

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

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>

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>