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

[Andrew Dalke]

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?

Cheers,

				Andrew
				dalke at dalkescientific.com