Ask Ben: Removing Duplicate List Items While Maintaining Original List Order

Posted January 15, 2009 at 9:50 AM

Tags: ColdFusion, Ask Ben

Do you know a way to remove duplicates from a list while keeping it sorted a-z? I have a list with the values I want and sorted correctly, but I have yet to find a way to sort it correctly. Any help would be great! Thanks!!

A while back, I described a very simple, elegant solution for using ColdFusion structs to remove duplicate values from a list. While nice, the limitations of that algorithm were that it did not ensure case sensitivity of the list items (depending on how you coded it) and it did not maintain any ordering of the original list. For the most part, I work with lists of IDs, so that was not a problem.

If we want to maintain the case sensitivity and ordering of the original list, we just need to add a little more logic to this idea. We can still use the ColdFusion struct as a look-up for our unique values; but, we will no longer use the struct to render our final list of unique values:

 Launch code in new window » Download code as text file »

As you can see, as we loop over our existing list, we are building a parallel list (using an array) with the unique values. Since both lists and arrays have inherent ordering, our use of ArrayAppend() maintains the order of the original list. Every time we hit a new unique value, we add it to our struct-look-up table to make sure that we never copy a duplicate value over to the new list.

When we run the above code, we get the following output:

1,2,3,4,5,9,0

The list is now composed of unique values in the original order. I am using an array and ArrayAppend() to build the new list rather than ListAppend() only because I have found arrays to be faster than string concatenation. Of course, for small lists, there would be zero difference in performance. I hope that helps.

Download Code Snippet ZIP File

Post Comment  |  Ask Ben  |  Permalink  |  Other Searches  |  Print Page

• Add To Del.icio.us
• Add To Digg
• Add to Spurl.net
• Add to Wists
• Add to Simpy
• Add to Newsvine
• Add to BlinkList
• Add to Furl
• Add to reddit
• Add to FARK
• Add to BlogMarks
• Add to Yahoo! My Web
• Add to smarking
• Add to Ma.gnolia
• Add to Segnalo

Reader Comments

Thanks Ben, exactly what I needed!!

I use your structure dedupe idea and then just do a listsort to get the sorting correctly.

@Adam,

Awesome man, glad to help.

@Aaron,

That's a good idea as well. I guess when I read the question, I ignored the "a-z" part and just thought about the order of the original list. Nice catch.

Very very nice. I was a bit confused though when I read "The list is not composed of unique values in the original order" (emphasis added), and it took me a while to realize that you meant "... now composed ...." I guess I'm not quite awake yet.

@Matt,

Ooops. Good catch - typo fixed.

how about this:

// list with duplicate values.
strList = "1,1,2,3,4,1,3,5,5,1,9,0,1";

// new list to the copy that wont have dups
strNewList = "";

while (listLen(strList)) {
if (!listFind(strNewList,listFirst(strList))) strNewList = listAppend(strNewList,listFirst(strList));
strList = listRest(strList);
}

<cfoutput>#strNewList#</cfoutput>

You know, I just posted a method that uses listAppend instead of arrayAppend, and now I realize that you explained why you used the array instead of the list. Doh! My bad. You can delete my post if you like.

For your "How NOT to do it" file:

<cfset strList="1,1,2,3,4,1,3,5,5,1,9,0,1">
<cfset q=queryNew("item,position")>
<cfloop list="#strList#" index="j">
<cfset queryAddRow(q)>
<cfset querySetCell(q, "item", j, q.recordCount)>
<cfset querySetCell(q, "position", q.recordCount, q.recordCount)>
</cfloop>
<cfquery name="r" dbtype="query">
SELECT item, MIN(position) as firstPosition
FROM q
GROUP BY item
</cfquery>
<cfquery name="s" dbtype="query">
SELECT q.item, q.position
FROM q, r
WHERE (q.item = r.item) AND (q.position = r.firstPosition)
ORDER BY q.position
</cfquery>
<cfset strNewList=valueList(s.item)>

@Chris,

No worries my man. For small lists, the speed differences are not going to be noticeable.

@Rick,

