Nos comentários de artigos anteriores, ocasionalmente há censuras - por que estudar outras classificações, se já existe a classificação Rápida mais rápida do mundo. Dizem que todo esse exótico fantasioso não tem utilidade e ninguém precisa.


Percy Diaconis , que estudou triagem de paciência, acredita que é a maneira mais rápida de organizar manualmente um baralho de cartas.

Portanto, se um matemático respeitado (e um mágico experiente em cartas) não mentir, então, com o valor prático do algoritmo, tudo estará em ordem.

Agora observe suas mãos.

Estágio 1. Deitado em pilhas

Então, pegue os vermes do convés. Eles representarão uma matriz de treze elementos aleatórios.



Precisamos decompor as cartas em várias pilhas, para que em cada pilha as cartas sejam uma sequência ordenada.

Em outras palavras, nossa tarefa neste estágio é criar rapidamente vários subarrays ordenados a partir da matriz não classificada existente. Ao mesmo tempo, é altamente desejável que o número desses subarrays seja menor, o que significa que você precisa se esforçar para garantir que os subarrays sejam mais autênticos. Isso é feito da seguinte maneira.

A primeira carta é o começo da primeira pilha.



Transferimos as cartas para essa pilha, por sua vez, até que a próxima carta transferida seja menor que a primeira da pilha.

Além disso, cada pilha é uma pilha - não trabalhamos com a pilha inteira, mas apenas com a carta de cima, que foi colocada por último.



Se a carta atual for mais do que o mínimo na pilha, você precisará criar uma nova pilha, a carta atual abrirá uma nova pilha.



A ordem das pilhas é importante! Se o número deles já for maior que um, colocamos a próxima carta não na última pilha, mas na pilha mais à esquerda, na qual podemos colocá-la.

Agora, depois da dama, preciso anexar nove em algum lugar. Mecanicamente, quero colocar a carta na segunda pilha, mas na primeira pilha a carta do topo tem mais de nove. Portanto, podemos continuar a primeira pilha sem violar sua ordem. Os próximos três, que seguem os nove, também a propósito, vão para a primeira pilha.



Sete e seis não podem ser adicionados à primeira pilha (eles são maiores que a carta do topo), mas ainda têm um lugar na segunda pilha.



Ace começa uma nova pilha. A ninharia restante cai em bandejas diferentes, dependendo da distância à esquerda da pilha onde ela pode ser inserida.



Como resultado, os cartões são dispostos em várias pilhas. Em cada pilha, as cartas são uma sequência decrescente, no topo - a menor carta. Pilhas são pilhas.

Como tentamos primeiro preencher as pilhas que estavam à esquerda, formamos a menor quantidade possível. Se passássemos pela matriz e extraíssemos as sub-matrizes decrescentes, a pilha naturalmente ficaria muito maior.

Etapa 2. A linha inferior

Mova as cartas principais disponíveis um pouco para baixo, para que elas fiquem em uma fila separada. Se as pilhas forem pilhas, trabalharemos com a linha inferior como com uma fila.



É importante ressaltar que os cartões principais disponíveis nas pilhas também são uma sequência ordenada. A linha inferior já está classificada em ordem crescente. O que não é surpreendente - ao formar pilhas de cartões, cartões menores foram enviados para a esquerda.

No futuro, até o final da classificação, não estaremos interessados ​​em todas as cartas colocadas na mesa. Apenas estes são necessários:

• O cartão mais à esquerda (vamos chamá-lo de atual) na linha inferior da fila.
• Em stacks-stacks, trabalhamos apenas com as melhores cartas disponíveis. Nesse caso, apenas as pilhas localizadas diretamente no mapa atual e à esquerda são necessárias. As pilhas que estão à direita neste momento não são necessárias.

Na linha inferior, classificamos as cartas da esquerda para a direita. O mais à esquerda é o mínimo atual, retornamos à linha superior original. Ao mesmo tempo, toda vez que retornamos à base outro cartão, é necessário colocar outro em seu lugar. De onde obtê-lo? Das pilhas que estão acima do mapa atual e à esquerda dele - entre as cartas disponíveis, é selecionado um mínimo que se move para a posição vaga da carta esquerda atual na linha inferior e daí para a matriz principal.

Dois na matriz retornam imediatamente. O lugar vago é ocupado pelo triplo (nós o movemos da primeira pilha para a linha inferior) e, da linha inferior, o triplo, no mínimo, vai para a matriz principal. Nas duas primeiras pilhas, o mínimo é pesquisado novamente - estas são as quatro - que também vai para casa. Cinco se torna o mínimo atual, etc.



Combinando o trabalho com uma ordem crescente da fila e uma ordem decrescente das pilhas muito rapidamente, obtemos todos os elementos do mínimo ao máximo. Algo assim, em geral.

Animação deste processo.



Se você traduzir tudo o que foi mencionado acima em Python, obtém o seguinte:

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles]) 

Referências

Classificação de paciência ( Google-translate )

Fonte de classificação de paciência

Princeton CS: subsequência crescente mais longa

Combinação de pilhas de classificação de paciência ( Google-translate )

Resumos da Wiki: classificação de pacientes

Palavra alinhada ( Google-translate )

Artigos da série:

• Aplicativo Excel AlgoLab.xlsm
• Classificações de Câmbio
• Classificações de inserção
  • Bibliotecário
  • Paciência Sort
  • Classificar "Torre de Hanói"
  • Classificação de mesa jovem
  • Inverter classificação
  • Inserir comparação de classificação
• Classificar por seleção
• Mesclar classificações
• Classificar por distribuição
• Classificação híbrida

No aplicativo AlgoLab, essa classificação agora está ativa. Ao mesmo tempo, a visualização é possível em dois modos: na forma de mapas (o modo padrão) e simplesmente na forma de números. No entanto, para o estilo de cartas, é necessário que a diferença entre os elementos máximo e mínimo na matriz seja menor que 54 (o número de cartas no baralho, incluindo dois coringas). Se essa condição não for atendida ou o modo do cartão estiver desativado por completo (para isso, você precisa escrever card = 0 no comentário da célula com o nome da classificação), a visualização será na forma de números sem graça.

Os fatos são considerados na ordem de preferência antiguidade: picos <clubes <pandeiros <corações.


Ou seja, qualquer carta de um pandeiro de um pandeiro é maior que qualquer carta de um naipe de clube, qualquer carta de um naipe de copas é maior que qualquer carta de um naipe de pique, etc. Se fizermos uma analogia com números, os picos serão de 0 a 9, os clubes serão de 10 a 19, os diamantes serão de 20 a 29, os corações serão de 30 a 39 (sim, é claro, dentro do naipe o número de cartas não é exatamente dez, mas você entende o que se entende). Quanto à antiguidade dentro do processo , será comum: de dois para um ás. Você também pode levar os curingas mais velhos que todos os outros cartões. Nesse caso, o curinga vermelho é mais pesado que o preto.

Este artigo foi escrito com o apoio da EDISON Software, uma empresa profissional de desenvolvimento web que redesenhou recentemente seu site.