How to Compare Two Unordered Tcl Lists

The Problem

I want to compare two lists for equality, but disregard the order. For example: {a b c} and {b a c} are equal, but {a b c} {a b c d} are not.

The Solutions

There are several solutions to this problem. The first is to first sort the two lists, then compare them. Another solution is to roll my own comparison function. Finally, I can use the equal command from the struct::set package.

The first solution involves sorting both lists, then comparing them. When the size of either list is large, then sorting will take time, thus hurts performance. Therefore, this solution works fine for small to medium size lists. I am lazy (it’s a virtue!) so rolling my own solution is out of the question, especially if there are solutions out there, such as the last solution.

This solution involves a little-known package called struct::set. This package implements sets, which is also a list. For the purpose of our discussion, we will concentrate on the struct::set equal command. Below is some examples from the Tcl shell (tclsh):

53 % package require struct::set
2.2.3
54 % struct::set equal {a b c} {b c a}
1
55 % struct::set equal {a b c} {a b c}
1
56 % struct::set equal {a b c} {a b}
0
57 % struct::set equal {a b c} {a b c a b c}
1

Discussion

  • Line 53 imports the struct::set package
  • Line 54 compares two lists for equality, regardless of order. In this instance, the equal command returns 1, which is true.
  • Line 55 compares two identical lists
  • Line 56 compares two different lists
  • Line 57 comes as a surprise: what is going on here? these two lists are equal? Recall that in a set, each element appears only once. That means {a b c a b c} is the same as {a b c} from a set point of view. This is a caveat one needs to take in consideration.

As we can see from the interactive session, the struct::set equal command compares two lists for equality–from a set standpoint. This command works well for lists with unique elements, but will fall short if a list contains duplicated elements.

3 thoughts on “How to Compare Two Unordered Tcl Lists

  1. John

    Hi, I have a problem with comparing two files and I can not find solutions. I hope you can help me.

    Problem:
    file1 file2

    cl = 5 cl = 7
    o = 4 o = 5
    p = 9 d = 1

    i need change value o in file1 same like in file2 and rest values have to be same.
    result in file2:
    cl = 7
    o = 4
    d = 1

    Thank you

    PS: i sorry for my bad english

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s