comparing 2 arrays

[Sébastien Cottalorda]

Hi all,

I have those two arrays:

@estimated = qw ( 1 3 6 7 3 1 2 4 6 9);
@arrived = qw ( 6 7 1 0 4);

I need to determine the next value that will probably come in the
@arrived array.
As you can see, I can have some "polution" in the @arrived array (with
the 0 value that should not have occured, but we need to to with that).

I need an algorithm that can give me the probably next value => 6
It smells a 2 arrays comparaison, but ...

How can I manage to do that.

Is someone have a clue ?

Thanks in advance for any kind of help.

Sebastien

 

[Anno Siegel]

Hi all,

I have those two arrays:

@estimated = qw ( 1 3 6 7 3 1 2 4 6 9);
@arrived = qw ( 6 7 1 0 4);

You have formatted @arrived so that corresponding elements appear under
their counterparts in @estimated, but without such an indication
it will be hard to establish the relation.

I need to determine the next value that will probably come in the
@arrived array.
As you can see, I can have some "polution" in the @arrived array (with
the 0 value that should not have occured, but we need to to with that).

What about the missing values in @arrived? Are there supposed to be
undefined entries in the @arrived array in their place, or are they
just missing?

I need an algorithm that can give me the probably next value => 6
It smells a 2 arrays comparaison, but ...

If you want help with the algorithm you'll have to explain the relation
of the @estimated and the @arrived arrays in more detail. All we know
now is that some elements in @arrived may or may not be equal to elements
of @estimated. That is not enough information to base an algorithm on.

How can I manage to do that.

Walking through two arrays in parallel is usually done using an index
(untested):

use Scalar::Util 'min';
for ( 0 .. min $#estimated, $#arrived ) {
# compare $estimated[ $_] with $arrived[ $_]
}

Is someone have a clue ?

Not yet. If you give us a clue what you really want to accomplish,
someone may.

Anno

 

[Sébastien Cottalorda]

Anno Siegel a écrit :
The real situation is that:
I work in the public car park of monaco (about 30 car parks).

A customer of mine, on internet, can plan a route that he want to do.
1st : Go to car park n°1
2nd : Go to car park n°3
3rd : Go to car park n°6
....
it represents @estimated array.

But when he comes in monaco, he finally decides to come first to car
park n°6, then car park n°7, then car park n°1, ... and car park n°4.
It represents @arrived array.

I need, when he want to exit a car park, to ask him if he plan to go to
the next car park n°....
In that precise case : I need to program an algorithm that give me '6'.

I smell now a recursive function.

First check the 6 (first element in @arrived) in @estimated.
Foreach position found, try to find now the 7 ...

Sebastien

 

[Anno Siegel]

Anno Siegel a écrit :

The real situation is that:
I work in the public car park of monaco (about 30 car parks).

Ugh. I asked for concretisation, but this is rather more concrete
than I expected.

A customer of mine, on internet, can plan a route that he want to do.
1st : Go to car park n°1
2nd : Go to car park n°3
3rd : Go to car park n°6
...
it represents @estimated array.

Okay. Why would he visit some of the car parks twice?

But when he comes in monaco, he finally decides to come first to car
park n°6, then car park n°7, then car park n°1, ... and car park n°4.
It represents @arrived array.

I need, when he want to exit a car park, to ask him if he plan to go to
the next car park n°....

It looks like you *don't* want to ask him...

In that precise case : I need to program an algorithm that give me '6'.

....but to predict what he'll do, though I don't see how.

So he comes in and visits car parks in a different sequence than
originally planned. In my view, that cancels the original plan.
What bearing does it still have? Is the assumption that he always
goes from park 4 to park 6? What if the last element in @arrived was
3 instead of 4? He can go to 6 or 1 from there.

I smell now a recursive function.
Why?

First check the 6 (first element in @arrived) in @estimated.
Foreach position found, try to find now the 7 ...

What does it mean to "find the 7 for a position found" and how does
that lead to the answer 6? I still don't know what you want to achieve.
Is he going to visit all the places on the plan, but in a different
order? Or has he skipped the (first) visit to 1 and both visits to 3
for good because the @arrives list doesn't begin with them?

Anno

 

[Sébastien Cottalorda]

Anno Siegel a écrit :

Ugh. I asked for concretisation, but this is rather more concrete
than I expected.

You asked for concretisation, you've got it ;-)

Okay. Why would he visit some of the car parks twice?

Why not ?

It looks like you *don't* want to ask him...

In fact, I would like to predict his new car park *according* to the
original planning.
I gave a complicate example with, I think, all possibility.
a less complicated example is :
@estimated (1 2 3 1 6 12);
@arrived (1 6);
because the customer arrived in late in monaco, he decides to make less
visit and goes to the 3 last car parks, respectively 1, 6 and ... => 12.

