How to resolve the algorithm Permutations by swapping step by step in the jq programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Permutations by swapping step by step in the jq programming language
Table of Contents
Problem Statement
Generate permutations of n items in which successive permutations differ from each other by the swapping of any two items. Also generate the sign of the permutation which is +1 when the permutation is generated from an even number of swaps from the initial state, and -1 for odd. Show the permutations and signs of three items, in order of generation here. Such data are of use in generating the determinant of a square matrix and any functions created should bear this in mind. Note: The Steinhaus–Johnson–Trotter algorithm generates successive permutations where adjacent items are swapped, but from this discussion adjacency is not a requirement.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Permutations by swapping step by step in the jq programming language
Source code in the jq programming language
# The helper function, _recurse, is tail-recursive and therefore in
# versions of jq with TCO (tail call optimization) there is no
# overhead associated with the recursion.
def permutations:
def abs: if . < 0 then -. else . end;
def sign: if . < 0 then -1 elif . == 0 then 0 else 1 end;
def swap(i;j): .[i] as $i | .[i] = .[j] | .[j] = $i;
# input: [ parity, extendedPermutation]
def _recurse:
.[0] as $s | .[1] as $p | (($p | length) -1) as $n
| [ $s, ($p[1:] | map(abs)) ],
(reduce range(2; $n+1) as $i
(0;
if $p[$i] < 0 and -($p[$i]) > ($p[$i-1]|abs) and -($p[$i]) > ($p[.]|abs)
then $i
else .
end)) as $k
| (reduce range(1; $n) as $i
($k;
if $p[$i] > 0 and $p[$i] > ($p[$i+1]|abs) and $p[$i] > ($p[.]|abs)
then $i
else .
end)) as $k
| if $k == 0 then empty
else (reduce range(1; $n) as $i
($p;
if (.[$i]|abs) > (.[$k]|abs) then .[$i] *= -1
else .
end )) as $p
| ($k + ($p[$k]|sign)) as $i
| ($p | swap($i; $k)) as $p
| [ -($s), $p ] | _recurse
end ;
. as $in
| length as $n
| (reduce range(0; $n+1) as $i ([]; . + [ -$i ])) as $p
# recurse state: [$s, $p]
| [ 1, $p] | _recurse
| .[1] as $p
| .[1] = reduce range(0; $n) as $i ([]; . + [$in[$p[$i] - 1]]) ;
def count(stream): reduce stream as $x (0; .+1);
(["a", "b", "c"] | permutations),
"There are \(count( [range(1;6)] | permutations )) permutations of 5 items."
$ jq -c -n -f Permutations_by_swapping.jq
[1,["a","b","c"]]
[-1,["a","c","b"]]
[1,["c","a","b"]]
[-1,["c","b","a"]]
[1,["b","c","a"]]
[-1,["b","a","c"]]
"There are 32 permutations of 5 items."
You may also check:How to resolve the algorithm Arithmetic/Complex step by step in the PostScript programming language
You may also check:How to resolve the algorithm Knight's tour step by step in the Fortran programming language
You may also check:How to resolve the algorithm Magic squares of singly even order step by step in the Perl programming language
You may also check:How to resolve the algorithm Discordian date step by step in the Julia programming language
You may also check:How to resolve the algorithm Copy a string step by step in the Gambas programming language