using System;

using System.Linq;

using System.Collections.Generic;

using System.Globalization;

​

public class Program

{

    public static void Main()

    {

        int total =0;

      foreach(var permutation in GetPermutations(new[]{"imagine", "how","is","touch","the","sky"}))

      {

          Console.WriteLine(string.Join(" ", permutation));

          total++;

      }

        Console.WriteLine(total);

    }

    public static void Dump<T>(IEnumerable<T> items)

    {

        Console.WriteLine(string.Join(", ",items));

    }

​

    public static IEnumerable<IReadOnlyList<T>> GetPermutations<T>(IReadOnlyList<T> input)

    {

        long subSwaps = (input.Count - 2) * (input.Count - 1) - 1;

        int subSwapIndexMax = input.Count - 2;

        T[] permutation = input.ToArray();

        for (long index = 0; index < input.Count; index++)

        {

            if (index > 0)

                MoveToFront(index, permutation);

            yield return permutation;

            int direction = 1;

            int pos = subSwapIndexMax;

            for (int s = 0; s < subSwaps; s++)

            {

                Swap(ref permutation[pos], ref permutation[pos + 1]);

                if (pos == subSwapIndexMax)

                    direction = -1;

                else if (pos == 1)

                    direction = 1;

                pos += direction;

                yield return permutation;

            }

​

            Swap(ref permutation[pos], ref permutation[pos + 1]);

        }

    }

​

    public static void Swap<T>(ref T a, ref T b)

    {

        T temp = a;

        a = b;

        b = temp;

    }

​

    public static void MoveToFront<T>(long index, T[] array)

    {

        T ele = array[index];

        for (long k = index; k > 0; k--)

            array[k] = array[k - 1];

        array[0] = ele;

    }

}