|
</pre >
=={{header|m4}}==
<lang m4>divert(-1)
# 1-based indexing of a string's characters.
define(`get',`substr(`$1',decr(`$2'),1)')
define(`set',`substr(`$1',0,decr(`$2'))`'$3`'substr(`$1',`$2')')
define(`swap',
`pushdef(`_u',`get(`$1',`$2')')`'dnl
pushdef(`_v',`get(`$1',`$3')')`'dnl
set(set(`$1',`$2',_v),`$3',_u)`'dnl
popdef(`_u',`_v')')
# $1-fold repetition of $2.
define(`repeat',`ifelse($1,0,`',`$2`'$0(decr($1),`$2')')')
#
# Heap's algorithm. Algorithm 2 in Robert Sedgewick, 1977. Permutation
# generation methods. ACM Comput. Surv. 9, 2 (June 1977), 137-164.
#
# This implementation permutes the characters in a string of length no
# more than 9. On longer strings, it may strain the resources of a
# very old implementation of m4.
#
define(`permutations',
`ifelse($2,`',`$1
$0(`$1',repeat(len(`$1'),1),2)',
`ifelse(eval(($3) <= len(`$1')),1,
`ifelse(eval(get($2,$3) < $3),1,
`pushdef(`_k',eval((($3) % 2) + ((1 - (($3) % 2)) * get($2,$3))))`'dnl
pushdef(`_new_permutation',swap(`$1',_k,$3))`'dnl
_new_permutation
$0(`$1',set($2,$3,incr(get($2,$3))),2)`'dnl
popdef(`_k',`_new_permutation')',
`$0(`$1',set($2,$3,1),incr($3))')')')')
divert`'dnl
permutations(`123')
permutations(`abcd')</lang>
{{out}}
$ m4 permutations.m4
<pre>123
213
321
213
321
213
abcd
bacd
cbad
bacd
cbad
bacd
dbca
bacd
cbad
bacd
cbad
bacd
adcb
bacd
cbad
bacd
cbad
bacd
abdc
bacd
cbad
bacd
cbad
bacd
</pre>
=={{header|Maple}}==
|