Xorlium
September 22nd, 2009, 11:06 AM
Hi,
I'm a math student, and I want to do something, but the only thing I can think of is slow. I'm using python (not that it matters much) and was wondering if anyone could tell me about a fast algorithm that does the following:
I have a (big) list of lists of four numbers from 0 to 7. For example L = [[7,3,2,6],[0,0,0,0],[1,7,0,0],...]
Now I want to find all lists of size 10 (potentially 8^10) such that when I extract certain sublists of size 4, they are all in L. The sublists are:
a) 0,1,2,3
b) 0,4,5,6
c) 1,4,7,8
d) 2,5,7,9
e) 3,6,8,9
(shifted one)
(i.e, so for example if my list of 10 is [2,1,7,3,5,0,0,1,2,6], d) means the sublist [7,0,1,6]). I want [7,0,1,6] to be in L, and so should a), b), c) and e).
Is there a fast algorithm for this? I can only think of the brute force one, that just tests everything.
I'm sorry if it's a well known algorithm or if it was asked before. I wouldn't even know how to search for this, and I'm not an algorithms expert. Actually, I don't know much about algorithms.
Thank you!
I'm a math student, and I want to do something, but the only thing I can think of is slow. I'm using python (not that it matters much) and was wondering if anyone could tell me about a fast algorithm that does the following:
I have a (big) list of lists of four numbers from 0 to 7. For example L = [[7,3,2,6],[0,0,0,0],[1,7,0,0],...]
Now I want to find all lists of size 10 (potentially 8^10) such that when I extract certain sublists of size 4, they are all in L. The sublists are:
a) 0,1,2,3
b) 0,4,5,6
c) 1,4,7,8
d) 2,5,7,9
e) 3,6,8,9
(shifted one)
(i.e, so for example if my list of 10 is [2,1,7,3,5,0,0,1,2,6], d) means the sublist [7,0,1,6]). I want [7,0,1,6] to be in L, and so should a), b), c) and e).
Is there a fast algorithm for this? I can only think of the brute force one, that just tests everything.
I'm sorry if it's a well known algorithm or if it was asked before. I wouldn't even know how to search for this, and I'm not an algorithms expert. Actually, I don't know much about algorithms.
Thank you!