Full Permutation Algorithm in BASH

justyy (84)in #programming • 5 years ago

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