CODEWITHSUNDEEP
arraysperlbranch-and-bound
Sam
Sam

Reputation: 2331

Perl deleting array elements after a few iterations of code, with a call to a sub function

My code works for the first few iterations, but after a few times through the while loop, it seems that my array elements are being deleted.

I'm taking numbers off the array constructed from the input parameters and all I can tell is that when I get to a number which was passed in twice, I get an error.

I am calling my script like this

./branchandboundNoComments.pl 1 2 3 4 5 5 7 7 9 9 10 10 12 14 19

I should get this as output

0, 7, 9, 10, 14, 19

This is my script

#!/usr/bin/perl -w 

use strict;

my @input  = @ARGV;
my $maxAll = $input[-1];
$#input = $#input - 1;
my @multiset = ( 0, $maxAll );
my @stack;

my $rotation = 0;    # this is 0,1, or 2.

while ( @input != 0 ) {

    my $max = $input[-1];

    my @deltamultiset;
    for ( my $i = 1; $i <= $#multiset; $i++ ) {
        push @deltamultiset, $multiset[$i] - $max;
    }
    push @deltamultiset, $max;

    my @deltamultiset2;
    for ( my $i = 1; $i <= $#multiset; $i++ ) {
        push @deltamultiset2, $multiset[$i] - ( $maxAll - $max );
    }
    push @deltamultiset2, $max;

    if ( subset( \@deltamultiset, \@input ) and $rotation == 0 ) {

        for ( my $i = 0; $i < $#deltamultiset; $i++ ) {
            pop @input;
        }

        push @multiset, $max;
        push @stack,    $max;
        push @stack,    0;
    }
    elsif ( subset( \@deltamultiset2, \@input ) and $rotation <= 1 ) {

        for ( my $j = 0; $j < $#deltamultiset; $j++ ) {
            pop @input;
        }

        push @multiset, ( $maxAll - $max );
        push @stack,    ( $maxAll - $max );
        push @stack, 1;
        $rotation = 0;
    }
    elsif ( @stack != 0 ) {

        $rotation = $stack[-1];
        $#stack--;
        $max = $stack[-1];
        $#stack--;
        $rotation++;

        for ( my $i = 0; $i < $#multiset; $i++ ) {
            if ( $multiset[$i] == $max ) {
                delete $multiset[$i];
                last;
            }
        }

        for ( my $i = 0; $i < $#deltamultiset; $i++ ) {
            push @input, $deltamultiset[$i];
        }
    }
    else {
        print "no solutions \n";
        exit;
    }
}

print "@multiset is a solution \n";

sub subset {
    my ( $deltamultisetSubref, $multisetSubref ) = @_;
    my @deltamultisetSub = @{$deltamultisetSubref};
    my @multisetSub      = @{$multisetSubref};

    while ( @deltamultisetSub != 0 ) {

        for ( my $i = $#multisetSub; $i >= -1; $i-- ) {

            if ( $multisetSub[$i] == $deltamultisetSub[-1] ) {
                pop @deltamultisetSub;
                $#multisetSub--;
                last;
            }

            if ( $i == -1 ) {
                return 0;
            }
        }
    }

    return 1;
}

This is what is output

Use of uninitialized value in subtraction (-) at ./branchandboundNoComments.pl line 20.
Use of uninitialized value in subtraction (-) at ./branchandboundNoComments.pl line 26.
no solutions

Upvotes: 0

Views: 104

Answers (1)

Borodin
Borodin

Reputation: 126722

I can't understand the algorithm you're trying to implement, so there are probably more errors, but the immediate problem is that the statement

delete $multiset[$i]

won't remove that element from the array unless it is the last element; otherwise the array stays the same length, exists on that element will return false, and it will evaluate to undef

If you want to remove the element, which seems most likely, then you want

splice @multiset, $i, 1;

But I have tested your code with that fix in place, and while it no longer produces Use of uninitialized value in subtraction errors, the result is still no solutions

Unfortunately I can't understand what you're trying to implement, and can't make any useful guesses about what may be wrong unless you can offer me a description of the underlying algorithm

Upvotes: 1

Related Questions