Library like os.path.commonprefix but returns common prefix of any 2+ inputted lists?

Question

dict = {'a':['b1','b2', 'b3'], 'b':['b1','b2','b3'], 'c':['b1','b3','b4','b5']}
toList = list(dict.values())
os.path.commonprefix(toList)

os.path.commonprefix(toList) prints just ['b1'] but I'm trying to find the longest common prefix amongst any of the list of lists inputted, so ['b1', 'b2'] here. Another example:

[a,b,c],[a,c,c],[a,b] -> [a,b]

[a,c,d],[a,b,c],[a,d] -> [a]

*EDITED ORIGINAL QUESTION - realized os.path.commonprefix(toList) doesn't return any existing common prefix (like in my example), but the common prefix of all given lists inputted. Is there a library that does do what I want in my example?

Why do you expect `['b1','b2']` to be the common prefix when the key `'c'` has a value that starts with `['b1','b3']` instead? — blhsing, Jan 24 '19 at 15:45
@blhsing Ooh I was under the impression commonprefix returned a common prefix of any of the lists provided, I guess I'll need to figure out another method to get the desired output — user90823745, Jan 24 '19 at 15:47
I'm confused - given [a,b,c],[a,c,c],[a,b], why should 'b' appear in the result when it's not in [a,c,c] and therefore isn't common to all three lists? — jfowkes, Jan 24 '19 at 15:52
This is what you need https://stackoverflow.com/questions/11263172/what-is-the-pythonic-way-to-find-the-longest-common-prefix-of-a-list-of-lists — mad_, Jan 24 '19 at 15:52
@jfowkes I want to return the longest common prefix of any 2+ lists, so in that ex the longest common prefix of at least 2 lists is [a,b] (in [a,b,c] and [a,b]) — user90823745, Jan 24 '19 at 15:56
So even if 2 lists are identical like your example where the 1st and 2nd lists are both `['b1','b2', 'b3']`, you want the output to ignore the last item in the list? — benvc, Jan 24 '19 at 15:57
@benvc i guess the way I'll brute force code this is to look at the 1st item in all the lists, if they're the same (b1) then look at the next item in all the lists and compare. If any 2+ of the lists are still the same, then keep going and return the longest prefix — user90823745, Jan 24 '19 at 16:04

score 1 · Accepted Answer · answered Jan 24 '19 at 16:19

You could build on your initial approach by adding itertools into the mix to find the commonprefix of all list combinations and then use max() to return the longest one. Note that this approach will only return one commonprefix so if there are multiple results that are of equal length and longer than all others it will only return one of them.

For example:

import itertools
import os

data = [['a','b','c'],['a','c','c'],['a','b']]

prefixes = [os.path.commonprefix([a, b]) for a, b in itertools.combinations(data, 2)]
longest = max(prefixes, key=len)
print(longest)
# OUTPUT
# ['a', 'b']

mad_ · Answer 2 · 2019-01-24T16:33:28.857

Made changes to the answer posted here

from itertools import takewhile,izip
x = [['b1', 'b2', 'b3'], ['b1', 'b3', 'b4', 'b5'], ['b1', 'b2', 'b3']]
flag_to_stop=False          # flag to stop returning True 

def allsame(x):
    global flag_to_stop
    if flag_to_stop:
        return False
    elif len(set(x)) == 1:
        return True
    elif len(set(x))>=1 and len(set(x))<len(x):
        flag_to_stop=True   #we have found the maximum common prefix. set flag_to_stop to True
        return True
    elif len(set(x))==len(x):
        flag_to_stop=True
        return False


[i[0] for i in takewhile(allsame ,izip(*x))]

Output

['b1', 'b2']

Library like os.path.commonprefix but returns common prefix of any 2+ inputted lists?

2 Answers2