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


fcn permute(seq)
{
   insertEverywhere := fcn(x,list){ //(x,(a,b))-->((x,a,b),(a,x,b),(a,b,x))
      (0).pump(list.len()+1,List,'wrap(n){list[0,n].extend(x,list[n,*]) })};
   insertEverywhereB := fcn(x,t){ //--> insertEverywhere().reverse()
      [t.len()..-1,-1].pump(t.len()+1,List,'wrap(n){t[0,n].extend(x,t[n,*])})};
 
   seq.reduce('wrap(items,x){
      f := Utils.Helpers.cycle(insertEverywhereB,insertEverywhere);
      items.pump(List,'wrap(item){f.next()(x,item)},
	      T.fp(Void.Write,Void.Write));
   },T(T));
}