Algoritmo de datos "unort" / homogeneidad

8

En un intento por no reinventar una rueda, pregunto si alguien tiene ideas sobre un algoritmo de homogeneidad de datos. Un breve ejemplo:

Mis datos tienen varios elementos que pueden gustar

  1. número
  2. color
  3. fruta
  4. Carta

Hay alrededor de 100 de estos elementos en una matriz. El algoritmo debe ordenar los elementos para que cualquier 2 entradas con el mismo número se separen entre sí tanto como sea posible, y lo mismo con el color, la fruta, etc. También sería bueno Si pudiera priorizar los elementos. Se siente como si nunca hubieras alcanzado el 100%, así que le darías una serie de pases, comprueba el resultado y luego intenta más pases.

No me sorprendería si hay algo aquí que simplemente funciona y no tengo suficiente google-fu para encontrar.

    
pregunta ExoByte 29.07.2011 - 02:21

3 respuestas

2

Esto me molestó por un tiempo, así que tuve que venir a ver si se resolvió. Aquí está mi idea. Desde cero, no es una aplicación de ningún algoritmo que conozca. Este sería un algoritmo de fuerza bruta bastante costoso, pero debería ser bastante efectivo. Se asume que usted está tratando con el conjunto de datos realmente pequeño que describió (100 filas de 4 columnas) y está trabajando en una computadora moderna con suficiente ram.

Descripción general : usamos un algoritmo recursivo en una lista ordenada para dispersar registros similares a su distancia máxima dentro de registros similares. Después de cada llamada, todos los registros con el mismo padre están a su distancia máxima. La llamada superior incluye todos los registros. Así que se desordena desde adentro hacia afuera.

Estructuras de datos :

  • newIndexes es un array<integer> . El índice de la matriz es el índice existente de la fila. El valor será el nuevo índice, comienza con -1
  • data es un array<array<string>> . La clave es el índice, la matriz interna es una representación de cadena de los valores en una fila. No es necesario que sea una cadena si tiene alguna forma de agrupar sus datos. El primer elemento de la matriz es el que tiene el mayor peso.

Ordenar data por orden de peso. Clasifíquelo primero por la columna con el mayor peso, dentro de eso por la columna con el segundo mayor peso, etc. El resultado es el inverso de lo que desea. Índice secuencialmente.

Aquí está el algoritmo (en código psudo).

        // siblingCount: On first call is the number of rows in the table,
    //    on recursive calls it is the number of elements with the same parent
    // index: the index of current row in 'data' - starts 0
    // depth: The element index - starts 0
    void unsort(int siblingCount, int index, int depth)
    {
        int count = 1;
        string hash = concatColumns(index, depth + 1);
        while ((index + count < data.count) && (hash == concatColumns(index + count, depth + 1)))
        {
            count++;
        }

        if (depth < columnCount)
            unsort(count, index, depth);
        else if (index < data.count)
            unsort(count, index + count, 0);

        int spacing = siblingCount / count;

        for (int i = 0; i < count; i++)
        {
            var offset = 0;
            while ((newIndexes[index + i + offset] > -1) & (index + i + offset + 1 < newIndexes.count))
                offset++;

            if (newIndexes[index + i + offset] > -1) throw new Exception("Shouldn't happen.");

            newIndexes[index + i + offset] = index + spacing * i;
        }
    }

    string concatColumns(int index, int count) // returns count columns concatinated
    {
        // 1,1 = "1"
        // 1,2 = "1, blue"
        // 1,3 = "1, blue, apple"
        return "1, blue, apple";
    } 

A continuación, aplique los nuevos índices a los datos que se van a desordenar.

Reflexiones sobre el enfoque: no probé esto, pero el almacenamiento de los nuevos índices y la resolución de conflictos puede ser problemático, ya que los primeros índices se asignan según las columnas menos significativas, por lo que si hay muchos conflictos, entonces las columnas más significativas puede agruparse. Puede intentar aplicar offset como positivo primero, luego negativo. O posiblemente haga una especie de inserción en una lista vinculada en lugar de una matriz.

    
respondido por el Jim McKeeth 30.07.2011 - 01:47
4

Eso me recuerda a algunos algoritmos de red que he visto, palabra clave 'tkwikibrowser' 'TouchGraphWikiBrowser', donde los elementos se combinan con una especie de banda de goma, pero son como imanes de la misma pol.

No sé cuál sería la mecánica, en su caso, pero tal vez "caso" sea la palabra clave correcta: los elementos se colocan en un caso, se alejan del borde del caso y se presionan se alejan, más aún, si tienen varios atributos en común.

Comienzan en posiciones aleatorias y se mueven en función de la distancia a la pared y de la distancia a elementos similares, y buscan una posición estable.

La fórmula para alejarse mutuamente podría ser lineal o cuadrática a la distancia, y podría buscar una buena fórmula en vivo, manipulando los valores.

actualización:

Para el poder de atracción, simplemente puede tomar el inverso del poder de distracción. Entonces, si 2 Elements no comparte un solo atributo, esta sería la atracción máxima.

    
respondido por el user unknown 29.07.2011 - 03:11
3

Use un orden aleatorio, u ordene según un hash de los datos concatenados: un buen hash proporciona salidas altamente disímiles para entradas similares, por lo que las entradas que sean similares en cualquier dimensión deberían estar separadas.

    
respondido por el Jon Purdy 29.07.2011 - 04:09

Lea otras preguntas en las etiquetas