Regular Solution 
   class Program
    {
        static void Main(string[] args)
        {
            string[] stringInput = { "Hello", "World", "Foo", "SDy" };
            ArrayList al = new ArrayList();
            al.Add("Hello");
            al.Add("World");
            al.Add("Foo");
            al.Add("SDy");
            ArrayList sss = Permute( al);
            foreach (ArrayList item in sss)
            {
                foreach (string i in item)
                {
                    Console.Write(" " + i);
                }
                Console.WriteLine();
            }
        }
        public static ArrayList Concat(string a, ArrayList b)
        {
            ArrayList result = new ArrayList();
            
             result.Add(a);
           
            foreach (string item in b)
            {
                result.Add(item);
            }
           
            return result;
        }
        public static ArrayList Permute(ArrayList list)
        {
            ArrayList result = new ArrayList();
            
            if (list.Count==0)
            {
                
                result.Add(new ArrayList());
                return  result;
            }
            
            else
            {
                int startindex = 0;
              //  ArrayList result = new ArrayList();
                foreach (string item2 in list)
                {
                    ArrayList sublist = RemainArray(startindex, list);                   
                   
                   foreach(ArrayList i in Permute(sublist))
                   {
                       result.Add(Concat(list[startindex].ToString(),i));
                   }
                    
                    
                    startindex++;
                }
               
            }
            return result;
         }
        public static ArrayList RemainArray(int indextoskip,ArrayList  originallist)
        {
            ArrayList result = new ArrayList();
            int index = 0;
            foreach (string item in originallist)
            {
                if (index != indextoskip)
                {
                    result.Add(item);
                }
                index += 1;
            }
            return result;
        }
    }
IEnumerable Solution (using yield return) 
class Program
    {
        public static string GetItemFromListByIndex(IEnumerable
 list, int index)
        {
            string result = null;
            int count = 0;
            foreach (string sdy in list)
            {
               
                if (count == index)
                {
                    result=sdy;
                    break;
                    
                }
                count++;
            }
            return result;
        }
        public static int Size(IEnumerable list)
        {
            int count=0;  
            foreach (string sdy in list)
            {
                count++;
            }
            return count;
        }
      
        public static IEnumerable> Permute(string item, IEnumerable list)
        {
            if (Size(list) == 0)
            {
                yield return new string[]{};
            }
            else
            {
                // get remain array
                 int startindex = 0;
                 foreach (string item2 in list)
                 {
                     string itemvalue=GetItemFromListByIndex(list,startindex);
                     IEnumerable sublist = RemainArray(startindex, list);
                     foreach (IEnumerable permutationOfRemainder in Permute(itemvalue, sublist))
                     {
                         yield return Concat( new string[]{itemvalue},permutationOfRemainder);
                     }
                     startindex++;
                 }
                
            }   
        }
        public static IEnumerable Concat(IEnumerable a, IEnumerable b)
        {
            foreach (string item in a)
            {
                yield return item;
            }
            foreach (string item in b)
            {
                yield return item;
            }
        }
        public static IEnumerable RemainArray(int indextoskip, IEnumerable originallist)
        {
            int index = 0;
            foreach (string item in originallist)
            {
                if (index != indextoskip)
                {
                    yield return item;
                }
                index += 1;
            }
        }
        static void Main(string[] args)
        {
            string[] stringInput = { "Hello", "World", "Foo", "SDy" };
       
            var sdy = Permute(null, stringInput);
            foreach (IEnumerable permutation in sdy)
            {
                foreach (string i in permutation)
                {
                    Console.Write(" " + i);
                }
                Console.WriteLine();
            }
         
        }
    }