lists of pairs
- To: mathgroup at smc.vnet.net
- Subject: [mg8486] lists of pairs
- From: Russell Towle <rustybel at foothill.net>
- Date: Tue, 2 Sep 1997 16:15:27 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Hi all, I have a problem in discarding duplicates from a list of integer
pairs, where if pairs of the form {a, b} and {b,a} exist in the list, I
wish to discard (or select) only one, it doesn't matter which. The method
I use below works, but is slow.
First, here is a sample list of integer pairs:
edges = {{16, 10}, {10, 4}, {4, 9}, {9, 15}, {15, 16}, {16, 15}, {15, 18},
{18, 20}, {20, 19}, {19, 16}, {16, 19}, {19, 14}, {14, 8}, {8, 10}, {10,
16}, {10, 8}, {8, 3}, {3, 1}, {1, 4}, {4, 10}, {4, 1}, {1, 2}, {2, 7}, {7,
9}, {9, 4}, {9, 15}, {15, 18}, {18, 13}, {13, 7}, {7, 9}, {19, 20}, {20,
17}, {17, 12}, {12, 14}, {14, 19}, {8, 14}, {14, 12}, {12, 6}, {6, 3}, {3,
8}, {1, 3}, {3, 6}, {6, 5}, {5, 2}, {2, 1}, {7, 2}, {2, 5}, {5, 11}, {11,
13}, {13, 7}, {18, 13}, {13, 11}, {11, 17}, {17, 20}, {20, 18}, {12, 17},
{17, 11}, {11, 5}, {5, 6}, {6, 12}}
It is this long:
In[35]:=
Length [ edges ]
Out[35]=
60
However, this is twice as long as I want, for every pair {a, b} has an
unwanted opposite {b, a}.
This is my present method:
(*find duplicates (indices in reverse order)*)
(*7.60 seconds*)
c=Table[
Position[edges, x_ /; x == edges[[i]] || x == Reverse[edges[[i]]] ],
{i,Length[edges]}];
Now I have the positions of all duplicates, twice over, so I use Union and
Take the First elements.
f=Map[Take[#,1]&, Union[c]]
And, this is the final list I wanted from the beginning:
f=Flatten[f,2]
Suggestions? It is desired to minimize the time it takes to do this.
Russell Towle
Giant Gap Press: books on California history, digital topographic maps
P.O. Box 141
Dutch Flat, California 95714
------------------------------
Voice: (916) 389-2872
e-mail: rustybel at foothill.net
------------------------------