If you want, I can set that algorithm up as a web service on my server and then you can modify your example to use CFHTTP to pass in the list and I'll return the unique version ;)

I could not resist -
Here is a version without cfloop based on java
It will allow you to retain the original list sort or to sort any way you want.

It is based on posts I have read from:
Adrian J. Moreno and Ben Nadel
Links to those posts are at the bottom

<cfset strList = "1,1,2,3,4,1,3,5,5,1,9,0,1" />
<cfset newListArray = listToArray( strList ) />
<cfset lhs = createObject("java", "java.util.LinkedHashSet") />
<cfset lhs.init( newListArray ) />

<!--- Clear out the original elements --->
<cfset newListArray.clear() />

<!--- Add all of the unique elements back from lhs --->
<cfset newListArray.addAll( lhs ) />

<!--- If you want to sort the array --->
<!--- either with Java --->
<cfset CreateObject( "java", "java.util.Collections" ).Sort( newListArray ) />
<!--- or with CF --->
<!--- <cfset temp = arraySort( newListArray,"numeric","asc") > --->

<!--- show the clean list --->
<cfoutput>#arrayToList( newListArray )#</cfoutput>

source posts:
http://www.iknowkungfoo.com/blog/index.cfm/2008/10/22/Remove-duplicate-list-or-array-elements-using-ColdFusion-and-Java
http://www.bennadel.com/blog/280-Randomly-Sort-A-ColdFusion-Array-Updated-Thanks-Mark-Mandel.htm

Or ...
http://wiki.openbluedragon.org/wiki/index.php/ListRemoveDuplicates()

Didn't like the () at the end of the last URL I posted, so let's try this:
http://tinyurl.com/a4oy3u

Ben said: "you can modify your example to use CFHTTP to pass in the list"

Well played, sir. Well played.

i did this for a couple of lists, just a little differently, but the results i think are the same. the lists were css and js files to be written to the document head, so the original order had to be maintained and the first occurrence of a duplicate had to remain. i did it by looping the list from end to start and setting the struct value to the index. then a numeric sort on the struct kept the original order. if you see any place this might fail, i'd be grateful to hear it.

<cfset objNoDupes = structNew()>

<cfloop from="#listlen( strList )#" to="1" step="-1" index="i">
<cfset objNoDupes[ listgetat( strList, i ) ] = i>
</cfloop>

<cfset strNewList = ArrayToList( structSort(objNoDupes, 'numeric') )>

@Jeff,

Good links. I always like learning about more Java-based methods (referring to the link that is not mine - Im not that big headed :)).

@Matt,

Ah, that makes it too easy.

@DB,

I don't think that one can maintain (or guarantee) the list order.

this is very similar to chris' example, but here it is anyway, and keeps order as well.

sz_List = '1,2,3,2,2,3,2,2,345,4324,23';
sz_ListNew = '';
for (i=1; i<= listLen(sz_List ); i++){
if(listFindNoCase(sz_listNew, listGetAt(sz_List , i)) == 0 )
sz_listNew = listAppend(sz_listNew, listGetAt(sz_List,i));
}

CFLib has a couple of similar functions. You would need to reorder by a separate function thogh.

http://cflib.org/udf/ListDeleteDuplicates
http://cflib.org/udf/ListDeleteDuplicatesNoCase

This method wont work if you need case sensitivity, since the struct key bins are case insensitive.

@Jon,

This is true. If you need case-sensitivity, I suppose you could go with ListFindNoCase() on the new list rather than using a struct. Not sure if the Java method that @Jeff mentions above will be case-sensitive.

@Ben, @Jon

Yes in the current format the Java solution is case sensitive.
The CF arraySort() will also sort the array "text" or "textnocase" so that you can really control the results should you want to sort them.

Nice.
once again , you saved me a bunch of time with this. thank yoouuu sir!

Post Comment  |  Ask Ben

Post A Comment

Please review the following issues:

Author Name:
Author Email:
Author Website:
Comment:	Formatting: <strong>bold</strong> <em>italic<em>
	Remember my information
	Subscribe to entry *
	Send me a copy of this comment (as part of the comment thread)

 

* If you subscribe, any new posts to this thread will be sent to your email address.