When he exits of the car park n°6, I *want* him to tell me if he plans
to go to car park ...12 because I need to tell him if the car park if
free or full.

The sequence he does is exactly the same as planned, but truncated.

On a more complicate example, I add some "polution" in the effective
route (@arrived) of the customer : he decides to go to car park 4 before
the n°12 because he has finally enough time to visit everything.

Why?

Let's take :

@estimated = qw ( 1 3 4 5 6 3 2 1 9);
@arrived = qw ( 3 4 6);

I think it's a good idea to construct a tree like this:
...
2 => never here
3 => never here
6 => found *6* => end of processing
5 => polution
4 => found *4*
@estimated = 1 3 => found *3*
2 => polution
1 => polution
9 => polution
End of array

going all over the tree, I find the value 3 at positions 1 and 5 of
@estimated.

I try to program such an algorithm, but it never goes in the 1 3 2 1 9
branch.


Sebastien

 

[Anno Siegel]

Anno Siegel a écrit :[...]

Okay. Why would he visit some of the car parks twice?

Why not ?

Because it makes the problem harder.

In fact, I would like to predict his new car park *according* to the
original planning.
I gave a complicate example with, I think, all possibility.
a less complicated example is :
@estimated (1 2 3 1 6 12);
@arrived (1 6);
because the customer arrived in late in monaco, he decides to make less
visit and goes to the 3 last car parks, respectively 1, 6 and ... => 12.

When he exits of the car park n°6, I *want* him to tell me if he plans
to go to car park ...12 because I need to tell him if the car park if
free or full.

Okay... There's always a possibility that the recorded arrivals match
at more than one place in the plan, so we can't expect the prediction
to be unique. Here is a sketch how to go about it:

my @estimated = qw(1 2 3 1 6 12);
my @arrived = qw( 1 6);

my @matches = grep match_at( $_, \ @arrived, \ @estimated),
0 .. $#estimated - @arrived;

my @predictions = map $estimated[ $_ + @arrived], @matches;

print "predictions: @predictions\n";

sub match_at {
my ( $i, $arr, $est) = @_;
for ( 0 .. $#$arr ) {
return 0 unless $est->[ $i + $_] == $arr->[ $_];
}
return 1;
}

In this case, the prediction is unique: 12, but it is easy to
construct examples where it isn't.

The sequence he does is exactly the same as planned, but truncated.

On a more complicate example, I add some "polution" in the effective

Let me skip that for now. If my approach above is about right, you
could modify the function match_at() to return "fuzzy" values between
0 and 1 for imperfect matches. You would then have to decide for a
limit and extract the matches like

my @matches = grep match_at( $_, \ @arrived, \ @estimated) > $limit,
0 .. $#estimated - @arrived;

I still don't see recursion looming anywhere.

Anno

 

[Sébastien Cottalorda]

Anno Siegel a écrit :

Anno Siegel a écrit :

Anno Siegel a écrit :

Sébastien Cottalorda <[email protected]> wrote in comp.lang.perl.misc:

[...]

A customer of mine, on internet, can plan a route that he want to do.
1st : Go to car park n°1
2nd : Go to car park n°3
3rd : Go to car park n°6
...
it represents @estimated array.


Okay. Why would he visit some of the car parks twice?

Why not ?

Because it makes the problem harder.

Of course, but it's the reality.

In fact, I would like to predict his new car park *according* to the
original planning.
I gave a complicate example with, I think, all possibility.
a less complicated example is :
@estimated (1 2 3 1 6 12);
@arrived (1 6);
because the customer arrived in late in monaco, he decides to make less
visit and goes to the 3 last car parks, respectively 1, 6 and ... => 12.

When he exits of the car park n°6, I *want* him to tell me if he plans
to go to car park ...12 because I need to tell him if the car park if
free or full.

Okay... There's always a possibility that the recorded arrivals match
at more than one place in the plan, so we can't expect the prediction
to be unique. Here is a sketch how to go about it:

my @estimated = qw(1 2 3 1 6 12);
my @arrived = qw( 1 6);

my @matches = grep match_at( $_, \ @arrived, \ @estimated),
0 .. $#estimated - @arrived;

my @predictions = map $estimated[ $_ + @arrived], @matches;

print "predictions: @predictions\n";

sub match_at {
my ( $i, $arr, $est) = @_;
for ( 0 .. $#$arr ) {
return 0 unless $est->[ $i + $_] == $arr->[ $_];
}
return 1;
}

In this case, the prediction is unique: 12, but it is easy to
construct examples where it isn't.

