Sort numbers lexicographically
- Task
Given an integer n, return 1──►n (inclusive) in lexicographical order.
Show all output here on this page.
- Example
Given 13,
return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
AWK
<lang AWK>
- syntax: GAWK -f SORT_NUMBERS_LEXICOGRAPHICALLY.AWK
- sorting:
- PROCINFO["sorted_in"] is used by GAWK
- SORTTYPE is used by Thompson Automation's TAWK
BEGIN {
prn(0) prn(1) prn(13) prn(9,10) prn(-11,+11) prn(-21) prn("",1) prn(+1,-1) exit(0)
} function prn(n1,n2) {
if (n1 <= 0 && n2 == "") { n2 = 1 } if (n2 == "") { n2 = n1 n1 = 1 } printf("%d to %d: %s\n",n1,n2,snl(n1,n2))
} function snl(start,stop, arr,i,str) {
if (start == "") { return("error: start=blank") } if (start > stop) { return("error: start>stop") } for (i=start; i<=stop; i++) { arr[i] } PROCINFO["sorted_in"] = "@ind_str_asc" ; SORTTYPE = 2 for (i in arr) { str = sprintf("%s%s ",str,i) } sub(/ $/,"",str) return(str)
} </lang>
- Output:
0 to 1: 0 1 1 to 1: 1 1 to 13: 1 10 11 12 13 2 3 4 5 6 7 8 9 9 to 10: 10 9 -11 to 11: -1 -10 -11 -2 -3 -4 -5 -6 -7 -8 -9 0 1 10 11 2 3 4 5 6 7 8 9 -21 to 1: -1 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -2 -20 -21 -3 -4 -5 -6 -7 -8 -9 0 1 0 to 1: error: start=blank 1 to -1: error: start>stop
C
<lang c>#include <math.h>
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
int compareStrings(const void *a, const void *b) {
const char **aa = (const char **)a; const char **bb = (const char **)b; return strcmp(*aa, *bb);
}
void lexOrder(int n, int *ints) {
char **strs; int i, first = 1, last = n, k = n, len; if (n < 1) { first = n; last = 1; k = 2 - n; } strs = malloc(k * sizeof(char *)); for (i = first; i <= last; ++i) { if (i >= 1) len = (int)log10(i) + 2; else if (i == 0) len = 2; else len = (int)log10(-i) + 3; strs[i-first] = malloc(len); sprintf(strs[i-first], "%d", i); } qsort(strs, k, sizeof(char *), compareStrings); for (i = 0; i < k; ++i) { ints[i] = atoi(strs[i]); free(strs[i]); } free(strs);
}
int main() {
int i, j, k, n, *ints; int numbers[5] = {0, 5, 13, 21, -22}; printf("In lexicographical order:\n\n"); for (i = 0; i < 5; ++i) { k = n = numbers[i]; if (k < 1) k = 2 - k; ints = malloc(k * sizeof(int)); lexOrder(n, ints); printf("%3d: [", n); for (j = 0; j < k; ++j) { printf("%d ", ints[j]); } printf("\b]\n"); free(ints); } return 0;
}</lang>
- Output:
In lexicographical order: 0: [0 1] 5: [1 2 3 4 5] 13: [1 10 11 12 13 2 3 4 5 6 7 8 9] 21: [1 10 11 12 13 14 15 16 17 18 19 2 20 21 3 4 5 6 7 8 9] -22: [-1 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -2 -20 -21 -22 -3 -4 -5 -6 -7 -8 -9 0 1]
C#
<lang csharp>using static System.Console; using static System.Linq.Enumerable;
public class Program {
public static void Main() { foreach (int n in new [] { 0, 5, 13, 21, -22 }) WriteLine($"{n}: {string.Join(", ", LexOrder(n))}"); }
public static IEnumerable<int> LexOrder(int n) => (n < 1 ? Range(n, 2 - n) : Range(1, n)).OrderBy(i => i.ToString());
}</lang>
- Output:
0: 0, 1 5: 1, 2, 3, 4, 5 13: 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9 21: 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 3, 4, 5, 6, 7, 8, 9 -22: -1, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -2, -20, -21, -22, -3, -4, -5, -6, -7, -8, -9, 0, 1
Factor
<lang factor>USING: formatting kernel math.parser math.ranges sequences sorting ; IN: rosetta-code.lexicographical-numbers
- lex-order ( n -- seq )
[1,b] [ number>string ] map natural-sort [ string>number ] map ;
{ 13 21 -22 } [ dup lex-order "%3d: %[%d, %]\n" printf ] each</lang>
- Output:
13: { 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9 } 21: { 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 3, 4, 5, 6, 7, 8, 9 } -22: { -1, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -2, -20, -21, -22, -3, -4, -5, -6, -7, -8, -9, 0, 1 }
Go
<lang go>package main
import (
"fmt" "sort" "strconv"
)
func lexOrder(n int) []int {
first, last, k := 1, n, n if n < 1 { first, last, k = n, 1, 2-n } strs := make([]string, k) for i := first; i <= last; i++ { strs[i-first] = strconv.Itoa(i) } sort.Strings(strs) ints := make([]int, k) for i := 0; i < k; i++ { ints[i], _ = strconv.Atoi(strs[i]) } return ints
}
func main() {
fmt.Println("In lexicographical order:\n") for _, n := range []int{0, 5, 13, 21, -22} { fmt.Printf("%3d: %v\n", n, lexOrder(n)) }
}</lang>
- Output:
In lexicographical order: 0: [0 1] 5: [1 2 3 4 5] 13: [1 10 11 12 13 2 3 4 5 6 7 8 9] 21: [1 10 11 12 13 14 15 16 17 18 19 2 20 21 3 4 5 6 7 8 9] -22: [-1 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -2 -20 -21 -22 -3 -4 -5 -6 -7 -8 -9 0 1]
Java
Requires Java 8 or later.
<lang java>import java.util.List;
import java.util.stream.*;
public class LexicographicalNumbers {
static List<Integer> lexOrder(int n) { int first = 1, last = n; if (n < 1) { first = n; last = 1; } return IntStream.rangeClosed(first, last) .mapToObj(Integer::toString) .sorted() .map(Integer::valueOf) .collect(Collectors.toList()); }
public static void main(String[] args) { System.out.println("In lexicographical order:\n"); int[] ints = {0, 5, 13, 21, -22}; for (int n : ints) { System.out.printf("%3d: %s\n", n, lexOrder(n)); } }
}</lang>
- Output:
In lexicographical order: 0: [0, 1] 5: [1, 2, 3, 4, 5] 13: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] 21: [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 3, 4, 5, 6, 7, 8, 9] -22: [-1, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -2, -20, -21, -22, -3, -4, -5, -6, -7, -8, -9, 0, 1]
Kotlin
<lang scala>// Version 1.2.51
fun lexOrder(n: Int): List<Int> {
var first = 1 var last = n if (n < 1) { first = n last = 1 } return (first..last).map { it.toString() }.sorted().map { it.toInt() }
}
fun main(args: Array<String>) {
println("In lexicographical order:\n") for (n in listOf(0, 5, 13, 21, -22)) { println("${"%3d".format(n)}: ${lexOrder(n)}") }
}</lang>
- Output:
In lexicographical order: 0: [0, 1] 5: [1, 2, 3, 4, 5] 13: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] 21: [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 3, 4, 5, 6, 7, 8, 9] -22: [-1, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -2, -20, -21, -22, -3, -4, -5, -6, -7, -8, -9, 0, 1]
Lua
Lua's in-built table.sort function will sort a table of strings into lexicographical order by default. This task therefore becomes trivial by converting each number to a string before adding it to the table. <lang lua>function lexNums (limit)
local numbers = {} for i = 1, limit do table.insert(numbers, tostring(i)) end table.sort(numbers) return numbers
end
local numList = lexNums(13) print(table.concat(numList, " "))</lang>
- Output:
1 10 11 12 13 2 3 4 5 6 7 8 9
M2000 Interpreter
<lang M2000 Interpreter> Module Checkit {
Function lexicographical(N) { const nl$=Chr$(13)+Chr$(10) If N<>0 then { if N=1 then =(1,) : Exit Document A$ For k=1 to N-1 A$=Str$(k,"")+{ } Next k A$=Str$(N,"") Method A$, "SetBinaryCompare" Sort A$ Flush \\ convert strings to numbers in one statement \\ in stack of values Data Param(Replace$(nl$,",", a$)) \\ return stack as array =Array([]) } else =(0,) ' empty array } Print lexicographical(5) ' 1 2 3 4 5 Print lexicographical(13) ' 1 10 11 12 13 2 3 4 5 6 7 8 9 Print lexicographical(21) ' 1 10 11 12 13 14 15 16 17 18 19 2 20 21 3 4 5 6 7 8 9 Print lexicographical(-22) ' -1 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -2 -20 -21 -22 -3 -4 -5 -6 -7 -8 -9 0 1
} } Checkit Module Checkit {
Function lexicographical$(N) { const nl$=Chr$(13)+Chr$(10) If N<>0 then { if N=1 then =(1,) : Exit Document A$ For k=1 to N-1 A$=Str$(k,"")+{ } Next k A$=Str$(N,"") \\ by default id TextCompare, so 0 an 1 comes first in -22 Method A$, "SetBinaryCompare" Sort A$ Flush ="["+Replace$(nl$," ", a$)+"]" } else =("",) ' empty array } Print lexicographical$(5) ' [1 2 3 4 5] Print lexicographical$(13) ' [1 10 11 12 13 2 3 4 5 6 7 8 9] Print lexicographical$(21) '[1 10 11 12 13 14 15 16 17 18 19 2 20 21 3 4 5 6 7 8 9] Print lexicographical$(-22) ' [-1 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -2 -20 -21 -22 -3 -4 -5 -6 -7 -8 -9 0 1]
} Checkit </lang>
Microsoft Small Basic
In Small Basic there is no string comparison: “a”>”b” the result is “False”, “b”>”a” the result is also “False”. It doesn’t help at all. <lang smallbasic>' Lexicographical numbers - 25/07/2018 xx="000000000000000" For n=1 To 3
nn=Text.GetSubText(" 5 13 21",n*4-3,4) ll=Text.GetLength(nn) For i=1 To nn t[i]=i EndFor i=nn-1 k=0 For i=i To 1 Step -1 ok=1 For j=1 To i k=j+1 tj=Text.GetSubText(Text.Append(t[j],xx),1,ll) tk=Text.GetSubText(Text.Append(t[k],xx),1,ll) If tj>tk Then w=t[j] t[j]=t[k] t[k]=w ok=0 EndIf EndFor If ok=1 Then Goto exitfor EndIf EndFor
exitfor:
x="" For i=1 To nn x=x+","+t[i] EndFor TextWindow.WriteLine(nn+":"+Text.GetSubTextToEnd(x,2))
EndFor </lang>
- Output:
5:1,2,3,4,5 13:1,10,11,12,13,2,3,4,5,6,7,8,9 21:1,10,11,12,13,14,15,16,17,18,19,2,20,21,3,4,5,6,7,8,9
Perl
<lang perl>printf("%4d: [%s]\n", $_, join ',', sort $_ > 0 ? 1..$_ : $_..1) for 13, 21, -22</lang>
- Output:
13: [1,10,11,12,13,2,3,4,5,6,7,8,9] 21: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,3,4,5,6,7,8,9] -22: [-1,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-2,-20,-21,-22,-3,-4,-5,-6,-7,-8,-9,0,1]
Perl 6
<lang perl6>sub lex (Int $n) { (1…$n).sort: ~* }
- TESTING
printf("%4d: [%s]\n", $_, .&lex.join: ',') for 13, 21, -22</lang>
- Output:
13: [1,10,11,12,13,2,3,4,5,6,7,8,9] 21: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,3,4,5,6,7,8,9] -22: [-1,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-2,-20,-21,-22,-3,-4,-5,-6,-7,-8,-9,0,1]
Phix
Idiomatic version - crashes if n<1, and calls sprint() 76 times. <lang Phix>function lexographic(integer i, j)
return compare(sprint(i),sprint(j))
end function
function lex_order(integer n)
return custom_sort(routine_id("lexographic"), tagset(n))
end function
?lex_order(13)</lang>
- Output:
{1,10,11,12,13,2,3,4,5,6,7,8,9}
Alternative version, handles n<1, and for n=13 (say) it calls sprint() only 13 times instead of 76. <lang Phix>function lex_order(integer n)
integer {lo,hi} = iff(n<1?{n-1,1}:{0,n}), l = hi-lo sequence s = repeat(0,l) for i=1 to l do s[i] = {sprint(lo+i),lo+i} end for s = sort(s) for i=1 to l do s[i] = s[i][2] end for return s
end function
?lex_order(13) ?lex_order(0) ?lex_order(-22)</lang>
- Output:
{1,10,11,12,13,2,3,4,5,6,7,8,9} {0,1} {-1,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-2,-20,-21,-22,-3,-4,-5,-6,-7,-8,-9,0,1}
PureBasic
<lang purebasic>EnableExplicit
Procedure lexOrder(n, Array ints(1))
Define first = 1, last = n, k = n, i If n < 1 first = n last = 1 k = 2 - n EndIf Dim strs.s(k - 1) For i = first To last strs(i - first) = Str(i) Next SortArray(strs(), #PB_Sort_Ascending) For i = 0 To k - 1 ints(i) = Val(Strs(i)) Next
EndProcedure
If OpenConsole()
PrintN(~"In lexicographical order:\n") Define i, j, n, k For i = 0 To 4 Read n k = n If n < 1 k = 2 - n EndIf Dim ints(k - 1) lexOrder(n, ints()) Define.s ns = RSet(Str(n), 3) Print(ns + ": [") For j = 0 To k - 1 Print(Str(ints(j)) + " ") Next j PrintN(~"\b]") Next i Input() End
DataSection Data.i 0, 5, 13, 21, -22 EndDataSection
EndIf</lang>
- Output:
In lexicographical order: 0: [0 1] 5: [1 2 3 4 5] 13: [1 10 11 12 13 2 3 4 5 6 7 8 9] 21: [1 10 11 12 13 14 15 16 17 18 19 2 20 21 3 4 5 6 7 8 9] -22: [-1 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -2 -20 -21 -22 -3 -4 -5 -6 -7 -8 -9 0 1]
REXX
This REXX version allows the starting and ending integer to be specified via the command line (CL). <lang rexx>/*REXX pgm displays a horizontal list of a range of integers sorted lexicographically.*/ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI= 13 /* " " " " " " */
- =0 /*for actual sort, start array with 1.*/
do j=LO to HI; #= # + 1; @.#=j /*construct an array from LO to HI.*/ end /*j*/
call lSort # /*sort integer array with a simple sort*/ $= /*initialize horizontal integer list. */
do k=1 for #; $= $','@.k /*construct " " " */ end /*k*/ /* [↑] prefix each number with a comma*/
say 'for ' LO"──►"HI' (inclusive), ' # "elements sorted lexicographically:" say '['strip($, "L", ',')"]" /*strip leading comma, bracket the list*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ lSort: procedure expose @.; parse arg n; m=n-1 /*N: is the number of @ array elements.*/
do m=m by -1 until ok; ok=1 /*keep sorting the @ array until done.*/ do j=1 for m; k=j+1; if @.j>>@.k then parse value @.j @.k 0 with @.k @.j ok end /*j*/ /* [↑] swap 2 elements, flag as ¬done.*/ end /*m*/; return</lang>
- output when using the default input:
for 1──►13 (inclusive), 13 elements sorted lexicographically: [1,10,11,12,13,2,3,4,5,6,7,8,9]
- output when using the input of: 1 34
for 1──►34 (inclusive), 34 elements sorted lexicographically: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,4,5,6,7,8,9]
- output when using the input of: -11 22
for -11──►22 (inclusive), 34 elements sorted lexicographically: [-1,-10,-11,-2,-3,-4,-5,-6,-7,-8,-9,0,1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,3,4,5,6,7,8,9]
Ring
<lang ring>
- Project : Lexicographical numbers
lex = 1:13 strlex = list(len(lex)) for n = 1 to len(lex)
strlex[n] = string(lex[n])
next strlex = sort(strlex) see "Lexicographical numbers = " showarray(strlex)
func showarray(vect)
see "[" svect = "" for n = 1 to len(vect) svect = svect + vect[n] + "," next svect = left(svect, len(svect) - 1) see svect + "]" + nl
</lang> Output:
Lexicographical numbers = [1,10,11,12,13,2,3,4,5,6,7,8,9]
VBA
<lang VB> Public Function sortlexicographically(N As Integer)
Dim arrList As Object Set arrList = CreateObject("System.Collections.ArrayList") For i = 1 To N arrList.Add CStr(i) Next i arrList.Sort Dim item As Variant For Each item In arrList Debug.Print item & ", "; Next
End Function
Public Sub main()
Call sortlexicographically(13)
End Sub </lang>
- Output:
1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9,
Sidef
<lang ruby>func lex_order (n) {
[range(1, n, n.sgn)...].sort_by { Str(_) }
}
[13, 21, -22].each {|n|
printf("%4s: %s\n", n, lex_order(n))
}</lang>
- Output:
13: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] 21: [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 3, 4, 5, 6, 7, 8, 9] -22: [-1, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -2, -20, -21, -22, -3, -4, -5, -6, -7, -8, -9, 0, 1]
zkl
<lang zkl>fcn lexN(n){ n.pump(List,'+(1),"toString").sort().apply("toInt") }</lang> <lang zkl>foreach n in (T(5,13,21)){ println("%2d: %s".fmt(n,lexN(n).concat(","))) }</lang>
- Output:
5: 1,2,3,4,5 13: 1,10,11,12,13,2,3,4,5,6,7,8,9 21: 1,10,11,12,13,14,15,16,17,18,19,2,20,21,3,4,5,6,7,8,9