Functional recursive matrix permutation: JS PoC

bubbleSort.js

/**
 * This module provides bubble sort functionality that is used to determine
 * the sequence of swaps needed to sort an array. The swap positions are
 * used by the permutation module to reorder matrix axes.
 */

/**
 * Determines the sequence of swap positions needed to sort an array using bubble sort.
 * This is particularly useful for matrix axis permutation, where we need to know
 * the exact sequence of swaps to achieve a desired axis order.
 * 
 * @param {Array} arr - The array to analyze for sorting operations
 * @returns {Array} An array of positions where swaps should occur
 */
function getBubbleSortOperations(arr) {
    const n = arr.length;
    const swapPositions = [];
    
    // Outer loop for each pass through the array
    for (let i = 0; i < n - 1; i++) {
        // Inner loop for comparing adjacent elements
        for (let j = 0; j < n - i - 1; j++) {
            // Swap if the current element is greater than the next
            if (arr[j] > arr[j + 1]) {
                // Record the swap position
                swapPositions.push(j);
                
                // Swap elements
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    
    return swapPositions;
}

/**
 * Applies bubble sort to an array using the swap positions determined by getBubbleSortOperations.
 * This function is useful for verifying the correctness of the swap positions.
 * 
 * @param {Array} arr - The array to sort
 * @returns {Array} The sorted array
 */
function applyBubbleSort(arr) {
    // Get the swap positions
    const swapPositions = getBubbleSortOperations([...arr]);
    
    // Create a copy of the array to sort
    const sortedArray = [...arr];
    
    // Apply each swap
    for (const pos of swapPositions) {
        // Swap elements at pos and pos+1
        const temp = sortedArray[pos];
        sortedArray[pos] = sortedArray[pos + 1];
        sortedArray[pos + 1] = temp;
    }
    
    return sortedArray;
}

/**
 * Example usage demonstrating the bubble sort operations and their application.
 * Shows how the swap positions can be used to sort an array.
 */
function main() {
    const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
    console.log("Unsorted array:", unsortedArray);
    console.log("Swap positions:", getBubbleSortOperations([...unsortedArray]));
    console.log("Sorted array:", applyBubbleSort(unsortedArray));
}

// Export the functions
module.exports = {
    getBubbleSortOperations,
    applyBubbleSort
};

// Only run main if this file is being run directly
if (require.main === module) {
    main();
} 

permute.js

/**
 * This module provides functionality for permuting the axes of multi-dimensional matrices.
 * It uses bubble sort operations to determine the sequence of axis swaps needed to achieve
 * the desired permutation order.
 */

const { getBubbleSortOperations } = require('./bubbleSort');

/**
 * Permutes the axes of a multi-dimensional matrix according to a specified order.
 * @param {Array} matrix - The input multi-dimensional matrix to permute
 * @param {Array} order - The desired order of axes (e.g., [2,1,0] to reverse axes)
 * @returns {Array} The permuted matrix with axes reordered according to the specified order
 */
function permuteAxes(matrix, order) {
    // Get the swap operations needed to sort the order array
    const swapOperations = getBubbleSortOperations([...order]);
    
    // Create a copy of the matrix to avoid modifying the original
    let permutedMatrix = JSON.parse(JSON.stringify(matrix));
    
    // Apply each swap operation
    for (const pos of swapOperations) {
        // Get the current and next axis indices
        const currentAxis = pos;
        const nextAxis = pos + 1;
        
        // Perform the axis swap using zip
        permutedMatrix = swapAxes(permutedMatrix, currentAxis, nextAxis);
    }
    
    return permutedMatrix;
}

/**
 * Transposes a 2D matrix by swapping rows and columns.
 * @param {Array} matrix - A 2D matrix to transpose
 * @returns {Array} The transposed matrix where rows become columns and vice versa
 */
function transpose(matrix) {
    return matrix[0].map((_, i) => matrix.map(row => row[i]));
}

/**
 * Recursively swaps two axes in a multi-dimensional matrix.
 * @param {Array} matrix - The input multi-dimensional matrix
 * @param {number} axis1 - The first axis to swap
 * @param {number} axis2 - The second axis to swap
 * @returns {Array} The matrix with the specified axes swapped
 */
function swapAxes(matrix, axis1, axis2) {
    // Base case: if we're at the deepest level (no more nested arrays), just return the matrix
    if (!Array.isArray(matrix[0])) {
        return matrix;
    }
    
    // If we're at the level where we need to swap (top level)
    if (axis1 === 0 && axis2 === 1) {
        // Transpose the matrix using the transpose function
        return transpose(matrix);
    }
    
    // Otherwise, recursively process each element at the current level
    return matrix.map(subMatrix => swapAxes(subMatrix, axis1 - 1, axis2 - 1));
}

/**
 * Example usage demonstrating the permutation of a 3D matrix.
 * Creates a 2x3x2 matrix and permutes its axes in reverse order.
 */
function main() {
    // A 3D matrix with dimensions 2x3x2
    const matrix = [
        [
            [1, 2],
            [3, 4],
            [5, 6]
        ],
        [
            [7, 8],
            [9, 10],
            [11, 12]
        ]
    ];
    
    const order = [2, 1, 0]; // Reverse order
    
    console.log("Original matrix:");
    console.log(matrix);
    
    const permuted = permuteAxes(matrix, order);
    console.log("\nPermuted matrix (order [2,1,0]):");
    console.log(permuted);

    // Expected result for order [2,1,0]
    const expected = [
        [
            [1, 7],
            [3, 9],
            [5, 11]
        ],
        [
            [2, 8],
            [4, 10],
            [6, 12]
        ]
    ];

    // Assert that the permutation is correct
    const isCorrect = JSON.stringify(permuted) === JSON.stringify(expected);
    console.log("\nPermutation is correct:", isCorrect);
    
    if (!isCorrect) {
        console.log("Expected:");
        console.log(expected);
        throw new Error("Permutation result is incorrect");
    }
}

// Only run main if this file is being run directly
if (require.main === module) {
    main();
}

module.exports = permuteAxes;