Algorithm to match indices.

Question

0.00/5 (No votes)

See more:

Python

l

list1 = [15, 12, 13, 19, 14] 
list2 = [19, 13, 15, 12, 14]

def function(l1, l2):
    for i in range(len(list1)):
       for j in range(len(list2)):
              if list1[i] == list2[j]:
                    print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')

function(list1, list2)

How to make a less time complexity algorithm?

What I have tried:

I have tried the above code, but I want another efficient one.

Posted 3-May-21 4:31am

User 15144929

Updated 3-May-21 10:43am

Add a Solution

Comments

Richard MacCutchan 3-May-21 9:37am

What is the code supposed to do?

CPallini 3-May-21 9:43am

'Match the indices', of course! :-)
Actually it finds the matching values.

Richard MacCutchan 3-May-21 9:47am

I can see what it is doing, but I do not understand what the objective is.

CPallini 3-May-21 9:55am

I suppose the objective is, precisely, finding matching values.

[no name] 3-May-21 10:13am

I mean in list 1, the first number is 15 (which is at index 0).. the mission is to find the same number in the second list, but printing its index. So, list1 number 15 is at list2 at index 2. and so on..
If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).

CPallini 3-May-21 9:43am

With unordered lists, I'm afraid that is the best time complexity you may achieve.

[no name] 3-May-21 10:13am

I mean in list 1, the first number is 15 (which is at index 0).. the mission is to find the same number in the second list, but printing its index. So, list1 number 15 is at list2 at index 2. and so on..
If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).

[no name] 3-May-21 10:02am

I mean in list 1, the first number is 15 (which is at index 0).. the mission is to find the same number in the second list, but printing its index. So, list1 number 15 is at list2 at index 2. and so on..
If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).

2 solutions

Solution 2

A little improvement, assuming there is only 1 match.

Python

list1 = [15, 12, 13, 19, 14] 
list2 = [19, 13, 15, 12, 14]

def function(l1, l2):
    for i in range(len(list1)):
       for j in range(len(list2)):
              if list1[i] == list2[j]:
                    print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')
                    break; # gets out of loop
function(list1, list2)

Only a little better than O(n²)

There is another approach where complexity is the one of sort function (O(n log(n)).

Python

list1 = [15, 12, 13, 19, 14]
list2 = [19, 13, 15, 12, 14]
# create a list with indices of list2
list3 = [0, 1, 2, 3, 4]
# then do an indirect sort
# I sort list3 on the values of list2
def sortindirect(elem):
    return list2[elem]

list3.sort(key=sortindirect)
# list3 = [4, 1, 3, 0, 2]
def function(l1, l2):
    for i in range(len(list1)):
        # Then rather that scan list2 for a match, I search list2 using dichotomy
       for j in range(len(list2)): # drop this loop and replace with a dichotomy search
       if list1[i] == list2[list3[j]]:
           print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')

Dichotomic search - Wikipedia[^]
Binary search algorithm - Wikipedia[^]

Python

# this print list2 as is
for i in range(len(list2)):
    print (list2[i])
# this print list2 sorted
for i in range(len(list3)):
    print (list2[[list3[i]])

Posted 3-May-21 10:43am

Patrice T

Updated 3-May-21 12:37pm

v3

Comments

CPallini 3-May-21 15:58pm

5.

Patrice T 3-May-21 16:01pm

Thank you

Michel Jakson 3-May-21 16:22pm

Patrice .. Can you explain your code please I do not get it? 'O(nlog(n))'

Patrice T 3-May-21 16:51pm

This is complexity of 'sort'

Michel Jakson 3-May-21 16:52pm

Yes I know, I mean your second code, I do not get it.

Patrice T 3-May-21 17:06pm

Done a correction in my code.

Michel Jakson 3-May-21 17:15pm

This is the whole code right?
list1 = [15, 12, 13, 19, 14]
list2 = [19, 13, 15, 12, 14]
list3 = [0, 1, 2, 3, 4]

def sortindirect(elem):
return list2[elem]

list3.sort(key=sortindirect)

for i in range(len(list1)):
for j in range(len(list2)):
if list1[i] == list2[list3[j]]:
print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')

Patrice T 3-May-21 17:25pm

mostly

Patrice T 3-May-21 17:39pm

Updated solution.
Binary search is left to you.

Michel Jakson 3-May-21 17:17pm

I'm sorry if i'm asking too much, i'm new in python, so i'm trying to develop it. Thanks a lot.

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Accepted Answer · 2021-05-03T05:12:00

Solution 1

Try the following which may, or may not be more efficient:

Python

for i in range(len(list1)):
    try:
        j = list2.index(list1[i])
        print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')
    except ValueError:
        print("no match for", list1[i])

Posted 3-May-21 5:12am

Richard MacCutchan

Comments

[no name] 3-May-21 10:16am

Thank you so much :)

Richard MacCutchan 3-May-21 10:38am

You are welcome, but see CPallini's comment below.

CPallini 3-May-21 10:23am

Should be still O(N^2),according to:
https://wiki.python.org/moin/TimeComplexity
However, the code is nice. Have my 5.

Richard MacCutchan 3-May-21 10:30am

Thanks. I could not see a Big-O value for the index method, although it does reduce the number of iterations in the second loop. The same could be done by a break statement in the original.

CPallini 3-May-21 10:33am

'x in s'

Richard MacCutchan 3-May-21 10:38am

:thumbsup:

Algorithm to match indices.

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Algorithm to match indices.

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us