results from pairs combination

[lipong]

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.

[jdporter]

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;

[JadeNB]

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.

[jdporter]

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.

[moritz]

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.

[lipong]

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.

[suaveant]

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).

[moritz]

Did the original post get updated?

Yes.

[Animator]

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.

Read more... (2 kB)

[lipong]

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

[Animator]

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 learn more;
• 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.

[AnomalousMonk]

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...
Read more... (1200 Bytes)