G'day remiah,

I wasn't entirely certain how @key_array factored into your sets: they're clearly not pairs (as per the title); however, they are included in the output you show. That led me to thinking whether you're really dealing with just pairs or if that was meant as a simplified example. Anyway, the following code should handle whatever you intended.

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{first};

my @key_array = 'a' .. 'i';
my @set_array = ( ['a', 'b'],  ['e','f'], ['f','g'] );
my %sets;

for my $set_ref (@set_array, map {[$_]} @key_array) {
    my $key = first { exists $sets{item}{$_} } @$set_ref; 
    my $set_data = defined $key
                 ? $sets{item}{$key}
                 : do { push @{$sets{data}}, {}; $sets{data}[-1] };

    for my $item (@$set_ref) {
        $sets{item}{$item} = $set_data unless exists $sets{item}{$item
+};
        ++$set_data->{$item};
    }
}

for (sort { @$b <=> @$a } map { [ sort keys %$_ ] } @{$sets{data}}) {
    print join ',' => @$_;
}
[download]

Output:

e,f,g
a,b
c
d
h
i
[download]

So, all the sets are in the @{$sets{data}} array. Each element is a hash. Each hash has the items of the set as its keys and a count of those items as the values. I wasn't sure if you wanted a count (some of your commented out code indicated you might); the code above hasn't used the value: ignore it if you don't need it.

$sets{data} looks like this:

[
    { a => 2, b => 2 },
    { e => 2, f => 3, g => 2 },
    { c => 1 },
    { d => 1 },
    { h => 1 },
    { i => 1 },
]
[download]

Individual items are the keys of the %{$sets{item}} hash; the values are references to the elements in the @{$sets{data}} array.

$sets{item} looks like this:

{
    a => $sets{data}[0],
    b => $sets{data}[0],
    c => $sets{data}[2],
    d => $sets{data}[3],
    e => $sets{data}[1],
    f => $sets{data}[1],
    g => $sets{data}[1],
    h => $sets{data}[4],
    i => $sets{data}[5],
}
[download]

As you can see, 'a' and 'b' point to a single set; 'c' and 'd' point to two different sets; 'e', 'f' and 'g' point to a single set, and so on.

You were also asking about sorting. I've sorted the sets by the number of elements to get the largest sets first (descending, numerical):

sort { @$b <=> @$a }
[download]

I've also sorted the items within each set (ascending, string):

sort keys %$_
[download]

You should note that the data you provided as input was inherently sorted (i.e. 'a' .. 'z' and the set pairs). If your real input is unordered, and you want sets of the same size to be ordered, you'll need an additional sort.

Hello kcott
I could get really deep responses with this thread.

I didn't notice that this is graph, until LanX said that, and your item and data are "adjacency list" with reference + count information. "item" is vertex which has reference to edge information,and "data" is edge data storage.

Your usage of reference: reference from "item" to "data" seems to me an essence I would like to use by myself...

I would like to have some more time to stick around this code, and thanks for your kind explanation.

regards

It's a classical problem from graph theory.

Your pairs are edges and you wanna determine connectivity resp. connected components.

Don't know if the other posters are aware of edge cases (your example data is too simple to show them).

But there are already efficient (and proven) algorithms available!

Hello LanX ! and oh my god !!!

#!/usr/bin/perl
use Graph::Undirected;
use strict; use warnings;
my $g = Graph::Undirected->new;
my @key_array = 'a' .. 'z';
my @set_array = ( ['a', 'b'],  ['e','f'], ['f','g'] );

$g->add_vertex( $_ ) for @key_array;
$g->add_edge( $_->[0], $_->[1] ) for @set_array;

print "$_\n" for  
    sort { length($b) <=> length($a) || $a cmp $b }
    map {join( ',',  @$_) } 
    $g->connected_components;
[download]

I totally forgot about Graph module until you tell me.
I would like to read your pages you gave me.

Really thanks for your reply.

Plz note thiss should also work with sets which are bigger than just pairs.

use strict;
use warnings;
use Data::Dump qw/pp/;

my @key_array = 'a' .. 'z';
my @set_array = ( ['a', 'b'],  ['e','f'], ['f','g'] );

