@cassidoo's interview question from January 5, 2025, in Bash

permute.sh

#!/usr/bin/env bash
set -eu -o pipefail

# Generate all permutations of a given string
# Usage: permutate "string"
permutate() {
    local string=$1
    local prefix=${2:-}
    local result=()
    local len=${#string}

    # Base case: if string is empty, add the accumulated prefix
    if ((len == 0)); then
        result+=("$prefix")
        echo "${result[@]}"
        return
    fi

    # Recursive case: try each character as the next in sequence
    for ((i = 0; i < len; i++)); do
        # Extract current character
        local curr_char="${string:i:1}"

        # Create new string without current character
        local remaining="${string:0:i}${string:i+1}"

        # Recursive call with updated prefix and remaining string
        # and collect the result
        result+=( $(permutate "$remaining" "$prefix$curr_char") )
    done

    # Output all collected permutations
    echo "${result[@]}"
}

# Print each permutation on a new line
while read -r perm; do
    echo "$perm"
done < <(permutate "${1:-}")

andrewrich@MONTASIO:~/Developer/cassidoo$ ./permute.sh abc
abc acb bac bca cab cba