The sequence he does is exactly the same as planned, but truncated.

On a more complicate example, I add some "polution" in the effective

Let me skip that for now. If my approach above is about right, you
could modify the function match_at() to return "fuzzy" values between
0 and 1 for imperfect matches. You would then have to decide for a
limit and extract the matches like

my @matches = grep match_at( $_, \ @arrived, \ @estimated) > $limit,
0 .. $#estimated - @arrived;

I still don't see recursion looming anywhere.

Anno

In a recursive way I see:

1st path:
1-> 0st element of @estimated
6-> 6th element of @estimated
==> next car parc = 7th element of @estimated ==> "12"
2nd path:
1-> 3rd element of @estimated
6-> 6th element of @estimated
==> next car parc = 7th element of @estimated ==> "12"

I've 2 differents ways, both gives car parc 12 as a result .




I'm impressed by your code.

I've checked that couple with your program:
my @estimated = qw(1 2 3 1 6 5 7 0 9);
my @arrived = qw(1 6 5 0);
but it doesn't predicate anything.

Normaly it should predicate 9.

Sebastien

 

[Mark Clements]

Hi all,

I have those two arrays:

@estimated = qw ( 1 3 6 7 3 1 2 4 6 9);
@arrived = qw ( 6 7 1 0 4);

I need to determine the next value that will probably come in the
@arrived array.
As you can see, I can have some "polution" in the @arrived array (with
the 0 value that should not have occured, but we need to to with that).

I need an algorithm that can give me the probably next value => 6
It smells a 2 arrays comparaison, but ...

How can I manage to do that.

Is someone have a clue ?

Thanks in advance for any kind of help.

Sebastien

<ignoring ongoing discussion>

Have you considered something like looking at

AI::NeuralNet::Simple

or some of the

AI::Fuzzy

hierarchy?

I may be way off the mark here, but it occurred to me that these are a
possible match for your problem domain.

Mark

 

[Anno Siegel]

Anno Siegel a écrit :

Anno Siegel a écrit :
Anno Siegel a écrit :

[...]


A customer of mine, on internet, can plan a route that he want to do.
1st : Go to car park n°1
2nd : Go to car park n°3
3rd : Go to car park n°6
...
it represents @estimated array.

[...]

But when he comes in monaco, he finally decides to come first to car
park n°6, then car park n°7, then car park n°1, ... and car park n°4.
It represents @arrived array.

I need, when he want to exit a car park, to ask him if he plan to go to
the next car park n°....


It looks like you *don't* want to ask him...

In fact, I would like to predict his new car park *according* to the
original planning.
I gave a complicate example with, I think, all possibility.
a less complicated example is :
@estimated (1 2 3 1 6 12);
@arrived (1 6);
because the customer arrived in late in monaco, he decides to make less
visit and goes to the 3 last car parks, respectively 1, 6 and ... => 12.

When he exits of the car park n°6, I *want* him to tell me if he plans
to go to car park ...12 because I need to tell him if the car park if
free or full.

Okay... There's always a possibility that the recorded arrivals match
at more than one place in the plan, so we can't expect the prediction
to be unique. Here is a sketch how to go about it:

my @estimated = qw(1 2 3 1 6 12);
my @arrived = qw( 1 6);

my @matches = grep match_at( $_, \ @arrived, \ @estimated),
0 .. $#estimated - @arrived;

my @predictions = map $estimated[ $_ + @arrived], @matches;

print "predictions: @predictions\n";

sub match_at {
my ( $i, $arr, $est) = @_;
for ( 0 .. $#$arr ) {
return 0 unless $est->[ $i + $_] == $arr->[ $_];
}
return 1;
}

In this case, the prediction is unique: 12, but it is easy to
construct examples where it isn't.

The sequence he does is exactly the same as planned, but truncated.

On a more complicate example, I add some "polution" in the effective

Let me skip that for now. If my approach above is about right, you
could modify the function match_at() to return "fuzzy" values between
0 and 1 for imperfect matches. You would then have to decide for a
limit and extract the matches like

my @matches = grep match_at( $_, \ @arrived, \ @estimated) > $limit,
0 .. $#estimated - @arrived;

I still don't see recursion looming anywhere.

Anno

In a recursive way I see:

1st path:
1-> 0st element of @estimated
6-> 6th element of @estimated 4th
==> next car parc = 7th element of @estimated ==> "12" 5th
2nd path:
1-> 3rd element of @estimated
6-> 6th element of @estimated 4th
==> next car parc = 7th element of @estimated ==> "12" 5th

I've 2 differents ways, both gives car parc 12 as a result .

Ugh. A diagram with two kinds of arrows, none of which is explained.

