问题描述

前段时间有位新员工同事遇到了对象组合问题，使用递归的方式实现，在代码审阅的过程中发现，该方法在实现上存在业务逻辑与算法逻辑耦合度过高、使用不便于调试的非尾递归等问题，而数组元素组合在我们开发的产品会被很多模块使用，讨论后决定尝试使用非递归的方式得到数组元素组合。

算法

graph TD;
开始-->init(初始化组合)
init-->set_cursor(将当前指针设定为最后一位)
set_cursor-->plus(指针位元素自增)
plus-->judge_max{指针位是否超过数组长度}
judge_max--是-->move_cursor(指针位前移一位)
judge_max--否-->success(自增结束)
success-->plus_back(从指针位后一位开始,每位比前一位增加1)
move_cursor-->plus
plus_back-->set_cursor
plus_back-->judge_overflow{检查是否有元素大于数组长度}
judge_overflow--是-->组合遍历结束
move_cursor-->negative{当前指针为-1?}
negative--是-->组合遍历结束
negative--否-->plus

形象点说，就是可以把组合视为一个计分牌，且每一位数值必须大于前一位数值
以 为例，初始化后的组合数是123，move后得到124，125。
对125进行move后得到126，因为末位大于5，触发前一位自增，因此得到134，依此类推，可以得到135，234，235共5总组合情况。

代码

        /// <summary>
        /// 计算得到组合数
        /// </summary>
        /// <param name="m">元素总数</param>
        /// <param name="n">组合数个数</param>
        /// <returns>组合列表，每个List<int>代表一个组合</returns>
    static List<List<int>> Combination(int m, int n)
        {
            var result = new List<List<int>>();
            var value = new int[n];
            for (var i = 0; i < n; i++)
                value[i] = i;
            var count = 0;
            do
            {
                count++;
                Console.WriteLine(string.Join(',', value));
            } while (Move(ref value, m));
            Console.WriteLine($"Total:{count}");
            return result;
        }
        /// <summary>
        /// 计算下一个组合
        /// </summary>
        /// <param name="value">当前组合</param>
        /// <param name="max">元素个数</param>
        /// <returns>true:获取组合成功，false:获取组合失败</returns>
        static bool Move(ref int[] value, int max)
        {
            var currentIndex = value.Length - 1;
            while (currentIndex > -1)
            {
                var current = value[currentIndex];
                current++;
                if (current == max)
                    currentIndex--;
                else
                {
                    value[currentIndex] = current;
                    for (var i = currentIndex + 1; i < value.Length; i++)
                    {
                        value[i] = value[i - 1] + 1;
                    }
                    if (!value.Any(x => x >= max))
                        return true;
                }
            }
            return false;
        }

总结

该方法每获取一次组合的时间复杂度最好情况是O(1)，最坏情况是O()，平均情况是O()，使用C#代码时可以考虑把方法返回类型改为IEnumerable，当获得适合组合情况时短路当前方法，避免过度的时间或空间损耗。