Python ont une fonction intégrée de la chaîne naturelle de tri?

Essayez ceci:

import re

def natural_sort(l): 
    convert = lambda text: int(text) if text.isdigit() else text.lower() 
    alphanum_key = lambda key: [ convert(c) for c in re.split('([0-9]+)', key) ] 
    return sorted(l, key = alphanum_key)

De sortie:

['elm0', 'elm1', 'Elm2', 'elm9', 'elm10', 'Elm11', 'Elm12', 'elm13']

Voir en ligne: ideone.

Code adapté à partir d'ici: De tri pour les êtres Humains : Naturel, l'Ordre de Tri.

J'ai écrit une fonction sur la base http://www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html qui ajoute la possibilité de toujours passer dans votre propre paramètre 'key'. J'ai besoin de ce dans le but d'effectuer un naturel de tri de listes qui contiennent des objets plus complexes (et pas seulement des chaînes de caractères).

import re

def natural_sort(list, key=lambda s:s):
    """
    Sort the list into natural alphanumeric order.
    """
    def get_alphanum_key_func(key):
        convert = lambda text: int(text) if text.isdigit() else text 
        return lambda s: [convert(c) for c in re.split('([0-9]+)', key(s))]
    sort_key = get_alphanum_key_func(key)
    list.sort(key=sort_key)

Par exemple:

my_list = [{'name':'b'}, {'name':'10'}, {'name':'a'}, {'name':'1'}, {'name':'9'}]
natural_sort(my_list, key=lambda x: x['name'])
print my_list
[{'name': '1'}, {'name': '9'}, {'name': '10'}, {'name': 'a'}, {'name': 'b'}]

Donné:

data=['Elm11', 'Elm12', 'Elm2', 'elm0', 'elm1', 'elm10', 'elm13', 'elm9']

Similaire à Serge de solution, un 1-liner sans bibliothèques externes serait:

data.sort(key=lambda x : int(x[3:]))

ou

sorted_data=sorted(data, key=lambda x : int(x[3:]))

Explication:

