Algoritmo per ordinare array

1

Prendi ad esempio questo array di input:

[2,7,1,4,9]

Per questo input, ho bisogno di produrre una matrice di 23 elementi totali che contiene due elementi di 2, sette elementi di 7, un elemento di 1, quattro elementi di 4 e nove elementi di 9. Esempio di matrice di output:

[2,2,7,7,7,7,7,7,7,1,4,4,4,4,9,...]

Tuttavia, questa matrice deve essere ordinata nel modo in cui riduce al minimo il numero degli stessi elementi che appaiono uno accanto all'altro . L'esempio di tale array sarebbe qualcosa di simile a questo:

[7,2,9,4,9,1,7,...]

L'obiettivo principale è ridurre al minimo il numero degli stessi elementi adiacenti.

L'obiettivo secondario è quello di distribuire elementi imparziali attraverso l'array risultante, se possibile.

Qualsiasi pseudo codice o C #, java, ... sarebbe utile.

    
posta Dusan 05.03.2014 - 18:09
fonte

2 risposte

4

Questo può essere visto come un problema del commesso viaggiatore :

  • ogni elemento è un nodo del tuo grafico, etichettato con il suo numero
  • ci sono spigoli tra ogni coppia di nodi
  • la "distanza" di passaggio da un nodo a un altro è 0 se le etichette hanno numeri diversi e 1 se i numeri sono uguali

Ora stai cercando un percorso attraverso questo grafico riducendo al minimo la distanza totale. Google per

           traveling salesman <your_favorite_programming_language>

e troverai tonnellate di implementazioni di esempio con approcci euristici o forza bruta.

    
risposta data 05.03.2014 - 18:38
fonte
1

L'array risultante ha solo bisogno di separare gli elementi più grandi, qualsiasi elemento più piccolo sarà banalmente separato dagli elementi più grandi. Quindi se abbiamo 9, 7, 4 e 2:

999999999
9797979797979799
97 97 97 97 97 97 97 94 9

E ora è facile, perché ci sono sempre abbastanza spazi per inserire numeri più piccoli (iniziando a sinistra)

974 974 974 972 972 97 97 94 9
    
risposta data 05.03.2014 - 22:37
fonte

Leggi altre domande sui tag