问题描述
前段时间有位新员工同事遇到了对象组合问题，使用递归的方式实现，在代码审阅的过程中发现，该方法在实现上存在业务逻辑与算法逻辑耦合度过高、使用不便于调试的非尾递归等问题，而数组元素组合在我们开发的产品会被很多模块使用，讨论后决定尝试使用非递归的方式得到数组元素组合。
算法
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，当获得适合组合情况时短路当前方法，避免过度的时间或空间损耗。
