CODEWITHSUNDEEP
pythondictionaryhashmaphashtable
Andrew Raleigh
Andrew Raleigh

Reputation: 31

Is there a way to create a hash table without dictionaries?

Question:

I have a practice problem, where the input is a list of tuples of 5 integers, and the output is the number of similar tuples. For example, in [(1, 2, 3, 4, 5), (2, 3, 4, 5, 1), (1, 3, 2, 4, 5)], the output would be 2.

You're not supposed to use dictionaries though, but it is from CLRS, so you're meant to use the concept of hash tables.

What I've tried so far:

Some psuedocode I wrote below:

It goes through each index of the list, compares it to every other index and rotating it.

What I realized was wrong about this is, it would run in O(5n^2), which is too efficient for a book about algorithms. Any advice on what I can do to do this without using a dictionary?

def leftShift(tup, n):
    if not tup or not n:
        return tup
    n %= len(tup)
    return tup[n:] + tup[:n]

i = 0
t = 0
rotateTuple(L):
  while i < len(L):
    if L[i][i] in L[i+1]:
      while t < 4:
        .... //This is when I noticed it would fail

The output depends on the number of unique tuples in the list. A tuple is a duplicate if, when rotated by $n$, it is the same as another tuple in the list.

Upvotes: 1

Views: 2011

Answers (1)

tobias_k
tobias_k

Reputation: 82939

A dictionary is a hash table, so the only way to use a hash table without using a dictionary would be to implement your own, which I would not recommend.

You don't have to compare every tuple to every other tuple. Instead, you can "normalize" the tuples by rotating them such that the smallest element is in front, e.g. 3,2,6,9,4 would be rotated to 2,6,9,4,3. If the list contains the minimum element more than once, you have to find all the positions of the minimum element and get the rotation that is "smallest" by natural order of lists, e.g. 1,2,3,4,1 is normalized to 1,1,2,3,4 and 1,3,1,2 to 1,2,1,3.

def normalize(lst):
    min_ = min(lst)
    return min(lst[i:] + lst[:i] for i, e in enumerate(lst) if e == min_)

You could then just put the normalized tuples into a set of "unique" tuples in O(n).

lsts = [(1, 2, 3, 4, 5), (2, 3, 4, 5, 1), (1, 3, 2, 4, 5)]
unique = set(map(normalize, lsts))  # has length 2

It could be argued, though, that a set is just a dict with no values. In this case, you could sort the list of normalized tuples and check for duplicates in O(nlogn + n).

srtd = sorted(map(normalize, lsts))
n = len(lsts) - sum(srtd[i-1] == srtd[i] for i in range(1, len(srtd)))  # 2

Upvotes: 2

Related Questions