Finding ordered array in an ordered array

Question

c = [-1, 0, 1, 2, 3, 4]  
d = [-1,0,2,3,4,5,6]
a = [-1, 1, 6, 8, 9, 12]
main = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

desired output:

fc = [-1,0,1,2,3],[0,1,2,3,4]
fd = [2,3,4,5,6]
fa = []

I want to find how many times the ordered set is in the larger set given an interval. In my case, I choose 5 since this is for my poker game. Set's won't work since they need to be in order so I don't know what to use.

In my program, I tried using for loops but I'm not getting it.

ns = len(c)-5
nt = range(0,ns)
if ns >= 0:
    for n in nt:
        templist = c[n:n+5]

I just need a function to compare both lists.

I don't understand the question, but maybe this is helpful: [Does Python have an ordered set?](https://stackoverflow.com/q/1653970/4518341) — wjandrea, May 26 '19 at 00:10

score 1 · Answer 1 · answered May 26 '19 at 01:12

1

Compare the small lists to slices of main.

c = [-1, 0, 1, 2, 3, 4]
d = [-1,0,2,3,4,5,6]
a = [-1, 1, 6, 8, 9, 12]
main = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

for sublist in [c, d, a]:
    l = len(sublist)
    i = 0
    while i + l <= len(main):
        if sublist == main[i:i+l]:
            print 'sublist %s matches' % sublist
        i = i + 1

answered May 26 '19 at 01:12

John Gordon

29,573
7
33
58

You need a second loop that pulls out each of the 5 element sub-sublists from the sublists. But the OP probably needs to do some of the work from here. – Heath Raftery May 26 '19 at 01:15
Ah, I didn't realize that the small lists were six elements long, not five. Good call. – John Gordon May 26 '19 at 01:18

score 0 · Answer 2 · answered May 26 '19 at 01:22

Neither pretty nor optimal, but it does what seems to be asked:

c = [-1, 0, 1, 2, 3, 4]
d = [-1, 0, 2, 3, 4, 5, 6]
a = [-1, 1, 6, 8, 9, 12]
main = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]


def find_in_order(to_find, to_search, num_to_find):
    solutions = []
    for bucket in to_find:
        bucket_solutions = []
        solutions.append(bucket_solutions)
        for thing in [bucket[x:x + num_to_find] for x in range(len(bucket) - num_to_find + 1)]:
            for section in [main[y:y + num_to_find] for y in range(len(to_search) - num_to_find + 1)]:
                if thing == section:
                    bucket_solutions.append(thing)
    return solutions


fc, fd, fa = find_in_order([c, d, a], main, 5)

# fc == [[-1, 0, 1, 2, 3], [0, 1, 2, 3, 4]]
# fd == [[2, 3, 4, 5, 6]]
# fa == []

There's not bounds-checking in this, so it might be brittle. I also don't like how the additions of the magic number 1 are needed to get things to align. If you care about speed, string searches do things like keeping a rolling checksum and only doing comparisons when the checksums match. This is left as an exercise. Also, I'm on:

sys.version
'3.6.8 |Anaconda, Inc.| (default, Dec 30 2018, 01:22:34) \n[GCC 7.3.0]'

score 0 · Answer 3 · answered May 26 '19 at 01:37

Here is a function that I made that might help you. You can pass your list as an argument and it will compare the lists.

main_set = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
c = [-1, 0, 1, 2, 3, 4]


def compare(cmp_array):
  new_arrays = []
  temp = []
  for pos, i in enumerate(cmp_array):
        for i2 in range(pos, pos+5):
              temp.append(cmp_array[i2])
        new_arrays.append(temp)
        temp = []
        if pos >= len(cmp_array)-5:
              break
  return_arrays = [] 
  for array in new_arrays:
        for pos, i in enumerate(main_set):
              match = True
              if i == array[0]:
                    for pos2 in range(pos, pos+5):
                          if array[pos2-pos] != main_set[pos2]:
                                match = False
                                break
                    if match:
                          return_arrays.append(array)
  return return_arrays

fc = compare(c)

print(fc)

Finding ordered array in an ordered array

3 Answers3