473,320 Members | 1,948 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Search one List<t> for a sub List<t>

I have two List<t>. I need to search ListA to see if it contains ListB

So:

ListA { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Searching ListA with { 4, 5, 6 } would return true and an index of 3.
Searching ListA with { 4, 6, 5 } would return false and or an index of -1.

Hope my pseudo coding is clear?

Is there any easy way of doing this with generic lists? I am looking at
lists of strings for now.

Thanks,
Jan 10 '06 #1
7 7729
KJ
This is an interesting post, and I wonder if anyone has implemented a
Set class yet using generics (and would like to share it).

Jan 10 '06 #2
"KJ" <n_**********@mail.com> wrote in news:1136932047.192507.134960
@f14g2000cwb.googlegroups.com:
This is an interesting post, and I wonder if anyone has implemented a
Set class yet using generics (and would like to share it).


Although it doesn't directly affect your question, in detail, he couldn't
use a set class because he is dependent on order, which is contrary to set
theory.

-mdb
Jan 10 '06 #3
ok, did a bruit force type thing. would appreciate any comments on the code.
Seems to work:

using System;

using System.Collections.Generic;

using System.Text;

class ListSearch<T>

{

public ListSearch()

{

}

public int IndexOf(List<T> list, List<T> subList)

{

return IndexOf(list, subList, 0);

}

public int IndexOf(List<T> list, List<T> subList, int start)

{

T s = subList[0];

int i = list.FindIndex(start, delegate(T t) { return
t.Equals(s); });

if (i < 0)

{

// found no initial match

return -1;

}

for (int j = 1; j < subList.Count; j++)

{

if (!list[j + i].Equals(subList[j]))

{

// got here because we found a non equal value.

// if there are more elements in the list, start over at the
next element

if (j + i < list.Count)

{

return IndexOf(list, subList, i + 1);

}

else

{

return -1;

}

}

}

return i;

}

}

List<int> list = new List<int>();

List<int> subList = new List<int>();

list.Add(1); // 0

list.Add(2); // 1

list.Add(3); // 2

list.Add(4); // 3

list.Add(4); // 4

list.Add(5); // 5

subList.Add(4);

subList.Add(5);

ListSearch<int> listSearch = new ListSearch<int>();

int i = listSearch.IndexOf(list, subList);
returns 4 which is correct.

--

Andrew Robinson
blog.binaryocean.com
"Michael Bray" <mbray@makeDIntoDot_ctiusaDcom> wrote in message
news:Xn****************************@207.46.248.16. ..
"KJ" <n_**********@mail.com> wrote in news:1136932047.192507.134960
@f14g2000cwb.googlegroups.com:
This is an interesting post, and I wonder if anyone has implemented a
Set class yet using generics (and would like to share it).


Although it doesn't directly affect your question, in detail, he couldn't
use a set class because he is dependent on order, which is contrary to set
theory.

-mdb

Jan 10 '06 #4
How about this:

class SearchableList<T> : List<T>
{
public int FindSubList(SearchableList<T> sublist, int start)
{
for (int i = start; i <= this.Count-sublist.Count ; i++)
{
int j;
for (j = 0; j < sublist.Count; j++)
if (!this[i+j].Equals(sublist[j]) ) break;

if (j==sublist.Count )
return i ;
}

return -1;
}
}
Luke

Jan 11 '06 #5
Luke,

Your version is cleaner but think they perform the same. I modified it a bit
further.

Thanks!

public class ListSearch<T>
{
public static int IndexOf(List<T> list, List<T> sublist)
{
return IndexOf(0, list, sublist);
}

public static int IndexOf(int start, List<T> list, List<T> sublist)
{
for (int i = start; i <= list.Count - sublist.Count; i++)
{
int j = 0;
while (j < sublist.Count)
{
if (!list[i + j].Equals(sublist[j++])) break;
}
if (j == sublist.Count) return i;
}

return -1;
}
}

"Luke Zhang [MSFT]" <lu******@online.microsoft.com> wrote in message
news:Vf**************@TK2MSFTNGXA02.phx.gbl...
How about this:

class SearchableList<T> : List<T>
{
public int FindSubList(SearchableList<T> sublist, int start)
{
for (int i = start; i <= this.Count-sublist.Count ; i++)
{
int j;
for (j = 0; j < sublist.Count; j++)
if (!this[i+j].Equals(sublist[j]) ) break;

if (j==sublist.Count )
return i ;
}

return -1;
}
}
Luke

Jan 11 '06 #6
Slight bug. Fixed:

public static class ListSearch<T>
{
public static int IndexOf(List<T> list, List<T> sublist)
{
return IndexOf(0, list, sublist);
}

public static int IndexOf(int start, List<T> list, List<T> sublist)
{
for (int i = start; i <= list.Count - sublist.Count; i++)
{
int j = 0;
while (j < sublist.Count)
{
if (!list[i + j].Equals(sublist[j])) break;
if (j < sublist.Count) j++;
}

if (j == sublist.Count) return i;
}

return -1;
}
}

"Luke Zhang [MSFT]" <lu******@online.microsoft.com> wrote in message
news:Vf**************@TK2MSFTNGXA02.phx.gbl...
How about this:

class SearchableList<T> : List<T>
{
public int FindSubList(SearchableList<T> sublist, int start)
{
for (int i = start; i <= this.Count-sublist.Count ; i++)
{
int j;
for (j = 0; j < sublist.Count; j++)
if (!this[i+j].Equals(sublist[j]) ) break;

if (j==sublist.Count )
return i ;
}

return -1;
}
}
Luke

Jan 11 '06 #7
Looks great! :)
Luke

