Na tentativa de não reinventar uma roda, estou perguntando se alguém tem ideias sobre um algoritmo de homogeneidade de dados. Um breve exemplo:
Meus dados têm vários elementos, talvez como
- Número
- Cor
- Fruta
- Carta
Existem cerca de 100 desses elementos em uma matriz. O algoritmo precisa classificar os elementos para que quaisquer 2 entradas com o mesmo número sejam espaçadas uma da outra o máximo possível, e o mesmo com cores, frutas etc. Também seria bom se eu pudesse priorizar os elementos. Parece que você nunca chegaria a 100%, então você daria um número de passes para fazer, confira o resultado e tente mais passes.
Eu não ficaria surpreso se há algo aqui que simplesmente funciona que eu não tenho google-fu suficiente para encontrar.
algorithms
data
sorting
ExoByte
fonte
fonte
Respostas:
Isso meio que me incomodou por um tempo, então eu tive que vir ver se estava resolvido. Aqui está a minha ideia. Do zero, não é uma aplicação de nenhum algoritmo que eu conheço. Esse seria um algoritmo de força bruta bastante caro, mas deveria ser bastante eficaz. Supõe-se que você esteja lidando com o conjunto de dados realmente pequeno que você descreveu (100 linhas de 4 colunas) e esteja trabalhando em computadores modernos com memória RAM suficiente.
Visão geral : usamos um algoritmo recursivo em uma lista classificada para dispersar registros semelhantes à sua distância máxima dentro de registros semelhantes. Após cada chamada, todos os registros com o mesmo pai estão em sua distância máxima. A chamada superior inclui todos os registros. Por isso, desagrega de dentro para fora.
Estruturas de dados :
newIndexes
é umarray<integer>
. O índice da matriz é o índice existente da linha. O valor será o novo índice, começa com -1data
é umarray<array<string>>
. A chave é o índice, a matriz interna é uma representação de string dos valores em uma linha. Não precisa ser uma sequência se você tiver alguma maneira de agrupar seus dados. O primeiro elemento da matriz é aquele com o maior peso.Classifique
data
por ordem de peso. Classifique-o primeiro pela coluna com maior peso, dentro da coluna com o segundo maior peso, etc. O resultado é o inverso do que você deseja. Índice sequencialmente.Aqui está o algoritmo (no código psudo).
Em seguida, aplique os newIndexes aos dados a serem não classificados.
Considerações sobre a abordagem: não testamos isso, mas o armazenamento dos novos Índices e a resolução de conflitos podem ser problemáticos, pois os primeiros índices são atribuídos com base em colunas menos significativas; portanto, se houver muitos conflitos, as colunas mais significativas poderão se agrupar. Pode-se tentar aplicar o deslocamento como positivo primeiro e depois negativo. Ou, possivelmente, faça esse tipo de inserção em uma lista vinculada, em vez de em uma matriz.
fonte
Isso me lembra um algoritmo de rede que eu vi, a palavra-chave
'tkwikibrowser''TouchGraphWikiBrowser', onde os elementos são combinados com um tipo de elástico, mas são como ímãs do mesmo pol.Eu não sei o que seria a mecânica, puxando no seu caso, mas talvez 'case' seja a palavra-chave certa: os elementos são colocados em um caso e são empurrados para longe da borda do caso e afastados um do outro , mais ainda, se eles tiverem vários atributos em comum.
Eles começam em posições aleatórias, movem-se dependendo da distância da parede e da distância de elementos similares, e buscam uma posição estável.
A fórmula para se afastar pode ser linear ou quadrática à distância, e você pode procurar uma boa fórmula ao vivo, manipulando os valores.
atualizar:
Para o poder de atração, você pode simplesmente assumir o inverso do poder de distração. Portanto, se 2 elementos não compartilharem um único atributo, essa seria a atração máxima.
fonte
Use uma ordem aleatória aleatória ou classifique por um hash dos dados concatenados: um bom hash fornece saídas altamente diferentes para entradas semelhantes; portanto, as entradas semelhantes em qualquer dimensão devem ser separadas.
fonte