Create lists of equivalences from pairs

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
5
down vote

favorite












I have a list of pairs, e.g.,



ex1=1,2,1,3,2,3, 4,5, 6,7,6,8, 7,8


that I would like to merge into the list



output=1,2,3,4,5,6,7,8


via the transitive property. More explicitly, if i,jis a pair in the original list, then i and j should both be in the same list. Furthermore, if i,j and j,k are pairs, then i, j, and k should all be in the same list. Another way to view this problem is that we begin with lists of binary equivalences and wish to construct all the equivalence classes.



In the case that the original list of pairs satisfies the property that if i,j is listed as a pair then j,i is also listed, e.g.,



ex2=1,2,2,1,1,3,3,1, 2,3,3,2, 4,5,5,4, 6,7,7,6,6,8,8,6,7,8,8,7


then the following function works:



equivClasses[listOfPairs_]:=listOfPairs//GatherBy[#, First]&//Map[Fold[Union], #, 1]&// Union


However, this function fails when the reverse of each pair doesn't necessarily appear, e.g., equivClasses[ex1]=1,2,3,2,3,.... We can manufacture such a new list easily, e.g., by



newList=(Sort/@ex1)~Join~(ReverseSort/@ex1)//Union


and then calling equivClasses as before.



Q1 Is the above function equivClasses reasonable? It feels a bit kludgy to me, in particular insofar as the code creates $n$-copies of each sublist of length $n$ before Union-ing them away.



Q2 The scope in which this problem has arisen is somewhat large and computationally expensive. The list of pairs that I can generate contains ~10^5 pairs of integers and takes ~10min if I only generate the pairs i,j with i < j. I can certainly do the Sort...~Join~ReverseSort business, this seems a bit inefficient insofar as it doubles the memory usage (although this step does run reasonably fast, about 0.005sec on my machine). How can I optimize this code?



Q3 Particularly problematic is the case when the list of pairs doesn't include all pairwise comparisons, e.g., 1,2,2,3 which should still get sorted into 1,2,3. What can I do in this case?






list-manipulation performance-tuning







share|improve this question

















  • 1




    closely related: Using Gather to rearrange my data, Computing the equivalence classes of the symmetric transitive closure of a relation
    – kglr
    27 mins ago














up vote
5
down vote

favorite












I have a list of pairs, e.g.,



ex1=1,2,1,3,2,3, 4,5, 6,7,6,8, 7,8


that I would like to merge into the list



output=1,2,3,4,5,6,7,8


via the transitive property. More explicitly, if i,jis a pair in the original list, then i and j should both be in the same list. Furthermore, if i,j and j,k are pairs, then i, j, and k should all be in the same list. Another way to view this problem is that we begin with lists of binary equivalences and wish to construct all the equivalence classes.



In the case that the original list of pairs satisfies the property that if i,j is listed as a pair then j,i is also listed, e.g.,



ex2=1,2,2,1,1,3,3,1, 2,3,3,2, 4,5,5,4, 6,7,7,6,6,8,8,6,7,8,8,7


then the following function works:



equivClasses[listOfPairs_]:=listOfPairs//GatherBy[#, First]&//Map[Fold[Union], #, 1]&// Union


However, this function fails when the reverse of each pair doesn't necessarily appear, e.g., equivClasses[ex1]=1,2,3,2,3,.... We can manufacture such a new list easily, e.g., by



newList=(Sort/@ex1)~Join~(ReverseSort/@ex1)//Union


and then calling equivClasses as before.



Q1 Is the above function equivClasses reasonable? It feels a bit kludgy to me, in particular insofar as the code creates $n$-copies of each sublist of length $n$ before Union-ing them away.



Q2 The scope in which this problem has arisen is somewhat large and computationally expensive. The list of pairs that I can generate contains ~10^5 pairs of integers and takes ~10min if I only generate the pairs i,j with i < j. I can certainly do the Sort...~Join~ReverseSort business, this seems a bit inefficient insofar as it doubles the memory usage (although this step does run reasonably fast, about 0.005sec on my machine). How can I optimize this code?



Q3 Particularly problematic is the case when the list of pairs doesn't include all pairwise comparisons, e.g., 1,2,2,3 which should still get sorted into 1,2,3. What can I do in this case?






