-10

For example: a list just like m=[[2,3],[3,4],[1,2],[4,7],[1,7]]
every element is a little list[x,y], x is not equal to y.
if element a and b in m follow: a[1]==b[0], then a and b will "combined into" c=[a[0],b[1]],
after that,a and b will remove from m,
and c will added into m.
of course,length of m reduced by one.

my question is :
after several times combined oprations,
is there same element exist in new m?
if yes, return True else return False. I write a demo below

from random import choice

def combine_two(a,b):
    c = [None,None]
    if a[1]==b[0]:
        c[0]=a[0]
        c[1]=b[1]
    elif b[1] == a[0]:
        c[0]=b[0]
        c[1]=a[1]
    return c

def fusion(list):
    ss = list[:]
    nn = len(ss)
    for i in range(100):
        ele_1 = choice(ss)
        ele_2 = choice(ss)
        c = combine_two(ele_1,ele_2)
        if c != [None,None]:
            ss.remove(ele_1)
            ss.remove(ele_2)
            ss.append(c)
    return ss

def check(list):
    n = len(list)
    for i in range(n):
        for j in range(n):
            if i != j:
                if list[i][0] == list[j][0] and list[i][1] == list[j][1]:
                    return False
    return True

jj = [[2,3],[3,4],[1,2],[4,7],[11,13],[1,7]]
m = fusion(jj)
print m
n = check(m)
print n

but my fusion function is a workaround. if the input list is very long. it will go wrong.
I have no idea of how to handle 2 element at a time Intelligently. is there a better way to achieve this function?

srishtigarg
  • 1,106
  • 10
  • 24
yp.b
  • 19
  • 2
  • This is not a coding service web page, comeback with specific questions and a code, show some effort. – diegoiva Aug 28 '18 at 03:33
  • What have you tried so far? Stack Overflow is not a code writing service, we're here to help but you'll need to show us what you've tried already. – ajxs Aug 28 '18 at 03:33
  • ok,sorry for my recklessness, I will show sth soon – yp.b Aug 28 '18 at 03:49
  • Use choice means won't cover all data, it may be incorrect in some case, especially list is large. Should cover all, should optimize codes. – zhiwen Aug 28 '18 at 06:58
  • https://stackoverflow.com/questions/1207406/how-to-remove-items-from-a-list-while-iterating – ivan_pozdeev Aug 28 '18 at 10:55

1 Answers1

0

Sort list second element thus can use binary search, after combine, replace one, but should move the other. Codes below:

def combine_two(a ,b):
    c = [None ,None]
    if b[1] == a[0]:
        c[0 ] =b[0]
        c[1 ] =a[1]
    elif a[1] == b[0]:
        c[0 ] =a[0]
        c[1 ] =b[1]
    return c

def binary_find(val, list):
    left = 0
    right = len(list)
    while right - left >= 0:
        mid = (left + right) / 2
        if list[mid][1] > val:
            right = mid - 1
        elif list[mid][1] < val:
            left = mid + 1
        else:
            return mid
    return -1

def fusion_new(list):
    src = list[:]
    src.sort(lambda x, y: x[1] - y[1] if x[1] != y[1] else x[0] - y[0])
    while True:
        i = 0
        merge_num = 0
        while i < len(src):
            elem_1 = src[i]
            ref_val = elem_1[0]

            ##find the match case in src
            index = binary_find(ref_val, src)
            if index >= 0 and index != i:
                elem_2 = src[index]
                c = combine_two(elem_1, elem_2)
                src[i] = c
                src.pop(index)
                merge_num += 1
            else:
                i += 1
        if merge_num < 1:
            break
    return src

def check_new(list):
    temp = list[:]
    temp.sort(lambda x, y: x[0] - y[0] if x[0] != y[0] else x[1] - y[1])
    for i in range(len(temp)-1):
        if temp[i] == temp[i+1]:
            return False
    return True

jj = [[2 ,3] ,[3 ,4] ,[1 ,2] ,[4 ,7] ,[11 ,13] ,[1 ,7]]
m = fusion_new(jj)
print m

n = check_new(m)
print n
zhiwen
  • 82
  • 4