再帰を使わない方法
import collections.abc
def flatten(lst):
i = 0
while i < len(lst):
while isinstance(lst[i], collections.abc.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でやる。
その1: リストのすべての要素についての順列を列挙する(permutationsの第2引数を指定しない)。
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>
#include <sstream>
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 {
stringstream ss;
for(int i=0; i<sz; i++) {
if(i) { ss << ", "; }
ss << v[i];
}
cout << ss.str() << endl;
} while(next_permutation(all(v)));
return 0;
}
その2: 指定された要素数の順列を列挙する(permutationsの第2引数に要素数を指定する)。
from itertools import permutations
a = [ 1, 2, 3, 4 ]
a = sorted(a)
for e in permutations(a, 2):
print(', '.join(map(str, e)))
itertoolsのcombinationsでやる。
from itertools import combinations
a = [ 1, 2, 3, 4 ]
a = sorted(a)
for e in combinations(a, 3):
print(', '.join(map(str,e)))
itertoolsのproductでやる。
from itertools import product
for e in product('abcd', repeat=3):
print(', '.join(e))
これは以下のコードと等価。
s = 'abcd'
for x in s:
for y in s:
for z in s:
print(', '.join(x+y+z))
以下の例だと、3 x 7 x 11 x 13 x 17 で 51051 になる。
from functools import reduce a = [3, 7, 11, 13, 17] print(reduce(lambda x, y: x*y, a))
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)))
# リストaの中にxが含まれている場合、その位置を0-indexedで返す。
# xが含まれていない場合は-1を返す。
from bisect import bisect_left
#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
def index(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
return -1
a = range(-int(5e7), int(5e7), 2)
xs = [ -1, 0, int(1e8), -int(1e8), -int(4e6-1), -int(4e6), -45672108, 2222222 ]
for x in xs:
# print('{0:10}: {1:8}'.format(x, binary_search(a, x)))
print('{0:10}: {1:8}'.format(x, index(a, x)))
dequeによる実装。append/popleftを使う。
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を使う。
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([])
from random import shuffle
def qsort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
smaller = [e for e in arr[1:] if e < pivot]
larger = [e for e in arr[1:] if e >= pivot]
return qsort(smaller) + [pivot] + qsort(larger)
a = list(range(1, 11))
shuffle(a)
print(a)
b = qsort(a)
print(b)