list-manipulation performance-tuning







share|improve this question

















  • 1




    closely related: Using Gather to rearrange my data, Computing the equivalence classes of the symmetric transitive closure of a relation
    – kglr
    27 mins ago












up vote
5
down vote

favorite









up vote
5
down vote

favorite











I have a list of pairs, e.g.,



ex1=1,2,1,3,2,3, 4,5, 6,7,6,8, 7,8


that I would like to merge into the list



output=1,2,3,4,5,6,7,8


via the transitive property. More explicitly, if i,jis a pair in the original list, then i and j should both be in the same list. Furthermore, if i,j and j,k are pairs, then i, j, and k should all be in the same list. Another way to view this problem is that we begin with lists of binary equivalences and wish to construct all the equivalence classes.



In the case that the original list of pairs satisfies the property that if i,j is listed as a pair then j,i is also listed, e.g.,



ex2=1,2,2,1,1,3,3,1, 2,3,3,2, 4,5,5,4, 6,7,7,6,6,8,8,6,7,8,8,7


then the following function works:



equivClasses[listOfPairs_]:=listOfPairs//GatherBy[#, First]&//Map[Fold[Union], #, 1]&// Union


However, this function fails when the reverse of each pair doesn't necessarily appear, e.g., equivClasses[ex1]=1,2,3,2,3,.... We can manufacture such a new list easily, e.g., by



newList=(Sort/@ex1)~Join~(ReverseSort/@ex1)//Union


and then calling equivClasses as before.



Q1 Is the above function equivClasses reasonable? It feels a bit kludgy to me, in particular insofar as the code creates $n$-copies of each sublist of length $n$ before Union-ing them away.



Q2 The scope in which this problem has arisen is somewhat large and computationally expensive. The list of pairs that I can generate contains ~10^5 pairs of integers and takes ~10min if I only generate the pairs i,j with i < j. I can certainly do the Sort...~Join~ReverseSort business, this seems a bit inefficient insofar as it doubles the memory usage (although this step does run reasonably fast, about 0.005sec on my machine). How can I optimize this code?



Q3 Particularly problematic is the case when the list of pairs doesn't include all pairwise comparisons, e.g., 1,2,2,3 which should still get sorted into 1,2,3. What can I do in this case?






list-manipulation performance-tuning







share|improve this question













I have a list of pairs, e.g.,



ex1=1,2,1,3,2,3, 4,5, 6,7,6,8, 7,8


that I would like to merge into the list



output=1,2,3,4,5,6,7,8


via the transitive property. More explicitly, if i,jis a pair in the original list, then i and j should both be in the same list. Furthermore, if i,j and j,k are pairs, then i, j, and k should all be in the same list. Another way to view this problem is that we begin with lists of binary equivalences and wish to construct all the equivalence classes.



In the case that the original list of pairs satisfies the property that if i,j is listed as a pair then j,i is also listed, e.g.,



ex2=1,2,2,1,1,3,3,1, 2,3,3,2, 4,5,5,4, 6,7,7,6,6,8,8,6,7,8,8,7


then the following function works:



equivClasses[listOfPairs_]:=listOfPairs//GatherBy[#, First]&//Map[Fold[Union], #, 1]&// Union


However, this function fails when the reverse of each pair doesn't necessarily appear, e.g., equivClasses[ex1]=1,2,3,2,3,.... We can manufacture such a new list easily, e.g., by



newList=(Sort/@ex1)~Join~(ReverseSort/@ex1)//Union


and then calling equivClasses as before.



Q1 Is the above function equivClasses reasonable? It feels a bit kludgy to me, in particular insofar as the code creates $n$-copies of each sublist of length $n$ before Union-ing them away.



Q2 The scope in which this problem has arisen is somewhat large and computationally expensive. The list of pairs that I can generate contains ~10^5 pairs of integers and takes ~10min if I only generate the pairs i,j with i < j. I can certainly do the Sort...~Join~ReverseSort business, this seems a bit inefficient insofar as it doubles the memory usage (although this step does run reasonably fast, about 0.005sec on my machine). How can I optimize this code?



Q3 Particularly problematic is the case when the list of pairs doesn't include all pairwise comparisons, e.g., 1,2,2,3 which should still get sorted into 1,2,3. What can I do in this case?






