Recursive function overwriting output list

Question

I was working on a class to find every combination of N lists. The combination algorithm seems to work flawlessly (when I step through it) but I am having trouble saving off my results. I want to store all the resulting arrays in another list to use later, but when I do the last array combination overwrites all the previous ones. Example input/outputs and my code are below. Does anyone have any ideas how I can fix this? (I've tried reference parameters and global lists with the same result).

/*
 Input: A B C
          X Y

  Expected Output: A X
                   A Y
                   B X
                   B Y
                   C X
                   C Y

  Actual Output:   C Y
                   C Y
                   C Y
                   C Y
                   C Y
                   C Y
*/


public class Combination<T>{
    private static void Combine(T[] res, int ix, List<List<T>> data, ref List<T[]> allCombos){
        foreach (T v in data[ix]){
            res[ix] = v;
            if (ix >= data.Count - 1){
                allCombos.Add(res);
            }else{
                Combine(res, ix + 1, data, ref allCombos);
            }
        }
    }

    public static List<T[]> Combine(List<List<T>> data){
        List<T[]> allCombos = new List<T[]>();
        Combine(new T[data.Count], 0, data, ref allCombos);
        return allCombos;
    }
}

Peter Duniho · Accepted Answer · 2014-11-29 08:51:51Z

3

The main problem here is that you only ever allocate a single T[] instance. Which you just add to your List<T[]> over and over.

Instead of this:

allCombos.Add(res);

You should try this:

allCombos.Add(res.ToArray());

That will create a new copy of the array each time as you add it to the list.

answered Nov 29, 2014 at 8:51

Peter Duniho

71k7 gold badges113 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Codeek · Accepted Answer · 2014-11-29 08:45:13Z

0

try this. I think this should work. I am not on terminal to test it.

public class Combination<T>
{
    static T[] res;
    private static void Combine(int ix, List<List<T>> data, ref List<T[]> allCombos)
    {
        foreach (T v in data[ix])
        {
            res[ix] = v;
            if (ix >= data.Count - 1)
            {
                allCombos.Add(res);
            }
            else
            {
                Combine(res, ix + 1, data, ref allCombos);
            }
        }
    }

public static List<T[]> Combine(List<List<T>> data)
{
    List<T[]> allCombos = new List<T[]>();
    res = new  T[data.Count];
    Combine(0, data, ref allCombos);
    return allCombos;
}

}

answered Nov 29, 2014 at 8:45

Codeek

1,6441 gold badge11 silver badges20 bronze badges

Comments

Ibrahim ben Salah · Accepted Answer · 2014-11-29 10:56:44Z

0

The problem is that res argument is reused and overwritten in each iteration. Here is my solution for you.

using System;
using System.Linq;
using System.Collections.Generic;
....

    private IEnumerable<T[]> Combine<T>(IEnumerable<T[]> data)
    {
        if (!data.Any())
            yield break;

        var head = data.First();
        var tail = Combine(data.Skip(1));
        foreach (var e in head)
        {
            var list = new T[] {e};
            if (!tail.Any())
                yield return list;
            else
            {
                foreach (var t in tail)
                {
                    yield return list.Concat(t).ToArray();
                }
            }
        }
    }

answered Nov 29, 2014 at 10:56

Ibrahim ben Salah

7333 silver badges15 bronze badges

Comments

Diego Chávez Soria · Accepted Answer · 2020-05-16 14:03:38Z

0

For the record, I had a similar issue, with a list of custom objects recently. What did it for me was basically creating a new object, using the object that used to get overwriten ("subTree") as the basis.

//Do this
TreeView newTree= new TreeView { 
name = subTree.name,
children = subTree.children
};
actualTree.Add(newTree);
//Not this
actualTree.Add(subTree)

If I did not do that, I would have gotten the last "subTree" object everytime I tried to add a TreeView element to the "actualTree" List. The solution is to create a new object with the values that you need from other object whenever you have to add an element to your list, so that you are not always adding the same object.

answered May 16, 2020 at 14:03

Diego Chávez Soria

1

Collectives™ on Stack Overflow

Recursive function overwriting output list

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related