using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using UnityEngine;

namespace XGame
{
    /// <summary>
    /// ALgorithm相关的实用函数。
    /// </summary>
    public static partial class Utility
    {
        public static void Swap<T>(ref T x, ref T y)
        {
            T t = x;
            x = y;
            y = t;
        }

        /// <summary>
        /// 递归求组合（从n个不同元素中取出m个元素组合）
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">结果列表</param>
        /// <param name="arr">所求数组</param>
        /// <param name="n">辅助变量</param>
        /// <param name="m">辅助变量</param>
        /// <param name="pos">辅助下标存储数组</param>
        /// <param name="M">辅助变量</param>
        public static void GetCombination<T>(ref List<T[]> list, T[] arr, int n, int m, int[] pos, int M)
        {
            for (int i = n; i >= m; i--)
            {
                pos[m - 1] = i - 1;
                if (m > 1)
                {
                    GetCombination(ref list, arr, i - 1, m - 1, pos, M);
                }
                else
                {
                    T[] temp = new T[M];
                    for (int j = 0; j < M; j++)
                    {
                        temp[j] = arr[pos[j]];
                    }

                    if (list == null)
                    {
                        list = new List<T[]>();
                    }

                    list.Add(temp);
                }
            }
        }

        /// <summary>
        /// 数组中n个元素的组合
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr">所求数组</param>
        /// <param name="n">元素个数</param>
        /// <returns>组合结果列表</returns>
        public static List<T[]> GetCombination<T>(T[] arr, int n)
        {
            if (arr.Length < n)
            {
                return null;
            }

            List<T[]> list = new List<T[]>();
            GetCombination(ref list, arr, arr.Length, n, new int[n], n);
            return list;
        }

        /// <summary>
        /// 递归求排列（从n个不同元素中取出m个元素排列）
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="result">结果列表</param>
        /// <param name="list">所求数组</param>
        /// <param name="start">起始标号</param>
        /// <param name="end">结束标号</param>
        public static void GetPermutation<T>(ref List<T[]> list, T[] arr, int start, int end)
        {
            if (start == end)
            {
                T[] temp = new T[arr.Length];
                arr.CopyTo(temp, 0);

                if (list == null)
                {
                    list = new List<T[]>();
                }
                list.Add(temp);
            }

            for (int i = start; i <= end; i++)
            {
                Swap(ref arr[i], ref arr[start]);
                GetPermutation(ref list, arr, start + 1, end);
                Swap(ref arr[i], ref arr[start]);
            }
        }

        /// <summary>
        /// 数组n个元素的排列
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr">所求数组</param>
        /// <param name="n">元素个数</param>
        /// <returns>排列结果列表</returns>
        public static List<T[]> GetPermutation<T>(T[] arr, int n)
        {
            if (arr.Length < n)
            {
                return null;
            }

            List<T[]> list = new List<T[]>();
            List<T[]> comList = GetCombination(arr, n);
            foreach (var com in comList)
            {
                List<T[]> perList = new List<T[]>();
                GetPermutation(ref perList, com, 0, n - 1);
                list.AddRange(perList);
            }
            return list;
        }
    }
}