python3: sets

[lab08](http://cs61a.org/lab/lab08/)よりsetsについて簡単な紹介と問題が出たのでそこまで時間も必要なさそうなのでさらっとsetsについて復習がてら。

# sets

>a set is an __unordered__ collection of __distinct__ objects that supports membership testing, union, intersection, and adjunction. The main difference between sets and lists are 1. they are unordered, and 2. there are no duplicates. Other than that almost everything is the same.

unorderedはそのまんまだと思うけどdistinctっていう特徴はリストにはない性質なので中々面白い。ぱっと考えたのは例えばわざわざ`def lst_filter(cond, s): return filter(cond, s) where cond yields something that goes along the lines of return if x in s`みたいなのしなくても`set(s)`だけで余計な余りを全て消してくれたり。もしくは`sorted`系のscreening_funcを使ってセットをリストに返してあげることも楽に。setが何よりも優れている点は__いちいち関数をつくったりしないといけないようなことを`set`を通すだけで他者より圧倒的な処理速度でやってしまうこと。__

ラボからの例を参考に:

```
>>> a = [1, 1, 2, 2, 3, 3]
>>> a = set(a)
>>> a  # No duplicates
{1, 2, 3}
>>> a = {3, 1, 2}
>>> a  # Not necessarily in same order
{1, 2, 3}
```

# membership testing, union, intersection and adjunction?

イマイチ実感がわかなかったので調べてみたら意外とシンプル。一般的な解説は[ここに](https://docs.python.org/2/library/sets.html#set-objects)書いてあるので参考までに。一言でいうとmembership testingは`x in s`、unionはリストで言う`add(lst1, lst2)`、intersectionは無理矢理リストの考え方を使えば`[filter(lambda x: x in lst, sublist) for sublist in sublst]`でadjunctionは`lst.add(4)`になるのかな。

ちなみに個人的に`intersection (also denoted as set(x) & set(y))`に混乱させられたのでSOFも参考にしながら調べました。

```
>> set([1,2,3]) & set([2,3,4])
set([2, 3])
>> set().intersection(*[[1,2,3], [2,3,4]])
set([])
```
なぜ下のコードが出ないかというと単純に最初の`set()`が空っぽだから。上に書いてあるように二つに何か要素が入っていないとこの場合では空のセットを出してしまうのでこのケースで考えられるとしたらあらかじめセットを何かの変数に入れておいて`set.intersection(*sets)`として一気に片付けてしまうのが賢いなと勉強になった。以下SOFより

```
>>> x = [{1, 2, 3}, {2, 3, 4}, {3, 4, 5}]
>>> set.intersection(*x)
set([3])
```
# Exercises
エクササイズがてら実際にラボにでた問題を参考にセットの性質を考えてみることにします。

##Q1
```
# Question2
def find_duplicates(lst):
    """Returns True if lst has any duplicates and False if it does not.

    >>> find_duplicates([1, 2, 3, 4, 5])
    False
    >>> find_duplicates([1, 2, 3, 4, 2])
    True
    >>> find_duplicates(list(range(100000)) + [-1]) # make sure you have linear time
    False
    """
    set_lst = set(lst)
    if list(set_lst) != lst:
        return True
    else:
        return False
```

「setに変えたlstとinputとして入ってきたlstを比べて同じだったらFalseで違かったら（=lst has been mutated）`True`と返せばいいんじゃ」と思い以上の用に書いてみました。模範解答はもっと短くてさすが！ってうなります。`return len(set(lst)) != len(lst)`これだけ。。。。！たしかにmutateされたってことは究極的には長さが変わるってことだしな。snap!

##Q2
```
def pow(n,k):
    """Computes n^k.

    >>> pow(2, 3)
    8
    >>> pow(4, 2)
    16
    >>> a = pow(2, 100000000) # make sure you have log time
    """
    if k == 0:
        return 1
    elif k == 1:
        return n
    elif k % 2 == 1:
        return n * pow(n, k - 1)
    else:
        pow2 = pow(n, k / 2)
        return pow2**2
```

これはTAからもらったヒントとたくさんぐぐって調べた結果出た答え。簡単に言うと例えば2^64を分解すると2^2 * 2^2 => 2^4 * 2^4 => 2^8 * 2^8 => 2^16 * 2^16 => 2^32 * 2^32 = 2^64を考えてみると問題が分かりやすくなる。（ちなみにこれは約logの数分（appx 5)だけ処理が行われるらしい。）結果、偶数の場合は以上の処理を行い、そうじゃない場合は無理矢理偶数の形にしてから処理を行うイメージ。

##追記: Q3

[HW05](http://cs61a.org/hw/hw05/#q8)より。

```
def add_up(n, lst):
    """Returns True if any two non identical elements in lst add up to n.

    >>> add_up(100, [1, 2, 3, 4, 5])
    False
    >>> add_up(7, [1, 2, 3, 4, 2])
    True
    >>> add_up(10, [5, 5])
    False
    >>> add_up(151, range(0, 200000, 2))
    False
    >>> timeit(lambda: add_up(151, range(0, 200000, 2))) < 1.0
    True
    >>> add_up(50002, range(0, 200000, 2))
    True
    """
    "*** YOUR CODE HERE ***"
```

最初に自分で作ったコードは以下の様な感じでした。

```
def add_up(n, lst):
    sorted_lst = list(set(lst))
    n_diff = [n - x for x in sorted_lst]
    if set(sorted_lst) & set(n_diff) == set():
        return False
    else:
        if set(sorted_lst) == set(n_diff):
            return False
        else:
            return True
```

ただ<a href="http://codereview.stackexchange.com/questions/93661/finding-two-numbers-that-add-to-a-given-total" target="_blank">色々調べていたら</a>他にも色んな方法があったのでそっちも参考にもう一つの解答を自分なりに作ってみた。

```
def add_up(n, lst):
	divided_n = n // 2
	    filtered_out_nums = set([n - x for x in lst if x <= divided_n]) & set([x for x in lst if x > divided_n])
	    if filtered_out_nums == set():
	        return False
	    else:
	        for x in filtered_out_nums:
	            num_list = [n-x, x]
	        return n == sum(num_list)
```

考え方は若干似てるような似てないような。最初に片方の数`x`を持ってきて`other_val = n - x`としている。こちらでは`div_n = n // 2`を用意してそれより大きい数と小さい数をベースに数を集めてきて共通する数字を`filtererd_out_nums`に入れている。処理の順番が若干違うのとsetの出し方が若干異なる点以外ではそこまで変わりはなさそう。

![Screen Shot 2016-03-24 at 1.23.34 PM.png](https://qiita-image-store.s3.amazonaws.com/0/87666/8aeed6a9-519b-0844-b475-a5d75f8ad025.png)

![Screen Shot 2016-03-24 at 1.31.18 PM.png](https://qiita-image-store.s3.amazonaws.com/0/87666/1dd28895-aa37-8837-fbc9-b630a5177565.png)

#追記: Difference

例えば2つのリストがあって各リストが持っていない要素だけを引っ張って欲しいときなどに有効活用できそうな`set(lst).difference(lst2)`。`list`に変えると更に扱いやすくなる。

```
def missing_val(lst0, lst1):
    """Assuming that LST0 contains all the values in LST1, but LST1 is missing
    one value in LST0, return the missing value.  The values need not be
    numbers.

    >>> from random import shuffle
    >>> missing_val(range(10), [1, 0, 4, 5, 7, 9, 2, 6, 3])
    8
    >>> big0 = [str(k) for k in range(15000)]
    >>> big1 = [str(k) for k in range(15000) if k != 293 ]
    >>> shuffle(big0)
    >>> shuffle(big1)
    >>> missing_val(big0, big1)
    '293'
    >>> timeit(lambda: missing_val(big0, big1)) < 1.0
    True
    """
    "*** YOUR CODE HERE ***"
    return list(set(lst0).difference(lst1))[0]
```


#参考にしたリンク
- [Unordered collections of unique elements](https://docs.python.org/2/library/sets.html#set-objects)
- [Python set Union and set Intersection operate differently?](http://stackoverflow.com/questions/19580944/python-set-union-and-set-intersection-operate-differently)
- [Finding two numbers that add to a given total](http://codereview.stackexchange.com/questions/93661/finding-two-numbers-that-add-to-a-given-total)
- [Missing and Additional values in 2 list](http://stackoverflow.com/questions/15529775/missing-and-additional-values-in-2-list)