Combinatorics.cs

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

namespace HyperGraphModel
{
    public static class Combinatorics<T>
    {
        /// <summary>
        /// Множество перестановок (без повторения) элементов входящего множества
        /// </summary>
        /// <param name="array">Входящее множество</param>
        /// <returns></returns>
        public static List<List<T>> Transposition(List<T> array)
        {
            List<List<T>> result = new List<List<T>>();

            int[] temp = new int[array.Count];
            int n = array.Count;
            for (int i = 0; i < n; i++)
                temp[i] = i + 1;

            while (true)
            {
                int j = n - 2;
                while (j != -1 && temp[j] >= temp[j + 1])
                    j--;
                if (j == -1)
                    break;

                int k = n - 1;
                while (temp[j] >= temp[k]) k--;

                Swap(ref temp[j], ref temp[k]);
                int l = j + 1, r = n - 1;
                while (l < r)
                    Swap(ref temp[l++], ref temp[r--]);
                result.Add(AddInOrderFromList(array, temp));
            }

            return result;
        }
        /// <summary>
        /// Создает новый массив (лист) типа Т, со значениями в порядке массива order
        /// </summary>
        /// <param name="list">Лист значений</param>
        /// <param name="order">Массив порядка значений</param>
        /// <returns></returns>
        private static List<T> AddInOrderFromList(List<T> list, int[] order)
        {
            List<T> temp = null;

            try
            {
                temp = new List<T>();
                for (int i = 0; i < order.Length; i++)
                    temp.Add(list[order[i] - 1]);
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
            return temp;
        }

        private static bool Swap<t>(ref t a, ref t b)
        {
            try
            {
                t temp = a;
                a = b;
                b = temp;
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                return false;
            }
            return true;
        }

        /// <summary>
        /// Маска, позволяющая перебрать множество сочетаний элементов с повторениями
        /// </summary>
        /// <param name="n">Мощность множества элементов</param>
        /// <param name="m">По скольку элементов нужно сочетать выборку</param>
        /// <returns>Вернет двумерный список размера n^m, где каждый список имеет размер m</returns>
        public static List<List<int>> CombinationWithReplays(int n, int m)
        {
            List<List<int>> test2 = new List<List<int>>();
            bool NextSet(int[] aa, int nn, int mm)
            {
                int j = mm - 1;
                while (j >= 0 && aa[j] == nn) j--;
                if (j < 0) return false;
                if (aa[j] >= nn)
                    j--;
                aa[j]++;
                if (j == mm - 1) return true;
                for (int k = j + 1; k < mm; k++)
                    aa[k] = 1;
                return true;
            }
            List<int> minus(List<int> from)
            {
                for (int i = 0; i < from.Count; i++)
                    from[i]--;
                return from;
            }
            int h = n > m ? n : m; // размер массива а выбирается как max(n,m)
            int[] a = new int[h];
            for (int i = 0; i < h; i++)
                a[i] = 1;
            test2.Add(minus(a.Take(m).ToList()));
            while (NextSet(a, n, m))
                test2.Add(minus(a.Take(m).ToList()));
            return test2;
        }

        /// <summary>
        /// Маска, позволяющая перебрать множество сочетаний элементов без повторений
        /// </summary>
        /// <param name="n">Мощность множества элементов</param>
        /// <param name="m">По скольку элементов нужно сочетать выборку</param>
        /// <returns>Вернет двумерный список размера n^m, где каждый список имеет размер m</returns>
        public static List<List<int>> СombinationWithoutReplays(int n, int m)
        {
            List<List<int>> test2 = new List<List<int>>();
            bool NextSet(int[] aa, int nn, int mm)
            {
                int k = mm;
                for (int i = k - 1; i >= 0; --i)
                    if (aa[i] < nn - k + i + 1)
                    {
                        aa[i]++;
                        for (int j = i + 1; j < k; j++)
                            aa[j] = aa[j - 1] + 1;
                        return true;
                    }
                return false;
            }
            List<int> minus(List<int> from)
            {
                for (int i = 0; i < from.Count; i++)
                    from[i]--;
                return from;
            }
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = i + 1;
            test2.Add(minus(a.Take(m).ToList()));
            if (n >= m)
            {
                while (NextSet(a, n, m))
                    test2.Add(minus(a.Take(m).ToList()));
            }
            return test2;
        }
    }
}