Sunday, October 24, 2021

[SOLVED] Bash for variable exceeds conidtion

Issue

I need to write a script that does all permutation from 1 to n, where n is my script argument. For some reason I can't get it working in bash, the program logic should be good, since it works fine in C. So I'm assuming I'm making some kind of mistake bash related. If I echo the i it seems to exceed the condition in the for body, which I'm guessing is the issue, but I don't know why.

Ex:n = 3

123
132
213
231
312
321

This is my code

#! /bin/bash

n=$1
a=()
used=( $(for i in $(seq $n);do echo 0;done) )
function show
{
    v=("$@")
    for i in ${v[@]}; do
        printf "%d " $i
    done
    printf "\n"
}

function backtracking
{
    if [ $1 -eq $((n+1)) ]
    then
        show ${a[@]}
    else
        for ((i=0;i<$n;i++));do
            if [ "${used[$i]}" -eq 0 ]
            then
                a[$(($1-1))]=$(($i+1))
                used[$i]=1
                backtracking $(($1+1))
                used[$((i))]=0
            fi
            done
    fi
}


backtracking 1

exit 0

Solution

Please read about local variables in Bash: https://tldp.org/LDP/abs/html/localvar.html

#!/usr/bin/env bash

n=$1
a=()
used=( $(for _ in $(seq $n);do echo 0;done) )
function show
{
    v=("$@")
    local i
    for i in ${v[@]}; do
        printf "%d " $i
    done
    printf "\n"
}

function backtracking
{
    local index="$1"

    if [ "$index" -eq $((n+1)) ]
    then
        show ${a[@]}
    else
        local i
        for ((i=0;i<$n;i++));do
            if [ "${used[$i]}" -eq 0 ]
            then
                a[$((index-1))]=$((i+1))
                used[$i]=1
                backtracking $((index+1))
                used[$i]=0
            fi
            done
    fi
}


backtracking 1

And tbh there are a lot of bad practices in your script. Go check out https://www.shellcheck.net and https://github.com/bash-lsp/bash-language-server, they are awesome.

Here's a cleaner version:

#!/usr/bin/env bash

width="$1"
mapfile current < <( for _ in $( seq 0 $(( width - 1 )) ); do printf '0\n'; done )

function backtracking {
    local index="$1"

    if [[ "$index" -eq "$width" ]]; then
        for bit in "${current[@]}"; do
            printf '%d ' "$bit"
        done
        printf '\n'
    else
        local i
        for (( i = 1; i <= "$width"; i++ )); do
            local used=0
            local j
            for (( j = 0; j < "$1"; j++ )); do
                if [[ "${current[$j]}" -eq "$i" ]]; then
                    used=1
                    break
                fi
            done
            if [[ "$used" -eq 1 ]]; then
                continue
            fi
            current[$index]="$i"
            backtracking $(( index + 1 ))
        done
    fi
}

backtracking 0


Answered By - Frederick Zhang
at