Full Permutation Algorithm Implementation in BASH

Swap Two Characters in BASH

In BASH, we can use “${#string}” to get the length of a string. And in a function, we use “local” keyword to declare local variables. And strings are immuntable in BASH, and thus we can use the following function to swap two characters in a string:

function swap() {
    local string=$1
    local len=${#string}
    local from=$2
    local to=$3
    local i=0
    local s=""
    while [[ $i -lt $len ]]; do
        if [[ $i -eq $from ]]; then
            s=$s${string:$to:1}
        elif [[ $i -eq $to ]]; then
            s=$s${string:$from:1}
        else
            s=$s${string:$i:1}
        fi
        i=$(($i+1))
    done
    echo $s
}

Full Permutation Algorithm in BASH

And then, with the perm function, we can recursively “swap” two letters and get the full permutation:

#!/bin/bash

function swap() {
    local string=$1
    local len=${#string}
    local from=$2
    local to=$3
    local i=0
    local s=""
    while [[ $i -lt $len ]]; do
        if [[ $i -eq $from ]]; then
            s=$s${string:$to:1}
        elif [[ $i -eq $to ]]; then
            s=$s${string:$from:1}
        else
            s=$s${string:$i:1}
        fi
        i=$(($i+1))
    done
    echo $s
}

function perm() {
    local string=$1
    local len=${#string}
    local idx=$2
    if [[ $idx -ge $len ]]; then
        echo $string
    else
        local i=$idx
        while [[ $i -lt $len ]]; do
            perm $(swap $string $i $idx) $((idx+1))
            i=$((i+1))
        done
    fi
}

perm $1

# ./perm.sh 123
123
132
213
231
321
312

Permutations and Combinations

• Using Bitmasking Algorithm to Compute the Combinations of an Array
• Teaching Kids Programming – Recursive Backtracking Algorithm to Compute the Combinations
• Teaching Kids Programming – Recursive Permutation Algorithm
• Teaching Kids Programming – Introduction to Permutation and Combination
• Teaching Kids Programming – Three Algorithms to Compute the Combination Number
• A Recursive Full Permutation Algorithm in Python
• The Permutation Iterator in Python
• GoLang: Full Permutation Command Line Tool
• The Permutation Algorithm for Arrays using Recursion
• Full Permutation Algorithm Implementation in BASH

BASH Programming/Shell

• Alarming on High Disk Usage using BASH, AWK, Crontab Job
• Compute GCD in Bash with Input Validation
• Why a Leading Space in Linux Shell Commands Can Matter?
• How to Get HTTP Response Code using cURL Command?
• Three Interesting/Fun BASH Commands
• One Interesting Linux Command (Steam Locomotive in BASH)
• Simple Bash Function to Repeat a Command N times with Retries
• How to Extract a Domain Name from a Full URL in BASH?
• BASH Function to Compute the Greatest Common Divisor and Least Common Multiples
• BASH Function to Get Memory Information via AWK
• BASH Function to Escape Parameters Argument
• BASH Function to Check if sudo Available
• Full Permutation Algorithm Implementation in BASH
• BASH Function to Install Docker
• A Simple BASH Function/Script to Run a Command in Background
• BASH Script to Compute the Average Ping to a Domain
• A Bash Process Controller to Start, Stop and Restart an Daemon Program
• Linux BASH shell - Echo This if you get angry
• Bash SHELL, Chess Board Printing

–EOF (The Ultimate Computing & Technology Blog) —