algorithm - seres - tipos de sistemas naturales

Algoritmo de clasificación natural

Question

¿Cómo se ordena una serie de cadenas de naturally en diferentes lenguajes de programación? Publique su implementación y en qué idioma se encuentra en la respuesta.

Answer 1

A continuación, le mostramos cómo puede obtener un comportamiento similar al del explorador en Python:

#!/usr/bin/env python
"""
>>> items = u''a1 a003 b2 a2 a10 1 10 20 2 c100''.split()
>>> items.sort(explorer_cmp)
>>> for s in items:
... print s,
1 2 10 20 a1 a2 a003 a10 b2 c100
>>> items.sort(key=natural_key, reverse=True)
>>> for s in items:
... print s,
c100 b2 a10 a003 a2 a1 20 10 2 1
"""
import re
def natural_key(astr):
"""See http://www.codinghorror.com/blog/archives/001018.html"""
return [int(s) if s.isdigit() else s for s in re.split(r''(/d+)'', astr)]
def natural_cmp(a, b):
return cmp(natural_key(a), natural_key(b))
try: # use explorer''s comparison function if available
import ctypes
explorer_cmp = ctypes.windll.shlwapi.StrCmpLogicalW
except (ImportError, AttributeError):
# not on Windows or old python version
explorer_cmp = natural_cmp
if __name__ == ''__main__'':
import doctest; doctest.testmod()

Para admitir cadenas Unicode, debe usarse .isdigit() lugar de .isdigit() .

.isdigit() también puede fallar (valor de retorno que no es aceptado por int() ) para una cadena de bytes en Python 2 en algunas configuraciones regionales, por ejemplo, ''/ xb2'' (''²'') en la configuración regional cp1252 en Windows .

Answer 2

Aquí hay una limpieza del código en el artículo al que se vincula la pregunta:

def sorted_nicely(strings):
"Sort strings the way humans are said to expect."
return sorted(strings, key=natural_sort_key)
def natural_sort_key(key):
import re
return [int(t) if t.isdigit() else t for t in re.split(r''(/d+)'', key)]

Pero en realidad no he tenido ocasión de ordenar nada de esta manera.

Answer 3

En C ++ utilizo este código de ejemplo para hacer una ordenación natural. El código requiere la biblioteca de impulso.

Answer 4

En C, esta solución maneja correctamente los números con ceros a la izquierda:

#include <stdlib.h>
#include <ctype.h>
/* like strcmp but compare sequences of digits numerically */
int strcmpbynum(const char *s1, const char *s2) {
for (;;) {
if (*s2 == ''/0'')
return *s1 != ''/0'';
else if (*s1 == ''/0'')
return 1;
else if (!(isdigit(*s1) && isdigit(*s2))) {
if (*s1 != *s2)
return (int)*s1 - (int)*s2;
else
(++s1, ++s2);
} else {
char *lim1, *lim2;
unsigned long n1 = strtoul(s1, &lim1, 10);
unsigned long n2 = strtoul(s2, &lim2, 10);
if (n1 > n2)
return 1;
else if (n1 < n2)
return -1;
s1 = lim1;
s2 = lim2;
}
}
}

Si desea usarlo con qsort , use esta función auxiliar:

static int compare(const void *p1, const void *p2) {
const char * const *ps1 = p1;
const char * const *ps2 = p2;
return strcmpbynum(*ps1, *ps2);
}

Y puedes hacer algo del orden de

char *lines = ...;
qsort(lines, next, sizeof(lines[0]), compare);

Answer 5

Mi implementación en Clojure 1.1:

(ns alphanumeric-sort
(:import [java.util.regex Pattern]))
(defn comp-alpha-numerical
"Compare two strings alphanumerically."
[a b]
(let [regex (Pattern/compile "[//d]+|[a-zA-Z]+")
sa (re-seq regex a)
sb (re-seq regex b)]
(loop [seqa sa seqb sb]
(let [counta (count seqa)
countb (count seqb)]
(if-not (not-any? zero? [counta countb]) (- counta countb)
(let [c (first seqa)
d (first seqb)
c1 (read-string c)
d1 (read-string d)]
(if (every? integer? [c1 d1])
(def result (compare c1 d1)) (def result (compare c d)))
(if-not (= 0 result) result (recur (rest seqa) (rest seqb)))))))))
(sort comp-alpha-numerical ["a1" "a003" "b2" "a10" "a2" "1" "10" "20" "2" "c100"])

