Permutations: Difference between revisions

=={{header|UNIX Shell}}==

{{works with|Bourne Again SHell}}

{{works with|Korn Shell}}

Straightforward implementation of Heap's algorithm operating in-place on an array local to the <tt>permute</tt> function.

<syntaxhighlight lang="bash">function permute {

if (( $# == 1 )); then

set -- $(seq $1)

fi

local A=("$@")

permuteAn "$#"

}

function permuteAn {

# return all permutations of first n elements of the array A, with remaining

# elements unchanged.

local -i n=$1 i

shift

if (( n == 1 )); then

printf '%s\n' "${A[*]}"

else

permuteAn $(( n-1 ))

for (( i=0; i<n-1; ++i )); do

local -i k

(( k=n%2 ? 0: i ))

local t=${A[k]}

A[k]=${A[n-1]}

A[n-1]=$t

permuteAn $(( n-1 ))

done

fi

}</syntaxhighlight>

For Zsh the array indices need to be bumped by 1 inside the <tt>permuteAn</tt> function:

{{works with|Z Shell}}

<syntaxhighlight lang="zsh">function permuteAn {

# return all permutations of first n elements of the array A, with remaining

# elements unchanged.

local -i n=$1 i

shift

if (( n == 1 )); then

printf '%s\n' "${A[*]}"

else

permuteAn $(( n-1 ))

for (( i=1; i<n; ++i )); do

local -i k

(( k=n%2 ? 1 : i ))

local t=$A[k]

A[k]=$A[n]

A[n]=$t

permuteAn $(( n-1 ))

done

fi

}</syntaxhighlight>

{{Out}}

Sample run:

<pre>$ permute 4

permute 4

1 2 3 4

2 1 3 4

3 1 2 4

1 3 2 4

2 3 1 4

3 2 1 4

4 2 1 3

2 4 1 3

1 4 2 3

4 1 2 3

2 1 4 3

1 2 4 3

1 3 4 2

3 1 4 2

4 1 3 2

1 4 3 2

3 4 1 2

4 3 1 2

4 3 2 1

3 4 2 1

2 4 3 1

4 2 3 1

3 2 4 1

2 3 4 1</pre>