Task

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.



References

 Steinhaus–Johnson–Trotter algorithm
 Johnson-Trotter Algorithm Listing All Permutations
 Heap's algorithm
 [1] Tintinnalogia


Related tasks

   Matrix arithmetic
   Gray code


# 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);