0

Given a sequence, I was wondering how to find duplicates using ONLY for loops (no imported modules, sorting functions, and etc.) in Python. Here's my following code that involves nested for loops so far:

def has_duplicates(list):
    x = 0
    ans = False
    for i in range(len(list)):
        index = i
        for object in list:
            x = object
        if list[i] == x:
            ans = True
            break
    return ans

I really do not know what to code for the inner loop... Are nested loops even necessary to find the duplicates of a sequence?

Examples of following outputs:

list = [10, 11, 12, 13, 14, 15]
print(ans)
False
list = "Hello"
print(ans)
True
Improve this question
7
  • You need to call the function at least, and use the return value. Commented Sep 29, 2015 at 14:50
  • 2
    are you allowed to use set ? Commented Sep 29, 2015 at 14:50
  • 5
    "I can only use for loops" is an ambiguous statement. What about function defintions, user-defined function calls, built-in function calls, assignment statements, int literals, boolean literals, list literals, binary operators, if blocks, return statements, break statements, and print statements? Because you're using all of those too, right now. Please ask your teacher to be more specific about what you may or may not use. Commented Sep 29, 2015 at 14:55
  • 3
    @Kevin I love how obvious it is that this is a homework assignment. Commented Sep 29, 2015 at 15:00
  • Is enumerate allowed? Commented Sep 29, 2015 at 15:19

4 Answers 4

Reset to default
2

You could do a much more efficient lookahead comparison for each element; this eliminates redundant comparisons throughout the list by only comparing each element to the ones which follow it. I'm not a Python programmer, so I'm only guessing this will work; it probably is the least idiomatic solution to this problem, as well (meaning Python probably has prettier ways of handling this, but it ought to work just fine).

def has_duplicates(list):
    for i in range(len(list)):
        for j in range(i+1, len(list)):
            if list[i] == list[j]:
                return True
    return False
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Since you commented on time complexity elsewhere, I'd just like to point out that this is O(n^2) as well, since it's only quicker than the naive solution by a constant factor of ~2. The efficient solution uses hashing.
@tzaman True, this isn't much more efficient; it's still the same complexity, but it does cut out a lot of excess, almost to the point of n log n. I'd love to see the efficient solution; could you write it up as an answer?
No, it doesn't work like that. Your way cuts out about half of the work; O(n^2 / 2) is still incredibly far from being n lg n. The whole point of dropping constant factors in big-O notation is because they are more or less irrelevant as n grows. Your solution is still very firmly in the O(n^2) bucket. The more efficient would use set so it's not allowed under OP's criteria, but @Peter Wood is close.
Your answer is about as efficient as it can get under the rules specified though, so +1.
If you want to make it a little more pythonic, you can skip the range(len(..)) stuff and just iterate over values: for i in lst: .. for j in lst[i+1:]: .. if i == j - also, don't name the variable list since that shadows the builtin.
|
1

To do that, we iterate over the current list checking for duplicates from the 2nd element onwards and seeing if that particular element exists anywhere at the beginning of the list.

To get the sub-list starting from index 0 uptill the current index we use the slice[:] operation in list and to check if the current element exists in that sub-list, we use the in operator.

You can do the following:

In [1]: def has_duplicates(my_list):
   ...:     for index in range(len(my_list)): 
   ...:         if index!=0: # check only from 2nd element onwards
   ...:             item = my_list[index] # get the current item
   ...:             if item in my_list[:index]: # check if current item is in the beginning of the list uptill the current element
   ...:                 return True # duplicate exist
   ...:     return False # duplicate does not exist
   ...:

In [2]: has_duplicates([1,2,3,4])
Out[2]: False

In [3]: has_duplicates([1,2,3,4,4])
Out[3]: True

In [4]: has_duplicates([1,1,2,3,4,4])
Out[4]: True
Improve this answer

Comments

0

As, there are some suggestions from performance point of view, my solution is from readability point of view. Better use enumerate to grab index.

def has_duplicates(list):

    for index,value  in enumerate(list):
        for index2,value2  in enumerate(list):
            if value==value2 and index!=index2:
                return True


    return False

print has_duplicates("Hello")
print has_duplicates([10, 11, 12, 13, 14, 15])

Output:

True
False
Improve this answer

2 Comments

@ShotgunNinja, off course, i wrote it above. I have written it to make it as simple as i can.
But yeah, this is a pretty clever and idiomatic way to solve this clearly.
0

Take slices of the un-iterated values:

def has_duplicates(values):
    for index, value in enumerate(values, start=1):
        for other_value in values[index:]:
            if value == other_value:
                return True
    return False

If you can use sets:

def has_duplicates(values):
    return len(values) > len(set(values))
Improve this answer

2 Comments

The OP specifies that they're not allowed to use set in their comments.
@ShotgunNinja Well, that burst my bubble.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.