Welcome to the Monastery PerlMonks

### results from pairs combination

by lipong (Initiate)
 on Oct 01, 2008 at 17:03 UTC Need Help??

lipong has asked for the wisdom of the Perl Monks concerning the following question:

Hi Could someone please help me solve the following situation: I have an array with the following pairs: @pairs = ("1,7","2,6","2,7","5,4","6,7"); I would like to be able to have the following results: "1,7","2,6","2,7","6,7" This result because 1,7 overlap with 2,7 and 6,7 but also because the 6,7 joined the group also the 2,6 must be included. The only pair that does not have nay overlap is "5,4" and should be put in a different group. Thank you very much. Any help would be much appreciated. Thank you very much.

Replies are listed 'Best First'.
Re: results from pairs combination
by jdporter (Chancellor) on Oct 01, 2008 at 17:41 UTC

You are looking for connected subgraphs. Use the Graph module.

use Graph; my @pairs=("a,b","c,b","d,f","e,b","f,g"); my \$g = new Graph; for ( @pairs ) { my(\$x,\$y) = split /,/; \$g->add_edge(\$x,\$y); } my @subgraphs = \$g->weakly_connected_components; for my \$subgraph ( @subgraphs ) { print "\nA subgraph:\n"; for my \$v ( @\$subgraph ) { my @s = \$g->successors(\$v); print " \$v-\$_\n" for @s; } }
Or:
use Graph; use Data::Dumper; use strict; use warnings; my @pairs = qw( a,b c,b d,f e,b f,g ); my \$g = new Graph edges => [ map [ split /,/ ], @pairs ]; my @av = map [ map { my \$v = \$_; map [\$v,\$_], \$g->successors(\$v) } @\$_ + ], \$g->weakly_connected_components; print Dumper @av;
Between the mind which plans and the hands which build, there must be a mediator... and this mediator must be the heart.
An equivalent way of looking at this is that the poster wants the transitive closure of a relation (or graph). Thus, Graph::TransitiveClosure (which is a submodule of Graph—if that terminology makes sense—and is probably what it calls to find (weakly) connected components anyway) or Algorithms::Graphs::TransitiveClosure are also suitable, and may suggest more directly what's going on.

(Of course, having to call weakly_connected_components instead of the probably more natural connected_components is an artifact of working with directed graphs, which could be avoided by getting a new Graph::Undirected instead.)

UPDATE: Directed graphs, not graphics.

a submodule of Graph—if that terminology makes sense

In some languages, but [un]fortunately not in Perl.

an artifact of working with directed graphics

One method name is as good as another. I originally sought to solve this using undirected graphs, but switched because it looks (lacking any other information) that the input graph is directed. If you treat the graph as undirected, then you might have b,a in the output when the input edge was a,b, and I'd rather have not made the assumption that that would be valid.

What lacks in both methods is a way to get the result in terms of edges rather than vertices. This forced me to do a bit more work to retrieve the relevant original edges from the vertices returned.

Between the mind which plans and the hands which build, there must be a mediator... and this mediator must be the heart.
Re: results from pairs combination
by moritz (Cardinal) on Oct 01, 2008 at 17:05 UTC

Update: original posting changed massively in the mean time, so this is kinda out of context. In case of doubt just ignore it.

Do you always want to change the order of the last two elements? If yes

@pairs[-1, -2] = @pairs[-2, -1];

should work for you.

Thanks for the quick reply The idea is not the order but each pair represents the relations between the elements so for example: @pairs=("a,b","c,b","d,f","e,b","f,g"); The results should be: "a,b","c,b","e,b" "d,f","f,g"; But the pairs can appear in any order and combination.
Re: results from pairs combination
by suaveant (Parson) on Oct 01, 2008 at 17:33 UTC
Update Never mind, all wrong. Did the original post get updated?

So you want a sort? Ok.

@sorted_pairs = sort { my@a1 = split',',\$a; my@b1 = split',',\$b; \$a1[0 +] <=> \$b1[0] || \$a1[1] <=> \$b1[1] } @pairs;
The first match returns 0 for a match, so it falls through to the second comparison for things like 2,6 2,7

You need to split the values, otherwise 10,1 would sort before a pair like 2,6, and just using numeric sorting breaks at the comma. It would be even better to split the values ahead of time, but probably not necessary. (You could always use a Schwarzian Transform).

- Ant
- Some of my best work - (1 2 3)

Did the original post get updated?
Yes.
Re: results from pairs combination
by Animator (Hermit) on Oct 01, 2008 at 18:00 UTC

Given that it seemed like an intresting problem I opted for re-inventing the wheel and not using Graph. See the readmore for the code.

Do note that the best solution is to use Graph since it went trough more testing and might be optimized. The code in the readmore is only provided as a learning-exercice on how to do it yourself.

Hi Thank you very much for the solution. I have try it and it works very well could I just ask you if could please comment the code a bit more so that I can understand each step. Thank you very much. Luis

I suggest you try documenting it yourself.

Some advice on how/where to start:

• Come up with an alogirthm to be used: take a piece of paper and try to solve the problem yourself. Go over each pair and make a note on how you decide in which group to put that pair;
• Post your algorithm here (in English);
• Try to turn your algorithm into code;
• Test the code;
• Post the code;
• Look back at the code I posted and see if you can understand what I wrote and why I wrote it. If question ask.;

I suggest this for the following reasons:

• It should be more rewarding;
• You will remember what you learned a lot longer;

The obvious downside is that it will take your more time to figure it out. If I document it/explain it then you know how to solve this particular problem but you might not be able to solve another, similar, problem since you might not see the alogirthm and/or forgot on how this problem was solved.

Re: results from pairs combination
by AnomalousMonk (Archbishop) on Oct 02, 2008 at 00:27 UTC
Also a re-invention of the wheel and thus inferior to Graph and its ilk (and also lacking the directed-ness, if I correctly understand that term, of jdporter's solution), but perhaps more terse...

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://714844]
Approved by toolic
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (8)
As of 2024-03-01 10:15 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (28 votes). Check out past polls.