algorithm - clustering - Buscando una solución óptima

algoritmos de agrupamiento clustering

Question

Esta fue una de las preguntas de la entrevista en Amazon. Dado un conjunto 2D de 0 y 1, necesitamos encontrar el patrón de tamaño máximo. Patters es el siguiente:

tamaño = 1:

   1
 1 1 1 
   1

tamaño = 2:

   1
   1 
 1 1 1 
   1 
   1

Solución ingenua: recorra todos y cada uno de los elementos de la matriz MxN, y busque el índice con el valor 1 y compruebe si las entradas izquierda y derecha son 1 y anote la longitud máxima de 1 arriba y debajo del índice.

Buscando una mejor solución. Si alguien tiene una pista, por favor haz una publicación.

Answer 1

Lo siguiente utiliza básicamente la misma lógica que la proporcionada por trincot en su respuesta, pero realiza el escaneo inverso cada vez que hay un corte en 1 consecutivos. Esto elimina la necesidad de construir una pila explícita.

El tiempo de ejecución debe ser aproximadamente el mismo. La única ventaja de mi método es que este algoritmo usa O (1) espacio extra, mientras que trincot usa O (rowCount) espacio extra para la pila.

Sin embargo, la pila extra es más corta y más legible.

El código está en C #:

class FindPatternResult
{
    public int Size { get; set; }
    public int Col { get; set; }
    public int Row { get; set; }
}

