using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LibNumThryCombinatorics
{
    public class clsPermutations
    {
        

        public IEnumerable<int[]> exchangePermutation(int size)
        {
            int[] perm = new int[size + 4]; // permutation
            int[] pos= new int[size+1]; // Inverse permutation for locating position for each value
            int[] dir = new int[size+1]; //direction of movement of each value


            //  Initialize
            for (int idx = 1; idx <= size; idx++)
            {
                perm[idx] = idx;
                pos[idx] = idx;
                dir[idx] = -1;
            }

            // Create barriers at ends of perm array
            perm[0] = size + 1;  
            perm[size+1]=size+1;

            // No exchange first time
            perm[size + 2] = 1;
            perm[size + 3] = 1;

            yield return perm;  // return initial permutation\

            for(int value=size;value >1;)
            {

                // Interchange two adjacent positions in perm.
                // Values in positions size + 2 and size + 3
                //    tell which positions were exchanged.

                int valuelPos = pos[value];
                int nextPos = valuePos + dir[value];

                perm[size + 2] = valuePos;
                perm[size + 3] = nextPos;

                int exchangeValue = perm[nextPos];

                perm[valuePos] = exchangeValue;
                pos[exchangeValue] = valuePos;

                perm[nextPos] = value;
                pos[value] = nextPos;

                yield return perm;

                // Find greatest value that is not at end
               value = size;
                while value > 1 && perm[pos[value] + dir[value]] > value)
                {
                    dir[value] = -dir[value]; // Reverse directions of current value
                   value--;
                }

            } // for
        }//exchangePermutation


    }
}