Jan 12 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

14
by: Dave | last post by:
Hello all, After perusing the Standard, I believe it is true to say that once you insert an element into a std::list<>, its location in memory never changes. This makes a std::list<> ideal for...
4
by: matty.hall | last post by:
I have two classes: a base class (BaseClass) and a class deriving from it (DerivedClass). I have a List<DerivedClass> that for various reasons needs to be of that type, and not a List<BaseClass>....
2
by: Brian Pelton | last post by:
I am not sure how to fix this problem I've stumbled into... I have a list<> of an interface type. I need to pass that list to a method that adds more objects to the list. But, eventually, I...
3
by: Varangian | last post by:
Hello, there I have a problem with regards to System.Collections.Generic.List<T> I need to pass a class with implements an interface - TestClass : IPerson I put this class in a...
9
by: Paul | last post by:
Hi, I feel I'm going around circles on this one and would appreciate some other points of view. From a design / encapsulation point of view, what's the best practise for returning a private...
7
by: Andrew Robinson | last post by:
I have a method that needs to return either a Dictionary<k,vor a List<v> depending on input parameters and options to the method. 1. Is there any way to convert from a dictionary to a list...
56
by: Zytan | last post by:
Obviously you can't just use a simple for loop, since you may skip over elements. You could modify the loop counter each time an element is deleted. But, the loop ending condition must be...
45
by: Zytan | last post by:
This returns the following error: "Cannot modify the return value of 'System.Collections.Generic.List<MyStruct>.this' because it is not a variable" and I have no idea why! Do lists return copies...
4
by: Peted | last post by:
I have the following code public enum pdfFlags { PFD_DRAW_TO_WINDOW, PFD_DRAW_TO_BITMAP, PFD_SUPPORT_GDI, PFD_SUPPORT_OPENGL, PFD_GENERIC_ACCELERATED, PFD_GENERIC_FORMAT,
35
by: Lee Crabtree | last post by:
This seems inconsistent and more than a little bizarre. Array.Clear sets all elements of the array to their default values (0, null, whatever), whereas List<>.Clear removes all items from the...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.