list-manipulation performance-tuning




list-manipulation performance-tuning






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 58 mins ago









erfink

289110




289110







  • 1




    closely related: Using Gather to rearrange my data, Computing the equivalence classes of the symmetric transitive closure of a relation
    – kglr
    27 mins ago












  • 1




    closely related: Using Gather to rearrange my data, Computing the equivalence classes of the symmetric transitive closure of a relation
    – kglr
    27 mins ago







1




1




closely related: Using Gather to rearrange my data, Computing the equivalence classes of the symmetric transitive closure of a relation
– kglr
27 mins ago




closely related: Using Gather to rearrange my data, Computing the equivalence classes of the symmetric transitive closure of a relation
– kglr
27 mins ago










3 Answers
3






active

oldest

votes

















up vote
5
down vote



accepted










ConnectedComponents[Graph[ex1]] would be easier.






share|improve this answer




















  • Really a cool solution!
    – mgamer
    49 mins ago










  • @mgamer Thank you. =D
    – Henrik Schumacher
    37 mins ago










  • Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
    – erfink
    28 mins ago










  • You're welcome!
    – Henrik Schumacher
    22 mins ago

















up vote
5
down vote













ConnectedComponents[ex1]



6, 7, 8, 1, 2, 3, 4, 5







share|improve this answer
















  • 1




    ... this more convenient form seems to be undocumented.
    – kglr
    21 mins ago

















up vote
1
down vote













Union @@@ Gather[ex1, IntersectingQ]



1, 2, 3, 4, 5, 6, 7, 8







share|improve this answer






















  • Seems to fail for 1,2,2,3,3,4 ?
    – erfink
    1 min ago










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f183060%2fcreate-lists-of-equivalences-from-pairs%23new-answer', 'question_page');

);

Post as a guest

















3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
5
down vote



accepted










ConnectedComponents[Graph[ex1]] would be easier.






share|improve this answer




















  • Really a cool solution!
    – mgamer
    49 mins ago










  • @mgamer Thank you. =D
    – Henrik Schumacher
    37 mins ago










  • Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
    – erfink
    28 mins ago










  • You're welcome!
    – Henrik Schumacher
    22 mins ago














up vote
5
down vote



accepted










ConnectedComponents[Graph[ex1]] would be easier.






share|improve this answer




















  • Really a cool solution!
    – mgamer
    49 mins ago










  • @mgamer Thank you. =D
    – Henrik Schumacher
    37 mins ago










  • Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
    – erfink
    28 mins ago










  • You're welcome!
    – Henrik Schumacher
    22 mins ago












up vote
5
down vote



accepted







up vote
5
down vote



accepted






ConnectedComponents[Graph[ex1]] would be easier.






share|improve this answer












ConnectedComponents[Graph[ex1]] would be easier.







share|improve this answer












share|improve this answer



share|improve this answer










answered 56 mins ago









Henrik Schumacher

40.6k256121




40.6k256121











  • Really a cool solution!
    – mgamer
    49 mins ago










  • @mgamer Thank you. =D
    – Henrik Schumacher
    37 mins ago










  • Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
    – erfink
    28 mins ago










  • You're welcome!
    – Henrik Schumacher
    22 mins ago
















  • Really a cool solution!
    – mgamer
    49 mins ago










  • @mgamer Thank you. =D
    – Henrik Schumacher
    37 mins ago










  • Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
    – erfink
    28 mins ago










  • You're welcome!
    – Henrik Schumacher
    22 mins ago















Really a cool solution!
– mgamer
49 mins ago




Really a cool solution!
– mgamer
49 mins ago












@mgamer Thank you. =D
– Henrik Schumacher
37 mins ago




@mgamer Thank you. =D
– Henrik Schumacher
37 mins ago












Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
– erfink
28 mins ago




Hah! That's super slick. Especially since this is happening in a graph theoretic context (construction of a Fischer cover). Thank you!
– erfink
28 mins ago












You're welcome!
– Henrik Schumacher
22 mins ago




You're welcome!
– Henrik Schumacher
22 mins ago










up vote
5
down vote













ConnectedComponents[ex1]



6, 7, 8, 1, 2, 3, 4, 5







