Eliminating duplicates from a list

Say, I have a list as follows

(1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5)

I want to remove duplicates from my list(without using a dictionary) i.e I want the above list transformed to

(1, 2, 3, 4, 5)

Following Perl code is designed to do exactly that

sub removeDuplicates {
  my (@points) = @_;
  my $noOfPoints = scalar(@points);

  for  (my $j = 0; $j < $noOfPoints; ++$j) {
    for (my $i = 0; $i < $noOfPoints; ++$i) {
      next if $i == $j;
      delete $points[$j] if $points[$i] == $points[$j];
    }
  }

  @points = grep {defined $_} @points;
  return @points;
}

The main thing to note here is that when you delete an element from a list, ‘undefined’ takes it’s place in the list. As far as I know, this is the best way to delete elements from a list while iterating over it, as it does not change the size of the list.

Edit:

A faster version of the for loop:

 for  (my $j = 0; $j < $noOfPoints - 1; ++$j) {
    for (my $i =  $j + 1; $i < $noOfPoints; ++$i) {
      next if $i == $j;
      delete $points[$j] if $points[$i] == $points[$j];
    }
  }

Advertisements

Code, Perl, Programming

January 29, 2009

2 Comments