using System;
namespace Util.Comp {
    public class CombinationPermutation {
        public static void Main() {
			//全排列使用方法
            foreach(string s in Permutation(new string[] {"a", "b", "c"})){
				Console.WriteLine(s);
			}

			//组合使用方法
			foreach(string s in Combination(new string[] {"a","b","c"},2)){
                Console.WriteLine(s);
            }
        }

        private static int Fac(int n) {
            int nRet = 1;
            for (int i = 2; i <= n; i++)
                nRet *= i;
            return nRet;
        }

        private static int CountC(int n, int r) {
            return Fac(n) / Fac(n - r) / Fac(r);
        }

        //全排列算法
        public static string[] Permutation(string[] s) {
            int n = s.Length;
            int[] seq = new int[n];
            for (int i = 0; i < n; i++)
                seq[i] = i;

            int[] a = new int[n];
            for (int i = 0; i < n; i++) 
                a[i] = seq[i];

            int nCount = Fac(n);
            string[] ret_val = new string[nCount];

            int index = 0;

            for (int i = 0; i < n; i++) {
                ret_val[index] += s[a[i]] + " ";
            }

            ret_val[index].TrimEnd(' ');
            index++;

            for (int k = 1; k < nCount; k++) {
                int m = n - 2;
                while (a[m] > a[m + 1])
                    m--;
                int q = n - 1;
                while (a[q] < a[m]) 
                    q--;
                int tmp;
                tmp = a[m];
                a[m] = a[q];
                a[q] = tmp;

                m = m + 1;
                q = n - 1;

                while (m < q) {
                    tmp = a[m];
                    a[m] = a[q];
                    a[q] = tmp;
                    q--;
                    m++;
                }
                for (int i = 0; i < n; i++) {
                    ret_val[index] += s[a[i]] + " ";
                }

                ret_val[index].TrimEnd(' ');
                index++;
            }
            return ret_val;

        }

        //组合算法
		public static string[] Combination(string[] seq, int n) {
            
            // 获得数组长度，判断组合参数的有效性
            int m = seq.Length;
            if (m< 1 || n > m)
                return null;

            int i, index=0;
            int c = 1; // 组合的数目

            // 计算组合的数目
            for (i = 0; i < n; i++)
                c *= m - i;
            for(i=0;i<n;i++)
                c /= i+1;

            int[] a = new int[m];
            string[] ret_val = new string[c]; // 保存组合的结果

            // 将前n个元素初始化为1
            for (i = 0; i < n; i++)
                a[i] = 1;

            // 输出第一个元素
            for (int j = 0; j < n; j++) {
                ret_val[index] +=  seq[j] + " ";
            }
            
            ret_val[index].TrimEnd(' ');
            index++;

            int m_1 = m - 1;

            while(true){
                // 寻找10 组合
                int flag_found = 0;
                for (i = 0; i < m_1; i++) {
                    if (a[i] == 1 && a[i + 1] == 0) {
                        flag_found = 1;
                        
                        // 将10 改变成 01
                        a[i] = 0;
                        a[i + 1] = 1;

                        // 将左边的1都移动到最左边
                        int one_cnt = 0;
                        for (int k = 0; k < i; k++)
                            if (a[k] == 1) {
                                a[k] = 0;
                                a[one_cnt++] = 1;
                            }

                        // 输出一个组合
                        for (int j = 0; j < m; j++)
                            if (a[j] == 1) 
                                ret_val[index] += seq[j] + " ";