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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#!/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
#!/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
1
2
3
4
5
6
7
# ./perm.sh 123
123
132
213
231
321
312
# ./perm.sh 123
123
132
213
231
321
312

Permutations and Combinations

BASH Programming/Shell

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
288 words
Last Post: Teaching Kids Programming - Count Odd Numbers in an Interval Range
Next Post: Teaching Kids Programming - Recursive Depth First Search Algorithm to Check If Two Binary Trees are Same

The Permanent URL is: Full Permutation Algorithm Implementation in BASH

Leave a Reply