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

Long meetings (6-7 hours a day): Being “babysat” by supervisor

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 31 down vote favorite 4 I hold a PhD in mechanical engineering with a 7 year background in self-guided, self-paced research including 2 years as a graduate level course instructor and a subject matter expert for various engineering projects in a university setting in the United States. For the last 10-11 months, I am working in a research industry in France where my task is to debug C++ spaghetti code written over a period of several years by my current supervisor. It is a team of 2: just I and my supervisor. Diurnally, I am posed with a "bug of the day" to get out of this C++ code. My supervisor generally gives me about 15-30 minutes to solve it and then accosts me about whether or not the task is completed and then rinses and repeats this until the end of the day. Off-late, my supervisor has been holding 6-7 hour long "meetin
Read more

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite Many fantasy worlds have multiple humanoid species (elves, orcs, humans, etc) living in the same world, in addition to that, they often have the ability to interbreed. And I can't help but question their believability... fantasy-races reproduction interspecies-relations share | improve this question edited Aug 9 at 14:46 Michael Kjörling ♦ 21.1k 10 85 161 asked Aug 9 at 13:13 Chlodio 118 6 closed as unclear what you're asking by MichaelK, Gryphon, John, Vincent, Frostfyre Aug 9 at 15:25 Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question. 3 Stack Exchange exist to
Read more

Confectionery

Image
Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of
Read more