CODEWITHSUNDEEP
c#vb.netarraysalgorithm
David Rutten
David Rutten

Reputation: 4806

Insert multiple items into List or Array (no Linq and not quite CodeGolf)

No matter how I try, I can't seem to create a nice and clean algorithm for doing the following:

  1. System.Array (or generic List) data of System.Object
  2. System.Array (or generic List) xval of System.Object
  3. System.Array (or generic List) idxs of System.Int32

xval and idxs contain the same number of elements and idxs contains no values less than zero or larger than data.Length

I need to insert all elements in xval into the data array, where the associated integer in idxs represents the insertion index in the original, unmolested data.

For example:

*data* = {A, B, C, D, E, F, G, H}
*xval* = {U, V, W, X, Y, Z}
*idxs* = {5, 0, 0, 0, 1, 1}

*output* = {V, W, X, A, Y, Z, B, C, D, E, U, F, G, H}

It's easy enough to do, but I always end up with icky code. My best attempt so far (but I'm worried about rounding errors):

  idxs.Reverse()
  xval.Reverse()

  Dim N As Int32 = data.Count + xval.Count
  Dim map(N - 1) As Double
  Dim output(N - 1) As Object

  Dim k As Int32 = -1
  For i As Int32 = 0 To data.Count - 1
    k += 1
    map(k) = i
    output(k) = data(i)
  Next
  For i As Int32 = 0 To xval.Count - 1
    k += 1
    map(k) = idxs(i) - ((i + 1) * 1e-8)
    output(k) = xval(i)
  Next

  Array.Sort(map, output)

Upvotes: 3

Views: 23993

Answers (4)

dbasnett
dbasnett

Reputation: 11773

'*data* = {A, B, C, D, E, F, G, H}
'*xval* = {U, V, W, X, Y, Z}
'*idxs* = {5, 0, 0, 0, 1, 1}
'*output* = {V, W, X, A, Y, Z, B, C, D, E, U, F, G, H}
    Dim data As New List(Of String)
    Dim xval As New List(Of String)
    Dim idxs As New List(Of Integer)
    Dim output As New List(Of String)

    data.AddRange(New String() {"A", "B", "C", "D", "E", "F", "G", "H"})
    xval.AddRange(New String() {"U", "V", "W", "X", "Y", "Z"})
    idxs.AddRange(New Integer() {5, 0, 0, 0, 1, 1})

    For x As Integer = 0 To data.Count - 1 'for each item in the data
        Dim idx As Integer = idxs.IndexOf(x)
        Do While idx <> -1 'do we have xval's for this index
            output.Add(xval(idx)) 'yes add it
            xval.RemoveAt(idx) 'remove the items from xval
            idxs.RemoveAt(idx) 'and idxs
            idx = idxs.IndexOf(x)
        Loop
        output.Add(data(x)) 'add data item to list
    Next

Upvotes: 1

Jeroen
Jeroen

Reputation: 1256

Note that there's no inversion of the lists.

    IList<Object> data = new Object[] { "A", "B", "C", "D", "E", "F", "G", "H" };
    IList<Object> xval = new Object[] { "U", "V", "W", "X", "Y", "Z" };
    IList<int> idxs = new int[] { 5, 0, 0, 0, 1, 1 };

    List<Object> output = new List<object>(data);

    for (int i = 0; i < xval.Count; i++)
    {
        int currentIndex = idxs[i];
        Object dataElement= data[currentIndex]; // We should insert the new element before this element.
        int elementsIndex = output.IndexOf(dataElement);
        output.Insert(elementsIndex, xval[i]);
    }
    return output;

Upvotes: 0

Timwi
Timwi

Reputation: 66583

Here is my attempt, which doesn’t use IndexOf, Sort, Reverse, dictionaries, or doubles.

// input data
char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
char[] xval = { 'U', 'V', 'W', 'X', 'Y', 'Z' };
int[] idxs = { 5, 0, 0, 0, 1, 1 };

// algorithm starts here
var output = new List<char>(data);
for (int i = 0; i < idxs.Length; i++)
{
    // Insert the i’th item in the right place
    output.Insert(idxs[i], xval[i]);

    // Increment all the following indexes so that they
    // will insert in the right place
    for (int j = i + 1; j < idxs.Length; j++)
        if (idxs[j] >= idxs[i])
            idxs[j]++;
}

// outputs V, W, X, A, Y, Z, B, C, D, E, U, F, G, H
Console.WriteLine(string.Join(", ", output));

Of course, if you don’t want the algorithm to modify the idxs array, then simply make a copy of it first.

Upvotes: 4

Grif
Grif

Reputation: 666

I'd go for something like this (replace 'char' with 'object')

char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
char[] xval = new char[] { 'U', 'V', 'W', 'X', 'Y', 'Z' };
int[] idxs = new int[] { 5, 0, 0, 0, 1, 1 };
List<char> output = data.ToList();

Dictionary<int, List<char>> dict = new Dictionary<int, List<char>>();
for (int i = 0; i < idxs.Length; i++)
{
    if (!dict.ContainsKey(idxs[i]))
        dict.Add(idxs[i], new List<char>());
    dict[idxs[i]].Add(xval[i]);
}
List<int> keys = dict.Keys.ToList();
keys.Sort();
keys.Reverse();
foreach (int key in keys)
    output.InsertRange(key,dict[key]);

Upvotes: 1

Related Questions