intermix list of items

[tstock]

weekend monks...

I have a list of IP addresses in dot decimal format, a class A RFC 1918 internal addresses (10.0.0.0/8). I would like to scan these IP's for a service, but instead of doing it sequentially (10.0.0.1, 10.0.0.2, ...) I would like to intermix different class C's as much as possible. What I first tried did not work:

my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2');
@list = sort intermix @list;

sub intermix
{ 
    return (
        substr( $a, 0, rindex($a, '.'))
        eq 
        substr( $b, 0, rindex($b, '.'))
        )
    ? 1 : 0;
}

Randomizing the list would be one way sort of around the sequential problem, but not as neat as what I was looking for. The reason behind the requirement is to avoid hitting limits and easy the load on individual routers/switches for each segment. Any nice perl idioms to solve this problem?

Tiago

[ikegami]

btw, the compare function is suppose to return -1, 0, +1, not just 0 and 1, so I expect your sort has some amount of randomness to it.

Maybe you want something like:

sub intermix { 
   my $a_prime = join('.', reverse(split(/\./, $a)));
   my $b_prime = join('.', reverse(split(/\./, $b)));
   $a_prime cmp $b_prime
}

my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2');
@list = sort intermix @list;

use Data::Dumper;
print Dumper(@list);

__END__
output
======
$VAR1 = '10.1.1.1';
$VAR2 = '10.2.2.1';
$VAR3 = '10.1.1.2';
$VAR4 = '10.2.2.2';

Almost the same, but more efficient:

sub intermix { 
   my $a_prime = reverse($a);
   my $b_prime = reverse($b);
   $a_prime cmp $b_prime
}

my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2');
@list = sort intermix @list;

use Data::Dumper;
print Dumper(@list);

__END__
output
======
$VAR1 = '10.1.1.1';
$VAR2 = '10.2.2.1';
$VAR3 = '10.1.1.2';
$VAR4 = '10.2.2.2';

This is the same thing as the last, but probably more efficient, especially for longer lists:

my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2');
@list = map { $_->[0] } 
        sort { $a->[1] cmp $b->[1] }
        map { [ $_, ''.reverse($_) ] } 
        @list;

use Data::Dumper;
print Dumper(@list);

__END__
output
======
$VAR1 = '10.1.1.1';
$VAR2 = '10.2.2.1';
$VAR3 = '10.1.1.2';
$VAR4 = '10.2.2.2';

Note: Given addresses of the form 'a.b.c.d', the above snippets only work well if there is there is a common 'd' of for every 'a.b.c' in the list.

[ikegami]

Here's an algorithm that doesn't suffer from the problem mentioned in the Note above:

my @list = ('10.1.1.[1..2]', '10.2.2.[1..2]', '10.3.3.[3..6]');

my @list_prime = 
   map {
      my $n = $_;
      $n =~ s/\[(\d+)\.\.(\d+)\]//;
      [ $n, $1, $2 ]
   } @list;

my @ordered_list;

my $done;
do {
   $done = 1;
   foreach (@list_prime) {
      next unless defined($_);
      if ($_->[1] > $_->[2]) { undef($_); next }
      push(@ordered_list, $_->[0].($_->[1]++));
      $done = 0;
   }
} while (!$done);


use Data::Dumper;
print Dumper(@ordered_list);

__END__
output
======
$VAR1 = '10.1.1.1';  # First  from first.
$VAR2 = '10.2.2.1';  # First  from second.
$VAR3 = '10.3.3.3';  # First  from third.
$VAR4 = '10.1.1.2';  # Second from first.
$VAR5 = '10.2.2.2';  # Second from second.
$VAR6 = '10.3.3.4';  # Second from third.
$VAR7 = '10.3.3.5';  # Third  from third.
$VAR8 = '10.3.3.6';  # Fourth from third.

It can probably be optimised.

[davido]

Since you have the @list of all IP's in your hand at once, wouldn't it be adequate to just perform a Fisher-Yates Shuffle on them?

If the goal is simply to not have sequential IP's, and if instead, random order is sufficient, the Fisher Yates shuffle might work great.

[pg]

That eq definitely does not make sense. I can guess what was in your mind, you probably thought that by using 'eq', sort will group elements for you base on how common they are. No, that is not what sort does. You have to tell sort "between each pair of two elements, how they shall be ordered".

You are looking for something like:

use Data::Dumper;

my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2');
@list = sort intermix @list;
print Dumper(@list);

sub intermix
{ 
    return (
        substr( $a, 0, rindex($a, '.'))
        gt 
        substr( $b, 0, rindex($b, '.'))
        )
    ? 1 : 0;
}

[tstock]

'gt' refers to the size of the string, running your example solution didn't seem to help. I was going for (and failed) non-equality of the substring means they are identical in sort order by using 'eq'.

[pg]

"'gt' refers to the size of the string"

No. In your code, gt looks at "dictionary sequence".

If string size/length is what you wanted, say length($str) expliciltly.

use Data::Dumper;

my @foo = ("abc", "bc");
print Dumper(sort bar1 @foo);
print Dumper(sort bar2 @foo);

sub bar1 {
    return $a gt $b;
}

sub bar2 {
    return length($a) gt length($b);
}

[pg]

sub intermix
{ 
    return (
        substr( $a, 0, rindex($a, '.'))
        eq 
        substr( $b, 0, rindex($b, '.'))
        )
    ? 1 : 0;
}

The use of ?: is not necessary:

sub intermix
{ 
    return (
        substr( $a, 0, rindex($a, '.'))
        eq 
        substr( $b, 0, rindex($b, '.'))
        );
#    ? 1 : 0;
}

[tstock]

thanks all. I went with the following based on your feedback -

use strict;
my @targets = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2');

my @list = intermix( @targets );

use Data::Dumper;
print Dumper \@list;

sub intermix
{
    my @list = @_;

    my %hash; # separating hash
    my @ret;  # returning list

    # build hash structure, each similar first 3 octects as key
    # array reference w/ IP addresses as values
    for (@list) {
        push( @{ $hash{ substr($_,0,rindex($_,'.'))  } }, $_ );
    }
    
    my @keys = keys %hash;
    while (@keys)
    {
        push(@keys, shift(@keys)); # rotate keys

        # extract one element, or delete the array ref and try again
        my $item = shift @{$hash{ $keys[0] }} || shift @keys && next;

        push @ret, $item;
    }

    return @ret;
}

__END__

$VAR1 = [
          '10.1.1.1',
          '10.2.2.1',
          '10.1.1.2',
          '10.2.2.2'
        ];

This doesn't require a specially defined sequential list type. I'm sorry it doesn't look small and neat though.

Tiago