我正在尝试编写一个C#函数,给定一个像new int [] {2,3,2}的参数,它指定每个元素的上限1,将返回以下内容(通过IEnumberable< int []>):
0 0 0
0 0 1
0 1 0
0 2 0
1 0 0
0 1 1
0 2 1
1 0 1
1 1 0
1 2 0
1 1 1
1 2 1
请注意,顺序很重要:所有排列都包含0个非零元素,后跟所有包含1个非零元素的排列等.在其中一个组中,顺序无关紧要.
我意识到这些在技术上可能不是排列,但它是我所知道的最接近的术语.另外我意识到一种方法是以某种顺序返回所有排列,然后根据计算有多少非零元素的函数对它们进行排序,但我希望有更优雅和高效的东西.
解决方法:
我想要一个不首先计算所有内容然后排序的答案,同时仍然只经历最少量的事情.这就是我所拥有的.请注意,外部修改int []可能会搞砸结果(或者,可能会返回一个新的int []).
第一种方法告诉辅助方法它在输出中需要多少0.然后帮助程序计算结果,如果它不能填充足够的0或者它遍历所有数据则停止.
static IEnumerable<int[]> Permutation(int[] bounds)
{
for(int num0s = bounds.Length; num0s >= 0; --num0s)
{
foreach(int[] ret in PermHelper(num0s, 0, bounds, new int[bounds.Length]))
yield return ret;
}
}
static IEnumerable<int[]> PermHelper(int num0s, int index, int[] bounds, int[] result)
{
//Last index.
if(index == bounds.Length - 1)
{
if(num0s > 0)
{
result[index] = 0;
yield return result;
}
else
{
for(int i = 1; i < bounds[index]; ++i)
{
result[index] = i;
yield return result;
}
}
}
//Others.
else
{
//still need more 0s.
if(num0s > 0)
{
result[index] = 0;
foreach(int[] perm in PermHelper(num0s - 1, index + 1, bounds, result))
yield return perm;
}
//Make sure there are enough 0s left if this one isn't a 0.
if(num0s < bounds.Length - index)
{
for(int i = 1; i < bounds[index]; ++i)
{
result[index] = i;
foreach(int[] perm in PermHelper(num0s, index + 1, bounds, result))
yield return perm;
}
}
}
}