share|improve this answer
















  • 1




    ... this more convenient form seems to be undocumented.
    – kglr
    21 mins ago














up vote
5
down vote













ConnectedComponents[ex1]



6, 7, 8, 1, 2, 3, 4, 5







share|improve this answer
















  • 1




    ... this more convenient form seems to be undocumented.
    – kglr
    21 mins ago












up vote
5
down vote










up vote
5
down vote









ConnectedComponents[ex1]



6, 7, 8, 1, 2, 3, 4, 5







share|improve this answer












ConnectedComponents[ex1]



6, 7, 8, 1, 2, 3, 4, 5








share|improve this answer












share|improve this answer



share|improve this answer










answered 25 mins ago









kglr

163k8188387




163k8188387







  • 1




    ... this more convenient form seems to be undocumented.
    – kglr
    21 mins ago












  • 1




    ... this more convenient form seems to be undocumented.
    – kglr
    21 mins ago







1




1




... this more convenient form seems to be undocumented.
– kglr
21 mins ago




... this more convenient form seems to be undocumented.
– kglr
21 mins ago










up vote
1
down vote













Union @@@ Gather[ex1, IntersectingQ]



1, 2, 3, 4, 5, 6, 7, 8







share|improve this answer






















  • Seems to fail for 1,2,2,3,3,4 ?
    – erfink
    1 min ago














up vote
1
down vote













Union @@@ Gather[ex1, IntersectingQ]



1, 2, 3, 4, 5, 6, 7, 8







share|improve this answer






















  • Seems to fail for 1,2,2,3,3,4 ?
    – erfink
    1 min ago












up vote
1
down vote










up vote
1
down vote









Union @@@ Gather[ex1, IntersectingQ]



1, 2, 3, 4, 5, 6, 7, 8







share|improve this answer














Union @@@ Gather[ex1, IntersectingQ]



1, 2, 3, 4, 5, 6, 7, 8








share|improve this answer














share|improve this answer



share|improve this answer








edited 5 mins ago

























answered 13 mins ago









C. E.

47.8k391193




47.8k391193











  • Seems to fail for 1,2,2,3,3,4 ?
    – erfink
    1 min ago
















  • Seems to fail for 1,2,2,3,3,4 ?
    – erfink
    1 min ago















Seems to fail for 1,2,2,3,3,4 ?
– erfink
1 min ago




Seems to fail for 1,2,2,3,3,4 ?
– erfink
1 min ago

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f183060%2fcreate-lists-of-equivalences-from-pairs%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
Read more

Installing NextGIS Connect into QGIS 3?

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 1 down vote favorite Just acquired free version of NEXTGIS and trying to install the plugin for QGIS. It tells me it was not designed for version 3 of QGIS. How do I set up the QGIS-NEXTGIS interface then? qgis qgis-plugins nextgis share | improve this question edited 3 hours ago PolyGeo ♦ 51.9k 17 77 233 asked 4 hours ago IanGS 16 4 New contributor IanGS is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. add a comment  |  up vote 1 down vote favorite Just acquired free version of NEXTGIS and trying to install the plugin for QGIS. It tells me it was not designed for version 3 of QGIS. How do I set up the QGIS-NEXTGIS interface then? qgis qgis-plugin...
Read more

One-line joke

A one-liner is a joke that is delivered in a single line. A good one-liner is said to be pithy - concise and meaningful. [1] Comedians and actors use this comedic method as part of their act, e.g. Jimmy Carr, Tommy Cooper, Rodney Dangerfield, Norm Macdonald, Ken Dodd, Stewart Francis, Zach Galifianakis, Mitch Hedberg, Anthony Jeselnik, Milton Jones, Shappi Khorsandi, Jay London, Mark Linn-Baker, Demetri Martin, Groucho Marx, Dan Mintz, Emo Philips, Tim Vine, Steven Wright and Henny Youngman and Arnold Schwarzenegger. [ citation needed ] Many fictional characters are also known to deliver one-liners, including James Bond, who usually includes pithy and laconic quips after disposing of a villain. [ citation needed ] Examples "A baby seal walks into a club." "A dyslexic man walks into a bra." (Anonymous) "There are three types of people, those who can count and those who can't." "Venison's dear, isn't it?" (Jimmy Carr) "An escala...
Read more