Jump to content

Ordenar strings que com letras e numeros


Ballister
 Share

Recommended Posts

Boas pessoal

Precisava de umas ideias para ordenar strings que representam matriculas de carros no formato portugues..

o que pretendo e q no fim saiam as do tipo LL-NN-NN, dps NN-NN-LL e por fim as do tipo NN-LL-NN

Alguem me pode dar um empurraozinho ??

Obrigado  👍

Link to comment
Share on other sites

Esse problema fez-me lembrar a solução que usei para um problema da fase de qualificação das ONI de 2008 (http://www.dcc.fc.up.pt/oni/problemas/2008/qualificacao/probA.html).

A estratégia que usei, foi transformar cada matrícula num número, transformando um array de 7 dimensões num número.

Vou-te dar um exemplo de como fazer isso, com um array de duas dimensões.

Imagina que tens um array de duas dimensões, cada dimensão com três elementos (imaginemos que todos os espaços são preenchidos por um 1), então tens:

    0 1 2

    ------

0| 1 1 1

1| 1 1 1

2| 1 1 1

Para transformar isso num array de uma dimensão, podes fazer o seguinte:

1 1 1 | 1 1 1 | 1 1 1

Para aceder a uma certa posição (i,j), no array unidimensional, podes usar esta fórmula:

i*3+j

Em que o 3 representa o número de elementos em cada subelemento.

Podes generalizar isto.

Se tiveres um array de tridimensional, com as seguintes dimensões: [4,3,2], e quiseres aceder ao elemento na posição (i,j,k), num array de uma dimensão, podes usar a fórmula:

i*3*2+j*2+k

Este método de converter arrays de várias dimensões num array de uma dimensão tem um nome, mas não me lembro qual.

Agora temos de aplicar isto às matrículas.

Podes considerar cada matrícula como um elemento num array de 7 dimensões, com os seguintes tamanhos: [3][23][23][10][10][10][10].

A maior dimensão representa qual dos três tipos de matrículas estamos a observar. o seguinte par representa o conjunto de letras do alfabeto, o seguinte par o primeiro conjunto de dígitos na matrícula, e o último par o segundo conjunto de dígitos na matrícula (nota que, apesar de cada tipo ter uma ordem diferente de grupos de letras/dígitos, visto que distinguimos os três tipos na primeira dimensão, é indiferente a ordem em que os pomos, desde que sejamos consistentes).

Assim, para converter uma matrícula num número, basta verificar qual o tipo de matrícula, de acordo com a posição dos dígitos, e converter em números. Para ordenar, basta usar um quick sort ou outro tipo de sort, e uma função de comparação que devolva qual das matrículas é maior de acordo com o número em que convertemos.

Um pormenor: as letras são transformadas em números primeiros (podes fazer isso em C, subtraindo 'A'. Além disso é preciso ter em conta que o 'K', o 'W' e o 'Y' não existem nas matrículas portuguesas, logo temos de tratar as letras acima de K, subtraindo um 1, e o X -- posição 21 -- e o Z -- posição 22 --, como letras especiais).

Um exemplo:

Para calcular o número da matrícula matrícula 00-99-XM, primeiro verificamos qual o seu tipo (é o segundo tipo -- valor 1), e convertemos as letras para número (X -- 21, M -- 11; estas posição começam no 0). Depois só temos de converter isto numa posição de uma array unidimensional:

1*23*23*10*10*10*10 + 21*23*10*10*10*10 + 11*10*10*10*10 + 0*10*10*10 + 0*10*10 + 9*10 + 9 = 10230099

Assim, chegamos à conclusão que esta matrícula foi a 10230099ª a ser feita.

Com estas posições, consegues então saber se uma matrícula é mais recente ou mais antiga, e assim podes ordená-la.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.