Calculates a permutation of a size x size binary image.

permutations.js

/**
Generate a grid of all permutations of a binary (black and white) NxN pixel image (where n is between 2 and 5).
Then filter it so it removes:
   all rotationally symmetric patterns ( rotating it 90 is considered the same patterns )
   all non-contiguous patterns ( all the white islands must be connected )
   all translationally the same patterns (dont know the term) ( if you move it some distance to the left, its considered the same pattern ) ( i solved this by cropping the image to best fit and then scaling back up )
   
 The result hopefully should be unique tetris pieces
*/
const canvas = document.querySelector('canvas#shapes');
const canvasWidth = canvas.width;

const size = 2;

function computePermutations(size, filter = true) {
    const s2 = size * size;
    const count = Math.pow(2, s2);
    const hcount = count / 2;

    let unique = 0;
    let permutations = {};
    //https://www.youtube.com/watch?v=fc3nnG2CG8U
    
    for (var i = 0; i < count; i++) {
        //Create the permutation and skip if we have already seen it
        let p = i.toString(2).padStart(s2, '0');

        let data = unflatten(p, size);
        if (filter) {
            data = crop(data);
            p = flatten(data, s2);
            data = unflatten(p, size);
        }

        if (permutations[p] !== undefined) continue;

        if (filter) {

            //Rotate each permutation and add it to our list
            let rotated = data;
            rotated = rotate(rotated);            
            permutations[flatten(rotated)] = false;

            rotated = rotate(rotated);
            permutations[flatten(rotated)] = false;

            rotated = rotate(rotated);
            permutations[flatten(rotated)] = false;

            rotated = rotate(rotated);
            permutations[flatten(rotated)] = false;

            //Get the bits and the map
            const bits = p.split('1').length - 1;
            if (bits > 1) {
                let i = p.indexOf('1');
                let x = i % size;
                let y = Math.floor(i / size);
                let count = countContiguous(data, x, y);
                if (count != bits) {
                    permutations[p] = false;
                    continue;
                }
            }
        }

        //Mark the permutation
        permutations[p] = true;
        unique++;
    }

    function countContiguous(data, x, y, visited = []) {
        let count = 0;
        let hash = `${x},${y}`;
        if (visited.indexOf(hash) != -1) return count;
        visited.push(hash)

        if (x > 0 && data[x-1][y] == '1')           count += countContiguous(data, x-1, y, visited);
        if (x < data.length-1 && data[x+1][y] == '1') count += countContiguous(data, x+1, y, visited);

        if (y > 0 && data[x][y-1] == '1') count += countContiguous(data, x, y-1, visited);
        if (y < data.length-1 && data[x][y+1] == '1') count += countContiguous(data, x, y+1, visited);
        return count + 1;
    }

    function crop(data) {
        let size = data.length;
        let minX = size, minY = size;
        let maxX = 0, maxY = 0;
        for (let x = 0; x < size; x++) {
            for (let y = 0; y < size; y++) {
                if (data[x][y] == '1') {
                    if (x < minX) minX = x;
                    if (y < minY) minY = y;
                    if (x > maxX) maxX = x;
                    if (y > maxY) maxY = y;
                }
            }
        }

        size = Math.max((maxX + 1) - minX, (maxY + 1) - minY);
        if (size < 0) {
            //console.log('skip', minX, maxX, minY, maxY, flatten(data));
            return data;
        }

        //console.log('crop', minX, maxX, minY, maxY, flatten(data));
        //console.log('crop', flatten(data), data, minX, minY);
        let results = [];
        for (let x = 0; x <  data.length; x++) {
            for (let y = 0; y <  data[x].length; y++) {
                if (x < minX || x > maxX || y < minY || y > maxY) continue;
                //console.log(x, y, x-minX, y-minY, data[x][y]);
                if (results[x-minX] == null) results[x-minX] = [];
                results[x-minX][y-minY] = data[x][y];
            }
        }
        //console.log('cropped', flatten(data, data.length * data.length), flatten(results, data.length * data.length), data, results);
        return results;
    }

    function rotate(data) {
        let size = data.length;
        let results = new Array(size);
        for (let i = 0; i < size; i++)
            results[i] = new Array(size);
          
        for (let i = 0; i < size; i++) {
            for (let j = 0; j < size; j++) {
                results[j][(size - 1) - i] = data[i][j];
            }
        }
        return results;
    }

    //Set the length of the actual number of permutations
    permutations.unique = unique;
    permutations.length = count;
    return permutations;
}

function unflatten(permutation, size) {
    const data = [];
    for (let k in permutation) { 
        let row = k % size;
        if (data[row] == null) data[row] = [];
        data[row].push(permutation[k]);
    }
    return data;
}
function flatten(data, size = null) { 
    let b = '';        
    for (let i = 0; i < data.length; i++) {
        for (let j = 0; j < data[i].length; j++) {
            b += data[i][j] == 1 ? '1' : '0';
        }
    }
    if (size) b = b.padStart(size, '0');
    return b;
}

function draw() {
    const ctx = canvas.getContext('2d');
    

    const permutations = computePermutations(size);
    const grid = Math.ceil(Math.sqrt(permutations.unique));
    const width = canvasWidth / grid;

    console.log('Drawing ', permutations.unique, `( ${grid} x ${grid} )`);

    //Set the font initialy
    ctx.font = '10px Monospaced';

    const padding = 0;
    let x = padding, y = padding;
    for(let perm in permutations) {
        if (perm == 'length' || perm == 'unique') continue;

        //Skip invalid permutations
        if (permutations[perm] === false) 
            continue;

        //Draw the permutation
        drawPermutation(ctx, x, y, width, perm, size);

        ctx.fillStyle = 'red';
        ctx.fillText(perm, x + 5, y + 15);
        
        //Increment x, if its greater than the width of the canvas, increment y and reset
        x += width + padding;
        if (x + width + padding > canvasWidth) { 
            y += width + padding;
            x = padding;
        }
    }
}

function drawPermutation(ctx, x, y, width, permutation, columns = null) {
    //console.log('Draw',permutation);
    const lineWidth = 3;

    if (columns == null) 
        columns = Math.sqrt(permutation.length);
    const pixWidth = width / columns;
        
    //Draw the background
    ctx.beginPath();
    ctx.fillStyle = 'black';
    ctx.fillRect(x, y, width, width);
    
    //Draw each perm
    ctx.fillStyle = 'gray';
    ctx.strokeStyle = 'black';
    ctx.lineWidth = 0;
    for(let i in permutation) {
        if (permutation[i] == '1') {

            let px = i % columns;
            let py = Math.floor(i / columns);

            ctx.beginPath();
            ctx.fillRect(x + (px * pixWidth), y + (py * pixWidth), pixWidth, pixWidth);
            ctx.beginPath();
        }
    }

    //Draw the border
    ctx.beginPath();
    ctx.strokeStyle = 'white';
    ctx.lineWidth = lineWidth;
    ctx.rect(x, y, width, width);
    ctx.stroke();
}

setTimeout(draw, 1);