private FindPatternResult FindPattern(int[,] a)
{
    var numCols = a.GetUpperBound(0)+1;
    var numRows = a.GetUpperBound(1)+1;
    var maxSize = -1;
    var maxCol = -1;
    var maxRow = -1;

    // anonymous function for checking matches when there is
    // a break in consecutive 1''s.
    var checkForMatch = new Action<int, int, int>((height, bottomRow, col) =>
    {
        var topRow = bottomRow - height + 1;
        for (int row = bottomRow-1; row > topRow; --row)
        {
            // There''s a potential optimization opportunity here.
            // If we get beyond the midpoint and size is decreasing,
            // then if size < maxSize, we can early-out.
            // For example, if maxSize is 3 and tow-topRow < 3,
            // then there can''t possibly be a longer match in this column.
            // I didn''t add that optimization because it doesn''t
            // really change the algorithm. But if the number of rows
            // is very large, it could be meaningful.
            if (a[row, col - 1] == 1 && a[row, col + 1] == 1)
            {
                var size = Math.Min(bottomRow-row, row-topRow);
                if (size > maxSize)
                {
                    maxSize = size;
                    maxCol = col;
                    maxRow = row;
                }
            }
        }
    });
    for (int col = 1; col < numCols - 1; ++col)
    {
        var size = 0;
        for (int row = 0; row < numRows; ++row)
        {
            if (a[row,col] == 1)
            {
                ++size;
            }
            else
            {
                // If size >= 3, then go back and check for a match
                if (size >= 3)
                {
                    checkForMatch(size, row, col);
                }
                size = 0;
            }
        }
        // If we end the loop with size >= 3, then check from the bottom row.
        if (size >= 3)
        {
            checkForMatch(size, numRows - 1, col);
        }
    }

Prueba con:

private void DoIt()
{
    var rslt = FindPattern(_sampleData);
    Console.WriteLine($"Result: {rslt.Size}, [{rslt.Row}, {rslt.Col}]");
}

private readonly int[,] _sampleData =
{
    {0, 0, 1, 0, 0, 1, 0},
    {0, 0, 1, 1, 0, 1, 0},
    {1, 1, 1, 0, 0, 1, 1},
    {1, 0, 1, 0, 1, 1, 0},
    {1, 1, 1, 1, 0, 1, 0},
    {0, 1, 1, 1, 1, 1, 1},
    {0, 0, 1, 0, 0, 1, 0}
};

Answer 2

Supongo que los valores 1 que rodean dicho patrón no lo destruyen, por lo que también este tendría el tamaño 1:

1 1 1 1
1 1 1 1
1 1 0 1
1 1 1 1

En ese caso, sugeriría un algoritmo en el que para cada columna haga lo siguiente:

1. Inicializar el tamaño como 0
2. Para cada celda en esta columna:
   • Empuje el tamaño actual en una pila; representa el número de 1 valores en dirección ascendente comenzando desde esta celda.
   • Si el valor en esta celda es un 1, entonces aumenta el tamaño ; de lo contrario, configúralo en 0
3. Inicializar el tamaño como 0
4. Para cada celda en esta columna, pero en orden inverso:
   • Pop el último valor de la pila
   • Llame a thisSize el menor del valor reventado y el valor de tamaño .
   • Si thisSize es mayor que el mejor patrón encontrado hasta el momento y los valores en ambos lados de la celda actual son 1, entonces considere este el mejor patrón.
   • Si el valor en esta celda es un 1, entonces aumenta el tamaño ; de lo contrario, configúralo en 0

Como una optimización adicional, podría salir del segundo bucle tan pronto como la distancia entre la celda actual y la parte superior de la parrilla se vuelva más pequeña que el tamaño del patrón más grande que ya encontramos anteriormente.

Aquí hay una implementación en JavaScript:

function findPattern(a) {
    var rows = a.length,
        cols = a[0].length,
        maxSize = -1,
        stack = [],
        row, col, pos, thisSize;
        
    for (col = 1; col < cols-1; col++) {
        stack = [];
        // Downward counting to store the number of 1s in upward direction
        size = 0;
        for (row = 0; row < rows; row++) {
            stack.push(size);
            size = a[row][col] == 1 ? size + 1 : 0;
        }
        // Reverse, but only as far as still useful given the size we already found
        size = 0;
        for (row = rows - 1; row > maxSize; row--) {
            thisSize = Math.min(size, stack.pop());
            if (thisSize >= maxSize && a[row][col-1] == 1 && a[row][col+1] == 1) {
                maxSize = thisSize;
                pos = [row, col];
            }
            size = a[row][col] == 1 ? size + 1 : 0;
        }
    }
    return [maxSize, pos];
}

// Sample data:
var a = [
    [0, 0, 1, 0, 0, 1, 0],
    [0, 0, 1, 1, 0, 1, 0],
    [1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 0],
    [1, 1, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 1],
    [0, 0, 1, 0, 0, 1, 0]];

var [size, pos] = findPattern(a);

console.log(''Size '' + size + '' with center at row '' + (pos[0]+1) 
            + '' and column '' + (pos[1]+1) + '' (first row/col is numbered 1)'');

Answer 3

Aquí: gist.github.com / ... es una implementación Java genérica que encuentra el patrón más grande (+) en una matriz 2D de cualquier tamaño.

1. La idea es buscar primero el patrón más grande (+) posible alrededor de los elementos centrales (ventana inicial) de la matriz. Para cada elemento en la ventana, encuentre el tamaño máximo más centrado en ese elemento.

2. Si se encuentra el más grande, devuelva el tamaño más grande.

3. Si no se encuentra el ''+'' más grande posible, almacene el tamaño de lo que sea más pequeño que el encontrado y repita la búsqueda desde el paso n. ° 1 en la siguiente ventana externa alrededor de la ventana anterior para un patrón ''+'' más pequeño; búsqueda iterativa de ''+'' en un ''patrón de capa de cebolla'' desde adentro hacia afuera.

La ventana central inicial se elige de modo que los bordes de la matriz estén igualmente lejos en todos los lados desde esta ventana.

• Ejemplo 1: para una matriz de tamaño {4x3}, la ventana central más pequeña se encuentra entre (1,1) y (2,1)

• Ejemplo 2: para una matriz de tamaño {3x9}, la ventana central más pequeña se encuentra entre (1,1) y (1,7)

  int rows = arr.length;
  int cols = arr[0].length;
  int min = rows < cols ? rows : cols;
  int diff = rows > cols ? rows - cols : cols - rows;
  
  // Initializing initial window params. The center most smallest window possible
  int first_r, first_c, last_r, last_c;
  first_r = (min - 1) / 2;
  first_c = (min - 1) / 2;
  last_r = rows < cols ? (rows / 2) : (cols / 2) + diff;
  last_c = rows > cols ? (cols / 2) : (rows / 2) + diff;

Código completo de Java:

public class PlusPattern {

    /**
     * Utility method to verify matrix dimensions
     *
     * @param a matrix to be verified
     * @return true if matrix size is greater than 0;
     */
    private static boolean isValid(int[][] a) {
        return a.length > 0 && a[0].length > 0;
    }

    /**
     * Finds the size of largest plus(+) pattern of given ''symbol'' integer in an integer 2D matrix .
     *
     * The idea is to find for the biggest possible plus(+) pattern first around the central elements
     * of the matrix. If largest is found return the largest size. If largest possible + is not
     * found, store the size of whatever smaller than that was found and repeat search for 1 size
     * smaller + in the next outer window around the previous window.
     *
     * @param arr    matrix to be searched
     * @param symbol whose + patter is sought
     * @return the radius of largest + found in the matrix.
     */
    static int findLargestPlusPattern(int[][] arr, int symbol) {
        if (!isValid(arr)) {
            throw new IllegalArgumentException("Cannot perform search on empty array");
        }
        int maxPlusRadius = 0;

        int rows = arr.length;
        int cols = arr[0].length;
        int min = rows < cols ? rows : cols;
        int diff = rows > cols ? rows - cols : cols - rows;

        // Initializing initial window params. The center most smallest window possible
        // Example - For matrix of size {4x3}, smallest central window lies from [1][1] to [2][1]
        // Example - For matrix of size {3x9}, smallest central window lies from [1][1] to [1][7]
        int first_r, first_c, last_r, last_c;
        first_r = (min - 1) / 2;
        first_c = (min - 1) / 2;
        last_r = rows < cols ? (rows / 2) : (cols / 2) + diff;
        last_c = rows > cols ? (cols / 2) : (rows / 2) + diff;

        // Initializing with biggest possible search radius in the matrix
        int searchRadius = (min - 1) / 2;

        int r, c;
        int found;

        // Iteratively searching for + in an ''onion layer pattern'' from inside to outside
        while (searchRadius > maxPlusRadius) {     // no need to find smaller + patterns than the one already found
            // initializing r and c cursor for this window iterations.
            r = first_r;
            c = first_c;

            // Search each of the 4 sides of the current window in a clockwise manner
            // 1# Scan the top line of window
            do { // do-while used to search inside initial window with width==1
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;      // cannot find a bigger plus(+) than this in remaining matrix
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                c++;
            } while (c < last_c);
            if (c > last_c)
                c--; // for initial window with width==1. Otherwise #3 condition will be true for invalid c-index

            // 2# Scan the right line of window
            do {  // do-while used to search inside initial window with height==1
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                r++;
            } while (r < last_r);
            if (r > last_r)
                r--; // for initial window with height==1. Otherwise #4 condition will be true for invalid r-index

            // 3# Scan the bottom line of window
            while (c > first_c) {
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                c--;
            }

            // 4# Scan the left line of window
            while (r > first_r) {
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                r--;
            }
            // r and c comes back at first_r and first_c.

            // increasing window on all sides by 1.
            first_r--;
            first_c--;
            last_r++;
            last_c++;

            // reducing search radius to avoid out of bounds error on next window.
            searchRadius--;
        }
        return maxPlusRadius;
    }

    /**
     * Finds, if exist, the size of largest plus around a given point a[r][c]. It grows radius
     * greedily to maximise the search for + pattern returns 0 if is the point is the only symbol.
     *
     * @param r          row coordinate of search center
     * @param c          column coordinate of search center
     * @param a          matrix
     * @param symbol     search symbol
     * @param max_radius around the center to be searched for + pattern
     * @return returns -1 if the point itself is not the symbol.
     * returns n if all the next elements in E W N S directions within radius n are the symbol elements.
     */
    static int findLargestPlusAt(int r, int c, int[][] a, int symbol, int max_radius) {
        int largest = -1;

        if (a[r][c] != symbol) {   // If center coordinate itself is not the symbol
            return largest;
        } else {
            largest = 0;
        }
        for (int rad = 1; rad <= max_radius; rad++) {
            if (a[r + rad][c] == symbol && a[r][c + rad] == symbol && a[r - rad][c] == symbol && a[r][c - rad] == symbol) {
                largest = rad;   // At least a ''+'' of radius ''rad'' is present.
            } else {
                break;
            }
        }
        return largest;
    }

    public static void main(String[] args) {
        int mat[][];
        mat = new int[][]{      // max + = 3
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 1, 1, 1, 1, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
        };
        int find = findLargestPlusPattern(mat, 1);
        System.out.println("# Max + size radius is : " + find);
        mat = new int[][]{  // max + = 2
                {1, 1, 9, 1, 1, 9, 1,},
                {1, 1, 9, 1, 1, 9, 1,},
                {7, 1, 1, 1, 1, 1, 1,},
                {1, 1, 9, 1, 1, 9, 1,},
                {1, 1, 9, 1, 1, 9, 1,},
        };
        find = findLargestPlusPattern(mat, 1);
        System.out.println("# Max + size radius is : " + find);

        mat = new int[][]{      // max + = 1
                {1, 1, 0, 1, 1},
                {1, 1, 0, 1, 1},
                {1, 1, 0, 1, 1},
                {1, 1, 1, 6, 1},
                {1, 1, 0, 1, 1},
                {1, 1, 0, 1, 1},
        };
        find = findLargestPlusPattern(mat, 1);
        System.out.println("# Max + size radius is : " + find);
    }
}