Resultado:

("1" "2" "10" "20" "a1" "a2" "a003" "a10" "b2" "c100")

Answer 6

Para MySQL, personalmente utilizo el código de un módulo de Drupal, que está disponible en hhttp: //drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x: /natsort.install.mysql

Básicamente, ejecutas el script SQL publicado para crear funciones y luego utilizas ORDER BY natsort_canon(field_name, ''natural'')

Aquí hay un archivo léame sobre la función: http://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/README.txt

Answer 7

Para Tcl, la opción -dict (dictionary) para lsort:

% lsort -dict {a b 1 c 2 d 13}
1 2 13 a b c d

Answer 8

Python, usando itertools:

def natural_key(s):
return tuple(
int(''''.join(chars)) if isdigit else ''''.join(chars)
for isdigit, chars in itertools.groupby(s, str.isdigit)
)

Resultado:

>>> natural_key(''abc-123foo456.xyz'')
(''abc-'', 123, ''foo'', 456, ''.xyz'')

Clasificación:

>>> sorted([''1.1.1'', ''1.10.4'', ''1.5.0'', ''42.1.0'', ''9'', ''banana''], key=natural_key)
[''1.1.1'', ''1.5.0'', ''1.10.4'', ''9'', ''42.1.0'', ''banana'']

Answer 9

Si el OP está preguntando sobre expresiones de ordenación idomáticas, entonces no todos los lenguajes tienen una expresión natural incorporada. Para c, iría a <stdlib.h> y usaría qsort . Algo en las líneas de:

/* non-functional mess deleted */

para ordenar los argumentos en orden léxico Lamentablemente, este modismo es bastante difícil de analizar para aquellos que no utilizan las formas de c.

Adecuadamente castigado por el voto a favor, de hecho leí el artículo vinculado. Mea culpa.

En cualquier caso, el código original no funcionó, excepto en el caso único que probé. Maldita sea. Plain vanilla c no tiene esta función, ni está en ninguna de las bibliotecas habituales.

El código siguiente ordena los argumentos de línea de comando de forma natural como vinculados. Caveat Emptor ya que solo se prueba ligeramente.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int naturalstrcmp(const char **s1, const char **s2);
int main(int argc, char **argv){
/* Sort the command line arguments in place */
qsort(&argv[1],argc-1,sizeof(char*),
(int(*)(const void *, const void *))naturalstrcmp);
while(--argc){
printf("%s/n",(++argv)[0]);
};
}
int naturalstrcmp(const char **s1p, const char **s2p){
if ((NULL == s1p) || (NULL == *s1p)) {
if ((NULL == s2p) || (NULL == *s2p)) return 0;
return 1;
};
if ((NULL == s2p) || (NULL == *s2p)) return -1;
const char *s1=*s1p;
const char *s2=*s2p;
do {
if (isdigit(s1[0]) && isdigit(s2[0])){
/* Compare numbers as numbers */
int c1 = strspn(s1,"0123456789"); /* Could be more efficient here... */
int c2 = strspn(s2,"0123456789");
if (c1 > c2) {
return 1;
} else if (c1 < c2) {
return -1;
};
/* the digit strings have equal length, so compare digit by digit */
while (c1--) {
if (s1[0] > s2[0]){
return 1;
} else if (s1[0] < s2[0]){
return -1;
};
s1++;
s2++;
};
} else if (s1[0] > s2[0]){
return 1;
} else if (s1[0] < s2[0]){
return -1;
};
s1++;
s2++;
} while ( (s1!=''/0'') || (s2!=''/0'') );
return 0;
}

Este enfoque es bastante fuerza bruta, pero es simple y probablemente pueda duplicarse en cualquier lenguaje imperativo.

Answer 10

Solo un enlace a un buen trabajo en Common Lisp por Eric Normand:

http://www.lispcast.com/wordpress/2007/12/human-order-sorting/

Answer 11

Solo uso StrCmpLogicalW . Hace exactamente lo que Jeff quiere, ya que es la misma API que usa el explorador. Es cierto que no es portátil.

En C ++:

bool NaturalLess(const wstring &lhs, const wstring &rhs)
{
return StrCmpLogicalW(lhs.c_str(), rhs.c_str()) < 0;
}
vector<wstring> strings;
// ... load the strings
sort(strings.begin(), strings.end(), &NaturalLess);

Answer 12

Tenga en cuenta que para la mayoría de estas preguntas, puede consultar el Wiki del Código Rosetta . Adapte mi respuesta de la entrada para ordenar enteros.

En el lenguaje de programación de un sistema, hacer algo como esto generalmente va a ser más feo que con un lenguaje de manejo de cadenas especial. Afortunadamente para Ada, la versión más reciente tiene una rutina de biblioteca para este tipo de tareas.

Para Ada 2005, creo que podría hacer algo en las siguientes líneas (advertencia, no compilado):

type String_Array is array(Natural range <>) of Ada.Strings.Unbounded.Unbounded_String;
function "<" (L, R : Ada.Strings.Unbounded.Unbounded_String) return boolean is
begin
--// Natural ordering predicate here. Sorry to cheat in this part, but
--// I don''t exactly grok the requirement for "natural" ordering. Fill in
--// your proper code here.
end "<";
procedure Sort is new Ada.Containers.Generic_Array_Sort
(Index_Type => Natural;
Element_Type => Ada.Strings.Unbounded.Unbounded_String,
Array_Type => String_Array
);

Ejemplo de uso:

 using Ada.Strings.Unbounded;
Example : String_Array := (To_Unbounded_String ("Joe"),
To_Unbounded_String ("Jim"),
To_Unbounded_String ("Jane"),
To_Unbounded_String ("Fred"),
To_Unbounded_String ("Bertha"),
To_Unbounded_String ("Joesphus"),
To_Unbounded_String ("Jonesey"));
begin
Sort (Example);
...
end;

Answer 13

php tiene una función fácil "natsort" para hacer eso, y yo lo implemento solo:

<?php
$temp_files = array(''+===='',''-=='',"temp15-txt","temp10.txt",
"temp1.txt","tempe22.txt","temp2.txt");
$my_arr = $temp_files;
natsort($temp_files);
echo "Natural order: ";
print_r($temp_files);
echo "My Natural order: ";
usort($my_arr,''my_nat_func'');
print_r($my_arr);
function is_alpha($a){
return $a>=''0''&&$a<=''9'' ;
}
function my_nat_func($a,$b){
if(preg_match(''/[0-9]/'',$a)){
if(preg_match(''/[0-9]/'',$b)){
$i=0;
while(!is_alpha($a[$i])) ++$i;
$m = intval(substr($a,$i));
$i=0;
while(!is_alpha($b[$i])) ++$i;
$n = intval(substr($b,$i));
return $m>$n?1:($m==$n?0:-1);
}
return 1;
}else{
if(preg_match(''/[0-9]/'',$b)){
return -1;
}
return $a>$b?1:($a==$b?0:-1);
}
}

Answer 14

JavaScript

Array.prototype.alphanumSort = function(caseInsensitive) {
for (var z = 0, t; t = this[z]; z++) {
this[z] = [], x = 0, y = -1, n = 0, i, j;
while (i = (j = t.charAt(x++)).charCodeAt(0)) {
var m = (i == 46 || (i >=48 && i <= 57));
if (m !== n) {
this[z][++y] = "";
n = m;
}
this[z][y] += j;
}
}
this.sort(function(a, b) {
for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) {
if (caseInsensitive) {
aa = aa.toLowerCase();
bb = bb.toLowerCase();
}
if (aa !== bb) {
var c = Number(aa), d = Number(bb);
if (c == aa && d == bb) {
return c - d;
} else return (aa > bb) ? 1 : -1;
}
}
return a.length - b.length;
});
for (var z = 0; z < this.length; z++)
this[z] = this[z].join("");
}

Source