Notice removed Reward existing answer by user40980 occurred Nov 20 '13 at 22:16 Bounty Ended with amon's answer chosen by Community♦ occurred Nov 20 '13 at 22:16 Notice added Reward existing answer by user40980 occurred Nov 15 '13 at 21:28 Bounty Started worth 100 reputation by Community♦ occurred Nov 15 '13 at 21:28 4 list formatting edited Nov 14 '13 at 21:55 svick 9,16111 gold badge3232 silver badges4848 bronze badges 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. 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 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 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. 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 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. 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 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 occurred Nov 13 '13 at 13:01 3 added 588 characters in body edited Nov 12 '13 at 15:03 David Gibson 17144 bronze badges 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. 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 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. 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 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 edited Nov 12 '13 at 12:33 Kilian Foth 93.9k3636 gold badges259259 silver badges277277 bronze badges 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence 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 asked Nov 12 '13 at 12:30 David Gibson 17144 bronze badges