Cette solution utilise le clé fonction de sorte de définir une fonction qui va être utilisé pour le tri. Parce que nous savons que chaque entrée est précédée par "l'orme" la fonction de tri convertit en entier la partie de la chaîne après la 3e personnage (c'est à dire de type int(x[3:])). Si la partie numérique de données est dans un emplacement différent, cette partie de la fonction serait de changer.

Acclamations

Une option est de transformer la chaîne de caractères dans un n-uplet et remplacer des caractères à l'aide forme développée http://wiki.answers.com/Q/What_does_expanded_form_mean

de cette façon a90 deviendrait ("un",90,0) et a1 deviendrait ("a",1)

ci-dessous est un exemple de code (qui n'est pas très efficace en raison de la façon dont Elle supprime 0 de nombres)

alist=["something1",
    "something12",
    "something17",
    "something2",
    "something25and_then_33",
    "something25and_then_34",
    "something29",
    "beta1.1",
    "beta2.3.0",
    "beta2.33.1",
    "a001",
    "a2",
    "z002",
    "z1"]

def key(k):
    nums=set(list("0123456789"))
        chars=set(list(k))
    chars=chars-nums
    for i in range(len(k)):
        for c in chars:
            k=k.replace(c+"0",c)
    l=list(k)
    base=10
    j=0
    for i in range(len(l)-1,-1,-1):
        try:
            l[i]=int(l[i])*base**j
            j+=1
        except:
            j=0
    l=tuple(l)
    print l
    return l

print sorted(alist,key=key)

de sortie:

('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 1)
('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 10, 2)
('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 10, 7)
('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 2)
('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 20, 5, 'a', 'n', 'd', '_', 't', 'h', 'e', 'n', '_', 30, 3)
('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 20, 5, 'a', 'n', 'd', '_', 't', 'h', 'e', 'n', '_', 30, 4)
('s', 'o', 'm', 'e', 't', 'h', 'i', 'n', 'g', 20, 9)
('b', 'e', 't', 'a', 1, '.', 1)
('b', 'e', 't', 'a', 2, '.', 3, '.')
('b', 'e', 't', 'a', 2, '.', 30, 3, '.', 1)
('a', 1)
('a', 2)
('z', 2)
('z', 1)
['a001', 'a2', 'beta1.1', 'beta2.3.0', 'beta2.33.1', 'something1', 'something2', 'something12', 'something17', 'something25and_then_33', 'something25and_then_34', 'something29', 'z1', 'z002']

Valeur De Ce Post

Mon point est d'offrir à un non regex solution qui peut s'appliquer de manière générale.

Je vais créer trois fonctions:

1. find_first_digit qui j'ai emprunté de @AnuragUniyal. Il va trouver la position du premier chiffre ou non de chiffres dans une chaîne de caractères.
2. split_digits qui est un générateur qui prend en outre une chaîne en chiffres et non des chiffres morceaux. Il sera également yield des entiers quand c'est un chiffre.
3. natural_key juste enveloppements split_digits dans un tuple. C'est ce que nous utilisons comme une clé pour sorted, max, min.

Fonctions

def find_first_digit(s, non=False):
for i, x in enumerate(s):
if x.isdigit() ^ non:
return i
return -1
def split_digits(s, case=False):
non = True
while s:
i = find_first_digit(s, non)
if i == 0:
non = not non
elif i == -1:
yield int(s) if s.isdigit() else s if case else s.lower()
s = ''
else:
x, s = s[:i], s[i:]
yield int(x) if x.isdigit() else x if case else x.lower()
def natural_key(s, *args, **kwargs):
return tuple(split_digits(s, *args, **kwargs))

On peut voir que c'est général que nous pouvons avoir plusieurs chiffres morceaux:

# Note that the key has lower case letters
natural_key('asl;dkfDFKJ:sdlkfjdf809lkasdjfa_543_hh')
('asl;dkfdfkj:sdlkfjdf', 809, 'lkasdjfa_', 543, '_hh')

Ou laisser comme sensible à la casse:

natural_key('asl;dkfDFKJ:sdlkfjdf809lkasdjfa_543_hh', True)
('asl;dkfDFKJ:sdlkfjdf', 809, 'lkasdjfa_', 543, '_hh')

---

Nous pouvons voir qu'il trie les OP de la liste, dans l'ordre

sorted(
['elm0', 'elm1', 'Elm2', 'elm9', 'elm10', 'Elm11', 'Elm12', 'elm13'],
key=natural_key
)
['elm0', 'elm1', 'Elm2', 'elm9', 'elm10', 'Elm11', 'Elm12', 'elm13']

Mais il peut gérer plus compliqué listes ainsi:

sorted(
['f_1', 'e_1', 'a_2', 'g_0', 'd_0_12:2', 'd_0_1_:2'],
key=natural_key
)
['a_2', 'd_0_1_:2', 'd_0_12:2', 'e_1', 'f_1', 'g_0']

---

Ma regex équivalent serait

def int_maybe(x):
return int(x) if str(x).isdigit() else x
def split_digits_re(s, case=False):
parts = re.findall('\d+|\D+', s)
if not case:
return map(int_maybe, (x.lower() for x in parts))
else:
return map(int_maybe, parts)
def natural_key_re(s, *args, **kwargs):
return tuple(split_digits_re(s, *args, **kwargs))

Plus susceptibles functools.cmp_to_key() est étroitement liée à l'implémentation sous-jacente de python de la sorte. En outre, la cmp paramètre est l'héritage. La façon moderne est de transformer des éléments d'entrée en objets qui prennent en charge l'souhaité riche d'opérations de comparaison.

En Vertu De Disponible 2.x, des objets de différents types peuvent être ordonnée même si le riche opérateurs de comparaison n'ont pas été mises en œuvre. En Vertu De Disponible 3.x, des objets de types différents devez explicitement de soutenir la comparaison. Voir Comment Python comparer string et int? qui relie le la documentation officielle. La plupart des réponses dépendent de l'implicite de la commande. De commutation pour Python 3.x nécessitera un nouveau type de mettre en œuvre et d'unifier les comparaisons entre les nombres et les chaînes de caractères.

Python 2.7.12 (default, Sep 29 2016, 13:30:34) 
>>> (0,"foo") < ("foo",0)
True  

Python 3.5.2 (default, Oct 14 2016, 12:54:53) 
>>> (0,"foo") < ("foo",0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: int() < str()

Il existe trois approches différentes. Le premier utilise des classes imbriquées à prendre avantage de Python Iterable de l'algorithme de comparaison. La deuxième se déroule cette imbrication dans une seule classe. La troisième renonce à sous-classement str de se concentrer sur la performance. Tous sont chronométrés; la seconde est deux fois plus rapide tandis que le troisième près de six fois plus. Sous-classement str n'est pas nécessaire, et était probablement une mauvaise idée en premier lieu, mais il ne viennent avec certaines convenances.

Le genre de personnages sont dupliqués à la force de la commande par cas, et le cas échangés à la force d'une lettre minuscule pour trier d'abord; c'est le cas typique de la définition de "naturel de tri". Je ne pouvais pas décider sur le type de groupement; certains préféreront peut-être la suivante, ce qui apporte également d'importants avantages de performance:

d = lambda s: s.lower()+s.swapcase()

S'il y a lieu, les opérateurs de comparaison sont à object donc ils ne seront pas être ignoré par functools.total_ordering.

import functools
import itertools
@functools.total_ordering
class NaturalStringA(str):
def __repr__(self):
return "{}({})".format\
( type(self).__name__
, super().__repr__()
)
d = lambda c, s: [ c.NaturalStringPart("".join(v))
for k,v in
itertools.groupby(s, c.isdigit)
]
d = classmethod(d)
@functools.total_ordering
class NaturalStringPart(str):
d = lambda s: "".join(c.lower()+c.swapcase() for c in s)
d = staticmethod(d)
def __lt__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
try:
return int(self) < int(other)
except ValueError:
if self.isdigit():
return True
elif other.isdigit():
return False
else:
return self.d(self) < self.d(other)
def __eq__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
try:
return int(self) == int(other)
except ValueError:
if self.isdigit() or other.isdigit():
return False
else:
return self.d(self) == self.d(other)
__le__ = object.__le__
__ne__ = object.__ne__
__gt__ = object.__gt__
__ge__ = object.__ge__
def __lt__(self, other):
return self.d(self) < self.d(other)
def __eq__(self, other):
return self.d(self) == self.d(other)
__le__ = object.__le__
__ne__ = object.__ne__
__gt__ = object.__gt__
__ge__ = object.__ge__

import functools
import itertools
@functools.total_ordering
class NaturalStringB(str):
def __repr__(self):
return "{}({})".format\
( type(self).__name__
, super().__repr__()
)
d = lambda s: "".join(c.lower()+c.swapcase() for c in s)
d = staticmethod(d)
def __lt__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
groups = map(lambda i: itertools.groupby(i, type(self).isdigit), (self, other))
zipped = itertools.zip_longest(*groups)
for s,o in zipped:
if s is None:
return True
if o is None:
return False
s_k, s_v = s[0], "".join(s[1])
o_k, o_v = o[0], "".join(o[1])
if s_k and o_k:
s_v, o_v = int(s_v), int(o_v)
if s_v == o_v:
continue
return s_v < o_v
elif s_k:
return True
elif o_k:
return False
else:
s_v, o_v = self.d(s_v), self.d(o_v)
if s_v == o_v:
continue
return s_v < o_v
return False
def __eq__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
groups = map(lambda i: itertools.groupby(i, type(self).isdigit), (self, other))
zipped = itertools.zip_longest(*groups)
for s,o in zipped:
if s is None or o is None:
return False
s_k, s_v = s[0], "".join(s[1])
o_k, o_v = o[0], "".join(o[1])
if s_k and o_k:
s_v, o_v = int(s_v), int(o_v)
if s_v == o_v:
continue
return False
elif s_k or o_k:
return False
else:
s_v, o_v = self.d(s_v), self.d(o_v)
if s_v == o_v:
continue
return False
return True
__le__ = object.__le__
__ne__ = object.__ne__
__gt__ = object.__gt__
__ge__ = object.__ge__

import functools
import itertools
import enum
class OrderingType(enum.Enum):
PerWordSwapCase         = lambda s: s.lower()+s.swapcase()
PerCharacterSwapCase    = lambda s: "".join(c.lower()+c.swapcase() for c in s)
class NaturalOrdering:
@classmethod
def by(cls, ordering):
def wrapper(string):
return cls(string, ordering)
return wrapper
def __init__(self, string, ordering=OrderingType.PerCharacterSwapCase):
self.string = string
self.groups = [ (k,int("".join(v)))
if k else
(k,ordering("".join(v)))
for k,v in
itertools.groupby(string, str.isdigit)
]
def __repr__(self):
return "{}({})".format\
( type(self).__name__
, self.string
)
def __lesser(self, other, default):
if not isinstance(self, type(other)):
return NotImplemented
for s,o in itertools.zip_longest(self.groups, other.groups):
if s is None:
return True
if o is None:
return False
s_k, s_v = s
o_k, o_v = o
if s_k and o_k:
if s_v == o_v:
continue
return s_v < o_v
elif s_k:
return True
elif o_k:
return False
else:
if s_v == o_v:
continue
return s_v < o_v
return default
def __lt__(self, other):
return self.__lesser(other, default=False)
def __le__(self, other):
return self.__lesser(other, default=True)
def __eq__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
for s,o in itertools.zip_longest(self.groups, other.groups):
if s is None or o is None:
return False
s_k, s_v = s
o_k, o_v = o
if s_k and o_k:
if s_v == o_v:
continue
return False
elif s_k or o_k:
return False
else:
if s_v == o_v:
continue
return False
return True
# functools.total_ordering doesn't create single-call wrappers if both
# __le__ and __lt__ exist, so do it manually.
def __gt__(self, other):
op_result = self.__le__(other)
if op_result is NotImplemented:
return op_result
return not op_result
def __ge__(self, other):
op_result = self.__lt__(other)
if op_result is NotImplemented:
return op_result
return not op_result
# __ne__ is the only implied ordering relationship, it automatically
# delegates to __eq__

>>> import natsort
>>> import timeit
>>> l1 = ['Apple', 'corn', 'apPlE', 'arbour', 'Corn', 'Banana', 'apple', 'banana']
>>> l2 = list(map(str, range(30)))
>>> l3 = ["{} {}".format(x,y) for x in l1 for y in l2]
>>> print(timeit.timeit('sorted(l3+["0"], key=NaturalStringA)', number=10000, globals=globals()))
362.4729259099986
>>> print(timeit.timeit('sorted(l3+["0"], key=NaturalStringB)', number=10000, globals=globals()))
189.7340817489967
>>> print(timeit.timeit('sorted(l3+["0"], key=NaturalOrdering.by(OrderingType.PerCharacterSwapCase))', number=10000, globals=globals()))
69.34636392899847
>>> print(timeit.timeit('natsort.natsorted(l3+["0"], alg=natsort.ns.GROUPLETTERS | natsort.ns.LOWERCASEFIRST)', number=10000, globals=globals()))
98.2531585780016

Tri naturel est à la fois très compliqué et vaguement défini comme un problème. N'oubliez pas d'exécuter unicodedata.normalize(...) à l'avance, et envisager d'utiliser str.casefold() plutôt que str.lower(). Il y a probablement subtile problèmes d'encodage, je n'ai pas considéré. J'ai donc provisoirement recommander la natsort de la bibliothèque. J'ai pris un coup d'oeil rapide sur le dépôt github; le code de la maintenance a été stellaire.

Tous les algorithmes que j'ai vu dépendent des astuces telles que la duplication et l'abaissement des caractères, et d'échanger sur les cas. Tout cela double le temps d'exécution, une autre solution nécessiterait un total de l'ordre naturel à l'entrée du jeu de caractères. Je ne pense pas que ce est une partie de la spécification unicode, et depuis il y a beaucoup plus d'unicode chiffres que [0-9], la création d'un tel tri serait tout aussi redoutable. Si vous voulez locale-connaissance des comparaisons, préparez vos cordes avec paramètres régionaux.strxfrm par Python Tri COMMENT.

a = ['H1', 'H100', 'H10', 'H3', 'H2', 'H6', 'H11', 'H50', 'H5', 'H99', 'H8']
b = ''
c = []
def bubble(bad_list):#bubble sort method
length = len(bad_list) - 1
sorted = False
while not sorted:
sorted = True
for i in range(length):
if bad_list[i] > bad_list[i+1]:
sorted = False
bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i] #sort the integer list 
a[i], a[i+1] = a[i+1], a[i] #sort the main list based on the integer list index value
for a_string in a: #extract the number in the string character by character
for letter in a_string:
if letter.isdigit():
#print letter
b += letter
c.append(b)
b = ''
print 'Before sorting....'
print a
c = map(int, c) #converting string list into number list
print c
bubble(c)
print 'After sorting....'
print c
print a

Remerciements:

Tri À Bulles Devoirs

Comment lire une chaîne de caractères une lettre à la fois en python