计算位数组中 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();
    }

计算位数组中 1 的所有可能位置

我认为问题出在这一行:

prepend = tmp;

我认为您打算将前置数组的状态恢复到方法开始时的原始状态。 但是,您正在设置直接引用,因此每次循环迭代时,您都会修改原始前置数组。 如果您每次都在此处复制数组,它似乎可以正常工作:

prepend = new ArrayList(tmp);

然而,所有这些数组复制都不是很有效。 您可以尝试删除刚刚添加的条目以及另一种选择:

prepend.Add(i);
Positions(n - 1, i + 1, prepend);
prepend.Remove(i);

那么从技术上讲,您甚至不再需要tmp副本。

编辑:另外,对于您的if声明,我认为您想要类似的东西

if (n > 1)