CODEWITHSUNDEEP
c#
anouar.bagari
anouar.bagari

Reputation: 2104

Calculate all possible positions of 1 in a bit array

I have a method that receives a number n as parameter and calculate all possible combinition containing exactly n 1 in a bit(0,1) array, the result returned is the positions of the number 1

for example suppose that our bit array has 3 elements and 

 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)

and for n=3 the result will be [0,1,2] (one possible position)

the function work correctly for an array with 3 elements, but gives wrong results for 4 elements

  n = 2 result : [0,1] - [0,2] - [0,3] -[1,2] - [1,3] - [1,2,3]

Can any one explain why it gives unexpected results for arraysize >= 4

Thanks in advance

    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 });
        }
    }

this is how i use the method

    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();
    }

Upvotes: 1

Views: 240

Answers (1)

mellamokb
mellamokb

Reputation: 56779

I think the issue is in this line:

prepend = tmp;

You are intending I think to restore the state of the prepend array to the original at the beginning of the method. However, you are setting a direct reference, so with every loop iteration you are modifying the original prepend array. If you copy the array here as well every time, it seems to work correctly:

prepend = new ArrayList(tmp);

All this copying of arrays, however, is not very efficient. You can try removing the entry you just added as well as another alternative:

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

Then technically you don't even need the tmp copy any more.

Edit: Also, for your if statement, I think you want something like

if (n > 1)

Upvotes: 1

Related Questions