Element uniqueness

Tags:

Determine the existence of duplicates. O(nlogn) is optimal.

#!/usr/bin/python

import copy

def elem_uniq(val_list):
        result = [[]]

        sorted_list = copy.deepcopy(val_list)
        sorted_list.sort()

        prev_val = sorted_list[0]
        result[-1].append(prev_val)
        for i in xrange(1, len(sorted_list)):
                cur_val = sorted_list[i]

                if prev_val == cur_val:
                        result[-1].append(cur_val)
                else:
                        prev_val = cur_val
                        result.append([cur_val])


        return result

print elem_uniq([1,3,4,3,1])
print elem_uniq([1,3,5,3,2,1,5,3,2])

Output:

mkseo@mkseo:~/tmp$ ./elem_uniq.py
[[1], [3, 3], [4]]
[[1], [2, 2], [3, 3, 3], [5, 5]]
mkseo@mkseo:~/tmp$

Updated: bug fix on 21 July. Thanks SamKong!

Comments

17 responses to “Element uniqueness”

  1. abraxsus Avatar

    머야.. 소팅하고나서 찾잖아-_-;
    정녕 이것뿐이란 말인가.
    이게 optimal인건가..
    소팅되지 않는 종류의 데이터들에 대해서는 어떻게 되는거지?
    equality만 존재하고 크기관계가 없는 데이터에 대해서는?

  2. MKSeo Avatar
    MKSeo

    흠. 그런 예는 잘 모르겠지만 아마도
    one way hashing with very little possibility of collision? MD5 같은?
    worst case 로 했을때 O(nlogn)이 lower bound거든.
    근데 사실 말이 쉽지, nlogn이 하한인거 모르고 덜컥 소팅하고
    찾으면 되잖아요라고 말하기는 어려움.

  3. MKSeo Avatar
    MKSeo

    실은 파이썬 연습목적도 있음 ㅎㅎ

  4. abraxsus Avatar

    ㅋㅋ.. 머야.. 여기가 연습장이냐! ㅎㅎㅎ
    물론, 동감. nlogn이 하한이라는거 모르고 이러면 되잖아요.. 라고 말할수는 없지..
    중요한건 그게 하한이라는거니까…. 근데 어떻게 증명되냐-_-;;

    그리고, 내 생각엔 대소관계가 없는(쉽게 생각해서 복소수같은거) 데이터들에
    대해서는 하한이 n^2일것같다. 대소관계가 정의될경우에나 nlogn이 가능할듯한데.
    음..

  5. MKSeo Avatar
    MKSeo

    복소수는…. a+bi, c+di 면 a먼저 비교하고 b, d 비교하고 이러면 되잖아.
    순서만 정하면 되니까.. 순서는 얼마든지 정할 수 있을거 같은데 ㅎㅎ

    그리고 심심한가본데 내가 문제하나 낼까? ㅋㅋ
    Q) 숫자 나열이 주어졌을때, 합이 0에 가장 가까운 서브 벡터를 찾으시오.

    예를들자면, 1,3,2,1,-1,7 이면 [1,-1] 이 합이 0에 가장 가깝지.
    또 예를들어, 80,70,5,-4,-1,8,100 이면 [5,-4, -1] 이 답이지.

    잘 아는 maximum subvector sum 의 변형판이야.. 물론 nlogn에 풀어야함.
    내가 낼 파이썬 코드로 올리지 ㅎㅎ

    아;; 그리고 증명은 숫자 n개가 있을때 얘네를 위의 코드가 출력하는 답처럼
    파티션을 나눠놓는다고 하자. 그럼 첫번째 수 a1가 있다고 할때, 두번째 수 a2는
    a1과 같거나 다르다. 세번째수 a3은 a1과 같거나 a2와 같거나 아니면 그 둘 모두와
    다르다. a4는 a1과 같거나 a2와 같거나 a3과 같거나 그 모두와 다르다. 뭐
    이런식으로하면 1*2*3*…*n 이 되서 n! 의 방법으로 파티셔닝을 할 수 있다는
    사실을 알 수 있다. 따라서 decision tree를 통해 파티션을 나눠놓는다고하면
    height가 nlogn. 여기까지가 내 생각인데 진규넘은 맞다고 하더군.

  6. 공성식 Avatar
    공성식

    이거 버그 아닌가요?

    [[1, 1], [3, 3], [4]]
    [[1, 1], [2, 2], [3, 3, 3], [5, 5]]

    이런 식으로 결과가 나와야 할 것 같은데…

    for i in xrange(1, len(sorted_list)):
    이것 때문인 것 같네요.
    for i in xrange(0, len(sorted_list)):
    이렇게 고치면 될 것 같구요.

    아니면 제가 문제를 잘못 이해한 걸까요?

  7. 공성식 Avatar
    공성식

    저도 한때는 파이썬에 흠뻑 빠진 적이 있습니다만 루비를 알고나서부턴 많이 멀어졌어요.
    There’s only one way to do it…이라는 미니멀리즘 철학은 참 좋았던 것 같은데…

    루비로 만들어봤어요.
    속도는 글쎄요… (미리 소트하지 않고 결과만 소트하므로 괜찮을 것 같습니다만.)
    저는 속도보다는 golfing을 즐기는 편이라…:-)

    def u a
    a.inject(Hash.new(0)) {|m, i| m[i] += 1; m}.sort_by{|k, v| k}.inject([]) {|m, i| m.push [i[0]] * i[1]}
    end

    p u([1,3,4,3,1])
    p u([1,3,5,3,2,1,5,3,2])

    push 대신 연산자를 쓰면 더 짧아지겠지만 여기서 깨질까봐서…

  8. 공성식 Avatar
    공성식

    두 분 대화에 끼어들어 죄송합니다.
    재밌는 문제를 보면 사죽을 못 쓰는 성격이라…
    아주 단순 무식하게 작성한 것입니다.(brute force…hehe)

    def comb arr
    return [arr] if arr.size == 1
    sub = comb(arr – [arr[0]])
    [[arr[0]]] + sub + sub.map {|i| [arr[0]] + i }
    end

    def nearest_zero arr
    comb(arr).sort_by {|i| i.inject(0) {|m, j| m + j}.abs}[0]
    end

    a = [1,3,2,1,-1,7]

    p nearest_zero(a)

  9. JM Avatar

    partial sum sort!

    그나저나 element duplicate 의 존재만을 determine 하는데 O(nlgn) 이라는건 왠지 억울하네요. 더 낮은 시간 복잡도가 있어야 할 것 같은 기분이에요 ㅜㅜ

  10. MKSeo Avatar
    MKSeo

    역시 JM!! ㅋㅋㅋ
    네 partial sum sort.
    그냥 원래부터 알던건가요? -_-;;;;
    어디서 그런건 다 보고 아는건지 궁금해요..

    음 그리고 0번값을 array에 안넣은 버그네요;;;;
    루비는 이제 접을까 합니다…
    가장 큰 이유는 커뮤니티가 너무 약하다는 것..

  11. abraxsus Avatar

    음.. 그래, 결국 duplicate의 결정은 partitioning문제로군.
    그리고, 0가까이 합구하는.. 이 문제는, 심심풀이 땅콩 문제가 아니자나!! -_-+++
    내가 심심하다는것이 참이라는것이 그렇다고 나를 괴롭혀도 된다는것을 의미하지는 않는다.
    -_-;;; 답안을 아직 살펴보지도 못했다.. 루비땜시..컹… 매력적인 언어야.흘
    뭐 국내 커뮤니티가 적은거지 밖에보면 커뮤니티 크자나..

  12. JM Avatar

    전에 partial sum 을 유용하게 여러 번 썼어서리.. :)
    근데 Programming Pearls 에 있는 문젠가요? 그럼 전에 풀어봤었겠네요. -_-;; 쿨럭;;

  13. abraxsus Avatar

    공성식님과는 다르지만, 이렇게도…

    irb(main):100:0> [1,3,5,2,3,1].sort.inject([]) {|m,n| if (m[-1] && m[-1][0]==n)
    then m[-1] [[1, 1], [2], [3, 3], [5]]

    그냥 true/false만을 원하면,

    irb(main):125:0> def u a
    irb(main):126:1> a.sort.inject{|m,n| return true if m==n;n}
    irb(main):127:1> false
    irb(main):128:1> end

  14. abraxsus Avatar

    에잉.. 코드 깨지넹..

    irb(main):100:0> [1,3,5,2,3,1].sort.inject([]) {|m,n| if (m[-1] && m[-1][0]==n)
    then m[-1].push( n) else m.push([n]) end;m }
    => [[1, 1], [2], [3, 3], [5]]

  15. MKSeo Avatar
    MKSeo

    @abraxsus: 루비 공부 많이 했군여;;;;;

  16. abraxsus Avatar

    @mkseo: 짬짬이 들여다보고있읍니다-_-;;; 시간이 잘 안나서…;; 그 골핑인지 뭔지에 재미들여가고있는듯하군요.. 헐헐.. 루비, 맘에 들었음.

  17. MKSeo Avatar
    MKSeo

    적응하느라 바쁜가보구나 ㅎㅎ

Leave a Reply

Your email address will not be published. Required fields are marked *