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


F s_permutations(seq)
   V items = [[Int]()]
   L(j) seq
      [[Int]] new_items
      L(item) items
         I L.index % 2
            new_items [+]= (0..item.len).map(i -> @item[0 .< i] [+] [@j] [+] @item[i..])
         E
            new_items [+]= (item.len..0).step(-1).map(i -> @item[0 .< i] [+] [@j] [+] @item[i..])
      items = new_items
 
   R enumerate(items).map((i, item) -> (item, I i % 2 {-1} E 1))
 
L(n) (3, 4)
   print(‘Permutations and sign of #. items’.format(n))
   L(perm, sgn) s_permutations(Array(0 .< n))
      print(‘Perm: #. Sign: #2’.format(perm, sgn))
   print()