471,325 Members | 1,233 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,325 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 7478
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 discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

14 posts views Thread by Dave | last post: by
2 posts views Thread by Brian Pelton | last post: by
7 posts views Thread by Andrew Robinson | last post: by
35 posts views Thread by Lee Crabtree | last post: by
reply views Thread by rosydwin | last post: by

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.