Python Function Help

[namarino]

Hey guys, I have to write a function that detects duplicates in a sequence. So given string or list of numbers or strings, the function returns True if the string has duplicate letters or if the list has duplicate numbers or strings. How do I go about doing this? I know there is a built in method to do this, but I can't use it. I'm not asking you to write this for me, just give me some ideas of the logic behind it. Thanks so much!

[Enderman]

for each item in string/list check list from start to that item position

if find equal item, delete this item

go to that same place in list -1 (because you deleted that item you need to move back 1 spot so that you dont miss the next item)

back to beginning

[fizzlesticks]

Is the built in function you're talking about set()?

[madknight3]

An easy, but less efficient algorithm, is to use a nested loop. For each item in the collection, check it against every other item in the collection.

[PampaZiya]

Let's say you have a string, what would be the best way to check if the item occurs more than one time? You start with the first letter and check if exists by going one letter at a time from the beginning of string till the end (hint), if, going through the letters, you find it again then the function will return true, if not it will keep on going till the end of string. Then it picks the 2nd letter and go through the string again, then third... till n, which is the length of the string. I can give you the algorithm and you translate it to python if you want.

[namarino]

Let's say you have a string, what would be the best way to check if the item occurs more than one time? You start with the first letter and check if exists by going one letter at a time from the beginning of string till the end (hint), if, going through the letters, you find it again then the function will return true, if not it will keep on going till the end of string. Then it picks the 2nd letter and go through the string again, then third... till n, which is the length of the string. I can give you the algorithm and you translate it to python if you want.

I'm going to give it a try first and then I'll let you know if I need help. Thanks!!

[Azgoth 2]

Two ways I can think of to approach this.  Without some testing I couldn't tell you which would be better (faster/less memory intensive/better scaling with large lists and strings/etc), but both should be easy to use.

 

• For the whole list, convert it to a set (which contains only the unique elements of the list), and see if the set('s length) is the same as the list('s length).  If not, then you have duplicates.  Do the same thing for each string--set(str) returns a set of each unique character in the string.
• Or, using the count() method.  X.count(Y) returns the number of times Y occurs in X.  This works for both substrings in a string and items in a list.

[namarino]

Let's say you have a string, what would be the best way to check if the item occurs more than one time? You start with the first letter and check if exists by going one letter at a time from the beginning of string till the end (hint), if, going through the letters, you find it again then the function will return true, if not it will keep on going till the end of string. Then it picks the 2nd letter and go through the string again, then third... till n, which is the length of the string. I can give you the algorithm and you translate it to python if you want.

Hey I could use some help...haha I got it to cycle through the string, but when I'm comparing letters, I can't figure out how to negate the letter that I've already read in. So for example, If I have the word 'hello', when I read in h, I can't get it to compare it only to the other letters. I don't know if that makes sense.....

[PampaZiya]

Hey I could use some help...haha I got it to cycle through the string, but when I'm comparing letters, I can't figure out how to negate the letter that I've already read in. So for example, If I have the word 'hello', when I read in h, I can't get it to compare it only to the other letters. I don't know if that makes sense.....

 

You should always start with the next letter. So if you started your loop from i=0, your nested loop should start from the i position + 1

[Nineshadow]

You could create a hash table.

It would be O(n) on average, but worst case can be O(n²) I think.

 

Or you can use sets , which would have O(n log n) worst case.

 

Or you can make a copy of your list/vector/array/whatever, sort it, then check adjacent elements. A decent sort tehnique would require O(n log n) for comparing then n-1 for checking adjecent elements.

 

Or, make another list, then go through your original list, adding each element if they aren't found anywhere in the new list.

 

Of course, all of these that I talked about could be used to get rid of duplicates. Checking for duplicates should be easier.

[namarino]

You should always start with the next letter. So if you started your loop from i=0, your nested loop should start from the i position + 1

def has_duplicates(xs):	duplicates = False		for x in xs:	    for y in xs[index[x + 1]]:                if x == y:	                    duplicates = True				return duplicates

This is what I have so far....the index function only works on lists and I'm not necessarily always going to be entering a list. Is my logic correct??