[TIP] Which is the proper way to test an "unordered list"

Andrew Dalke dalke at dalkescientific.com
Thu May 17 16:16:09 PDT 2012

On May 17, 2012, at 3:30 AM, Jorge Vargas wrote:
> My question is which will be the proper way to test for this when the
> "order of the list" is not valid?

The right answer depends on what the data set contains. Others have
already suggested:

 1) sorting; but that assumes that the objects can be compared
      by inequality

 2) converting to a set, but that assumes that objects are hashable,
      and that duplicates can be ignored

You can fix #2 by

  3) use a collections.Counter; this still requires hashable objects
       but doesn't have the count problem

The only generic solution is:

  4) Do the O(n*m) test of checking each item from one list to see
       if it occurs in the other, removing matches as they are found

Most people are uncomfortable with potentially quadratic worst-case
times, but with only a couple of states, this isn't a problem.

In your case, you can probably use the sets solution without a problem,
especially if your "next" implementation verifies that there are no
duplicates in the list. Or as Herman's commented, perhaps your
implementation is more appropriate with a set in the first place?


				dalke at dalkescientific.com

More information about the testing-in-python mailing list