プログラミング言語/Python/コードスニペットの履歴(No.2)

履歴一覧
差分を表示
現在との差分を表示
ソースを表示
プログラミング言語/Python/コードスニペットへ行く。
- 1 (2013-05-28 (火) 22:16:37)
- 2 (2013-05-29 (水) 21:01:55)
- 3 (2013-05-29 (水) 21:01:55)
- 4 (2013-06-03 (月) 20:05:19)

目次†

目次
flatten
順列
数字からなるリストの各要素をかけ算する
2つのリストの要素を交互に連結する
リストの重複を排除する
二分探索
キュー
スタック

flatten†

再帰を使わない方法

import collections
def flatten(lst):
  i = 0
  while i < len(lst):
    while isinstance(lst[i], collections.Iterable):
      if not lst[i]:
        lst.pop(i)
        i -= 1
        break
      else:
        lst[i:i+1] = lst[i]
    i += 1
  return lst

print [1, 2, 3, 4, 5, 6, 7] == flatten([1, [2, 3], [4, 5, [6, 7]]])

再帰を使う方法

def flatten(lst):
  flatList = []
  for e in lst:
    if type(e)==list:
      flatList.extend(flatten(e))
    else:
      flatList.append(e)
  return flatList

print [1, 2, 3, 4, 5, 6, 7] == flatten([1, [2, 3], [4, 5, [6, 7]]])

↑

順列†

itertoolsのpermutationsでやる。

from itertools import permutations
a = [ 1, 2, 3, 4 ]
a = sorted(a)
for e in permutations(a):
  print ', '.join(map(str,e))

参考: C++11での実装(next_permutation)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define all(v) v.begin(), v.end()

int main(void) {
    vector<int> v = { 1, 2, 3, 4 };
    int sz = v.size();
    sort(all(v));
    do {
        for(int i=0; i<sz; i++) {
            cout << v[i] << ", ";
        }
        cout << endl;
    } while(next_permutation(all(v)));
    return 0;
}

↑

数字からなるリストの各要素をかけ算する†

以下の例だと、3 x 7 x 11 x 13 x 17 で 51051 になる。

a = [3, 7, 11, 13, 17]
print reduce(lambda x, y: x*y, a)

↑

2つのリストの要素を交互に連結する†

2つのリストから交互にデータを取り出し1つのリストを作る。以下の例だと、c は [1, 4, 2, 5, 3, 6] になる。

a = [1, 2, 3]
b = [4, 5, 6]
c = list(sum(zip(a, b), ()))

↑

リストの重複を排除する†

リストの重複した要素を削除する。ただし要素の出現順に並べる。以下の例では、[2, 0, 3, 4, -1, -2] を出力する。

a = [2, 0, 0, 3, 2, 3, 4, 3, -1, -2, -1]
print list(sorted(set(a), key=a.index))

↑

二分探索†

# -*- coding: utf-8 -*-
# リストaの中にxが含まれている場合、その位置をゼロインデックスで返す。
# xが含まれていない場合は-1を返す。
def binary_search(a, x, lo=0, hi=None):
  if hi == None:
    hi = len(a)
  while lo < hi:
    md = (lo+hi) // 2
    v = a[md]
    if v < x:
      lo = md + 1
    elif x < v:
      hi = md
    else:
      return md
  return -1

a = range(-int(5e7), int(5e7), 2)

xs = [-1, 0, int(1e8), -int(1e8), -int(4e6-1), -int(4e6), -45672108]
for x in xs:
  print '%10d: %8d' % (x, binary_search(a, x))

↑

キュー†

dequeによる実装。append/popleftを使う。

# -*- coding: utf-8 -*-
from collections import deque
q = deque('xyz')
print q # deque(['x', 'y', 'z'])
q.append('a')
q.append('f')
print q # deque(['x', 'y', 'z', 'a', 'f'])
print q.popleft() # x
print q.popleft() # y
print q # deque(['z', 'a', 'f'])
print q.popleft() # z
print q.popleft() # a
print q.popleft() # f
if len(q):
  print q.popleft() # if文がないとIndexErrorになる。
print q # deque([])

↑

スタック†

dequeによる実装。append/popを使う。

# -*- coding: utf-8 -*-
from collections import deque
q = deque('xyz')
print q # deque(['x', 'y', 'z'])
q.append('a')
q.append('f')
print q # deque(['x', 'y', 'z', 'a', 'f'])
print q.pop() # f
print q.pop() # a
print q # deque(['x', 'y', 'z'])
print q.pop() # z
print q.pop() # y
print q.pop() # x
if len(q):
  print q.pop() # if文がないとIndexErrorになる。
print q # deque([])

プログラミング言語/Python/コードスニペット の履歴(No.2)

目次†