计算位数组中 1 的所有可能位置
本文关键字:有可能 位置 数组 计算 | 更新日期: 2023-09-27 18:36:08
我有一个方法,该方法接收一个数字n
作为参数,并计算所有可能的组合,其中包含位(0,1)数组中的正好n 1
,返回的结果是数字1的位置
例如,假设我们的位数组有 3
个元素和
for n = 1
the function gives : [0] - [1] - [2] (three possible positions)
for n=2
the result will be [0,1] - [0,2] - [1,2] (three possible positions)
对于 n=3 结果将是 [0,1,2](一个可能的位置)
该函数适用于具有 3 个元素的数组,但为 4 个元素给出错误的结果
n = 2 result : [0,1] - [0,2] - [0,3] -[1,2] - [1,3] - [1,2,3]
任何人都可以解释为什么它会在数组大小>= 4 时给出意外的结果
吗?提前致谢
const int arraySize = 4;
static private void Positions(int n, int start, ArrayList prepend, ArrayList results)
{
ArrayList tmp = new ArrayList(prepend);
int end = arraySize - n;
for (int i = start; i <= end; i++)
{
if (end < arraySize - 1)
{
prepend.Add(i);
Positions(n - 1, i + 1, prepend, results);
prepend = tmp;
}
else
results.Add(new ArrayList(prepend) { i });
}
}
这就是我使用该方法的方式
static void Main(string[] args)
{
ArrayList results = new ArrayList();
Positions(2, 0, new ArrayList(), results);
foreach (ArrayList array in results)
{
foreach (var elem in array)
Console.Write(elem);
Console.WriteLine();
}
Console.Read();
}
我认为问题出在这一行:
prepend = tmp;
我认为您打算将前置数组的状态恢复到方法开始时的原始状态。 但是,您正在设置直接引用,因此每次循环迭代时,您都会修改原始前置数组。 如果您每次都在此处复制数组,它似乎可以正常工作:
prepend = new ArrayList(tmp);
然而,所有这些数组复制都不是很有效。 您可以尝试删除刚刚添加的条目以及另一种选择:
prepend.Add(i);
Positions(n - 1, i + 1, prepend);
prepend.Remove(i);
那么从技术上讲,您甚至不再需要tmp
副本。
编辑:另外,对于您的if
声明,我认为您想要类似的东西
if (n > 1)