Order two numerical lists: Difference between revisions
(added a few languages' built-in support) |
(added c++) |
||
Line 5: | Line 5: | ||
The order is determined by [[wp:Lexicographical order#Ordering of sequences of various lengths|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 <code>true</code>. <code>false</code> otherwise. |
The order is determined by [[wp:Lexicographical order#Ordering of sequences of various lengths|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 <code>true</code>. <code>false</code> otherwise. |
||
=={{header|C++}}== |
|||
The built-in comparison operators already do this: |
|||
<lang cpp>#include <iostream> |
|||
#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> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
Revision as of 22:33, 28 November 2011
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
. false
otherwise.
C++
The built-in comparison operators already do this: <lang cpp>#include <iostream>
- 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 a) t) ((not b) nil) ((= (first a) (first b)) (list< (rest a) (rest b))) (t (< (first a) (first b)))))</lang>
Go
For numbers in the range 0 to 255: <lang go>func OrderTwoNumericalLists(a, b []byte) bool {
return string(a) < string(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>
Java
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 boolean ordered(List<Double> first, List<Double> second){ int i = 0; for(; i < first.size() && i < second.size();i++){ if(first.get(i) == second.get(i)) continue; if(first.get(i) < second.get(i)) 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>
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>
The function that achieves the task:
<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>
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>
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>
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>