Notice removed Reward existing answer by user40980
    Bounty Ended with amon's answer chosen by Community
    Notice added Reward existing answer by user40980
    Bounty Started worth 100 reputation by Community
4 list formatting
source | link

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

Reading some suggestions I feel that I have to clarify a couple of points that I left too vague.

  1. Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways

    Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways

    A = (1234356), B = (236), matches could be either -23---6 or -2--3-6

  2. I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient.

A = (1234356), B = (236), matches could be either -23---6 or -2--3-6

  1. I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient.

Sorry if this wasn't clear.

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

Reading some suggestions I feel that I have to clarify a couple of points that I left too vague.

  1. Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways

A = (1234356), B = (236), matches could be either -23---6 or -2--3-6

  1. I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient.

Sorry if this wasn't clear.

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

Reading some suggestions I feel that I have to clarify a couple of points that I left too vague.

  1. Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways

    A = (1234356), B = (236), matches could be either -23---6 or -2--3-6

  2. I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient.

Sorry if this wasn't clear.

    Tweeted twitter.com/#!/StackProgrammer/status/400609384575033344
3 added 588 characters in body
source | link

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

Reading some suggestions I feel that I have to clarify a couple of points that I left too vague.

  1. Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways

A = (1234356), B = (236), matches could be either -23---6 or -2--3-6

  1. I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient.

Sorry if this wasn't clear.

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

Reading some suggestions I feel that I have to clarify a couple of points that I left too vague.

  1. Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways

A = (1234356), B = (236), matches could be either -23---6 or -2--3-6

  1. I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient.

Sorry if this wasn't clear.

2 fix layout
source | link

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4) B = (1 3) C = (1 3 4) D = (3 1) E = (1 2 5)

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A C

C matches A D

D does not match A as the ordering is different E

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4) B = (1 3) C = (1 3 4) D = (3 1) E = (1 2 5)

B matches A C matches A D does not match A as the ordering is different E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something?

Take a sequence of integers A, for example (1 2 3 4)

Take various sequences of integers and test if any of them match A such that.

  1. A contains all of the integers in the tested sequence
  2. The ordering of the integers in the tested sequence are the same in A
  3. We don't care about any integers in A that are not in the test sequence
  4. We want all matching test sequences, not just the first.

An example

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B matches A

C matches A

D does not match A as the ordering is different

E does not match A as it contains an integer not in A

I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths.

Thanks

1
source | link