All I can see from it is that you arrive at 12 because 6 precedes it,
but in fact the second "path" is a much better match because it has
two consecutive matches at 3 and 4. How would a recursive routine
make use of that?

Mind you, I'm sure you can come up with a recursive function to solve
this (you almost always can). The big question about recursion is
when *not* to use it (it is inefficient and usually harder to understand
than a non-recursive solution). I don't see how your problem naturally
splits off a smaller partial problem that can be solved in the same way.
That is the usual indicator for a recursive approach.

I'm impressed by your code.

I've checked that couple with your program:
my @estimated = qw(1 2 3 1 6 5 7 0 9);
my @arrived = qw(1 6 5 0);
but it doesn't predicate anything.

No, it wouldn't. As I said, the code doesn't deal with errors in the
data. It needs a perfect match anywhere in the @estimated array to
make a prediction.

Normaly it should predicate 9.

On what ground? You seem to assume he skipped 7. If he swapped
0 and 7, the prediction would have to be 7. You need to define
an (idealized) behavior of your client to make predictions about it.
So far your haven't done that.

Anno

 

[Sébastien Cottalorda]

Anno Siegel a écrit :

Anno Siegel a écrit :

Anno Siegel a écrit :


Anno Siegel a écrit :



[...]



A customer of mine, on internet, can plan a route that he want to do.
1st : Go to car park n°1
2nd : Go to car park n°3
3rd : Go to car park n°6
...
it represents @estimated array.

[...]

But when he comes in monaco, he finally decides to come first to car
park n°6, then car park n°7, then car park n°1, ... and car park n°4.
It represents @arrived array.

I need, when he want to exit a car park, to ask him if he plan to go to
the next car park n°....


It looks like you *don't* want to ask him...

In fact, I would like to predict his new car park *according* to the
original planning.
I gave a complicate example with, I think, all possibility.
a less complicated example is :
@estimated (1 2 3 1 6 12);
@arrived (1 6);
because the customer arrived in late in monaco, he decides to make less
visit and goes to the 3 last car parks, respectively 1, 6 and ... => 12.

When he exits of the car park n°6, I *want* him to tell me if he plans
to go to car park ...12 because I need to tell him if the car park if
free or full.


Okay... There's always a possibility that the recorded arrivals match
at more than one place in the plan, so we can't expect the prediction
to be unique. Here is a sketch how to go about it:

my @estimated = qw(1 2 3 1 6 12);
my @arrived = qw( 1 6);

my @matches = grep match_at( $_, \ @arrived, \ @estimated),
0 .. $#estimated - @arrived;

my @predictions = map $estimated[ $_ + @arrived], @matches;

print "predictions: @predictions\n";

sub match_at {
my ( $i, $arr, $est) = @_;
for ( 0 .. $#$arr ) {
return 0 unless $est->[ $i + $_] == $arr->[ $_];
}
return 1;
}

In this case, the prediction is unique: 12, but it is easy to
construct examples where it isn't.

In a recursive way I see:

1st path:
1-> 0st element of @estimated
6-> 6th element of @estimated
4th

==> next car parc = 7th element of @estimated ==> "12"
5th

2nd path:
1-> 3rd element of @estimated
6-> 6th element of @estimated
4th

==> next car parc = 7th element of @estimated ==> "12"
5th

I've 2 differents ways, both gives car parc 12 as a result .

Ugh. A diagram with two kinds of arrows, none of which is explained.

All I can see from it is that you arrive at 12 because 6 precedes it,
but in fact the second "path" is a much better match because it has
two consecutive matches at 3 and 4. How would a recursive routine
make use of that?

You're true, the best one is the "path" 3-4 that allow to "predict" 12

Mind you, I'm sure you can come up with a recursive function to solve
this (you almost always can). The big question about recursion is
when *not* to use it (it is inefficient and usually harder to understand
than a non-recursive solution). I don't see how your problem naturally
splits off a smaller partial problem that can be solved in the same way.
That is the usual indicator for a recursive approach.




No, it wouldn't. As I said, the code doesn't deal with errors in the
data. It needs a perfect match anywhere in the @estimated array to
make a prediction.

but I need only a approximation.

I can suppose that the customer didn't go to car parc 7 and goes on his
travel => predict 9

On what ground? You seem to assume he skipped 7. If he swapped
0 and 7, the prediction would have to be 7. You need to define
an (idealized) behavior of your client to make predictions about it.
So far your haven't done that.

You're true too, but I only need a help for my customer.
I permiss me to do mistakes.

Anno

Never mind, I don't want you to lost your time with my problem, Anno, I
thank you a lot for your help.
I'll go on looking for that solution, and if I'm not happy with the
result, I'll throw away that function.

Sebastien