using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;

// 递归与分治算法

namespace AlgorithmCollection.Recursion
{

    public static class RecursionHelper
    {

        #region 全排列，返回数据的所有组合
        public static void Permutations<T>(List<T> data, ref List<List<T>> perms)
        {
            if (perms == null)
                perms = new List<List<T>>();
            foreach(List<T> perm in perms)
            {
                List<T> p = new List<T>(perm);
                perms.Add(p);
            }
        }

        // 生成器形式，每次返回一个组合
        public static IEnumerable Permutations<T>(List<T> data)
        {
            foreach(var perm in _Permutations(data, 0, data.Count - 1))
            {
                yield return perm;
            }
        }

        // 计算start~end范围内的全排列
        private static IEnumerable _Permutations<T>(List<T> data, int start , int end, List<T> perm = null)
        {
            if(perm == null)
                perm = new List<T>(data.Count);
            if(start == end)
            {
                perm.Add(data[start]);
                yield return perm;
                perm.RemoveAt(perm.Count - 1);
            }
            else
            {
                for (int i = start; i <= end; ++i)
                {
                    perm.Add(data[i]);
                    Algorithms.Swap(ref data, start, i);
                    IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator();
                    while(itor.MoveNext())
                        yield return itor.Current;
                    Algorithms.Swap(ref data, start, i);
                    perm.RemoveAt(perm.Count - 1);
                }
            }
        }
        #endregion  

    }
}