my (%neighbors,%group,%mark);

# collect all neighbors per vertex
for my $pair (@set_array) {
  for my $vert (@$pair){
    push @{$neighbors{$vert}},@$pair;
  }
}

#pp \%neighbors;


# mark all connected vertices with same group-id
my $group=1;
for my $vert (@key_array) {
  mark($vert,$group++);
}

#pp "group",\%group,"mark",\%mark;

# sort result by size and alphabetically
pp sort {@$b<=>@$a or $a->[0] cmp $b->[0]} values %group;

sub mark {
  # recursivly (deep) mark neighbors
  my ($vert,$group)=@_;
  return if $mark{$vert};
  
  $mark{$vert}=$group;
  push @{$group{$group}},$vert;

  for my $neighbor (@{$neighbors{$vert}}) {
    mark($neighbor,$group)
  }
}
[download]

output:

(
  ["e", "f", "g"],
  ["a", "b"],
  ["c"],
  ["d"],
  ["h"],
  ["i"],
  ["j"],
  ["k"],
  ["l"],
  ["m"],
  ["n"],
  ["o"],
  ["p"],
  ["q"],
  ["r"],
  ["s"],
  ["t"],
  ["u"],
  ["v"],
  ["w"],
  ["x"],
  ["y"],
  ["z"],
)
[download]

Another way:

my @key_array = 'a' .. 'z';
my @set_array = ( ['a', 'b'],  ['e','f'], ['f','g'] );

my %set = map {$_ => {$_ => 1}} @key_array;

for my $s (@set_array) {
    @{$set{$_}}{@$s} = (1) x @$s for @$s;
}

my $saw = '';

print map "$_\n",
      grep $saw =~ s/^(?!.*$_)/$_ /,
      sort {length $b <=> length $a || $a cmp $b}
      map join(',', sort keys %$_),
      values %set;
[download]

Hello, thanks for reply.
It took me some time to understand this.

#!usr/bin/perl
use strict; use warnings; use Data::Dumper;

my @key_array = 'a' .. 'z';
my @set_array = ( ['a', 'b'],  ['e','f'], ['f','g'],['x','y'] );

# {a =>{a=>1}, b=>{b=>1}, ....}
my %set = map {$_ => {$_ => 't'}} @key_array;  

for my $s (@set_array) {
    @{$set{$_}}{@$s} = (1) x @$s for @$s;    
=my_memo    
    #same as ...
    for (@$s){
              @{$set{$_}}{@$s} = (1) x @$s 
    }
    #fill hash value at one time
    my %h; @h{ 1 .. 5 }= 'A' ..'F';  
    
    #(1) x @$s 
    if @$s === (a,b) ,  (1) x @$s === (1,1) 
     
    #vertex which has edge information ..
    #{ a=>{a=>1,b=>1}, b=>{a=>1,b=>1} ...
=cut 
}

my $saw = '';

print map "$_\n",                                    
      grep $saw =~ s/^(?!.*$_)/$_ /,                
=my_memo
     # ??? how it can remove duplicate like "a,b","a,b" or "e,f,g","e,
+f","f,g"
    
     here comes "e,f,g", $saw='',         ==> $saw="e,f,g"        ==> 
+true  #saw doesn't have "" replace ^ to "e,f,g"
                "a,b"    $saw="e,f,g"     ==> $saw="a,be,f,g"     ==> 
+true  #saw doesn't have "a,b", replace ^ to "a,b
                "a,b"    $saw="a,be,f,g"     ==> $saw="a,be,f,g"     =
+=> false #saw have "a,b" not match;
                "e,f"    $saw="a,be,f,g"     ==> $saw="a,be,f,g"     =
+=> false #saw have "e,f" not match;
      ... removes edge already seen ... really great.
=cut
      sort {length $b <=> length $a || $a cmp $b}      #sort by length
+ desc || a cmp b
      map join(',', sort keys %$_),                    #"a,b" ... sort
+ed  
      values %set;                                     # values => {a=
+>1,b=>1}, {a=>1,b=>1},{c=>1},{d=>1},,,
[download]

short and great!