>>> from collections import deque >>> for x in range(4): d.append(x) ... >>> d deque([0, 1, 2, 3]) >>> for _ in range(4): print(d.popleft()) ... 0 1 2 3 >>> d deque([]) >>> d.extend(range(1, 10)) >>> d deque([1, 2, 3, 4, 5, 6, 7, 8, 9]) >>> len(d) 9 >>> d.reverse() >>> d deque([9, 8, 7, 6, 5, 4, 3, 2, 1]) >>> d.rotate(3) >>> d deque([3, 2, 1, 9, 8, 7, 6, 5, 4])
#
# deque.py : リングバッファによるディーキューの実装
#
# Copyright (C) 2018 Makoto Hiroi
#
class Deque:
def __init__(self, size):
self.buff = [None] * size
self.front = 0
self.rear = 0
self.cnt = 0
# 先頭からデータを取り出す
def pop_front(self):
if self.cnt == 0:
raise IndexError("Deque is empty")
x = self.buff[self.front]
self.front += 1
self.cnt -= 1
if self.front == len(self.buff):
self.front = 0
return x
# 末尾からデータを取り出す
def pop_back(self):
if self.cnt == 0:
raise IndexError("Deque is empty")
self.rear -= 1
self.cnt -= 1
if self.rear < 0:
self.rear = len(self.buff) - 1
return self.buff[self.rear]
# 末尾にデータを追加
def push_back(self, x):
if self.cnt == len(self.buff):
# 先頭からデータを取り出して捨てる
self.pop_front()
self.buff[self.rear] = x
self.rear += 1
self.cnt += 1
if self.rear == len(self.buff):
self.rear = 0
# 先頭にデータを追加する
def push_front(self, x):
if self.cnt == len(self.buff):
# 末尾からデータを取り出して捨てる
self.pop_back()
self.front -= 1
self.cnt += 1
if self.front < 0:
self.front = len(self.buff) - 1
self.buff[self.front] = x
# ジェネレータ
def each(self):
i = self.front
c = self.cnt
while c > 0:
yield self.buff[i]
i += 1
c -= 1
if i == len(self.buff): i = 0
# 空か？
def is_empty(self): return self.cnt == 0
# 空にする
def clear(self):
self.front = 0
self.rear = 0
self.cnt = 0
# 要素数を返す
def __len__(self): return self.cnt
# 表示
def __repr__(self):
s = 'Deque('
if self.cnt > 0:
for x in self.each():
s += '{}, '.format(x)
s = s[:-2]
s += ')'
return s
if __name__ == '__main__':
# 簡単なテスト
d = Deque(8)
print(d)
print(d.is_empty())
print(len(d))
for x in range(4): d.push_back(x)
print(d)
print(d.is_empty())
print(len(d))
for x in range(4, 8): d.push_front(x)
print(d)
print(d.is_empty())
print(len(d))
for _ in range(4): print(d.pop_front())
print(d)
print(d.is_empty())
print(len(d))
for _ in range(4): print(d.pop_back())
print(d)
print(d.is_empty())
print(len(d))
for x in range(10):
d.push_back(x)
print(d)
for x in range(10, 12):
d.push_front(x)
print(d)
Deque() True 0 Deque(0, 1, 2, 3) False 4 Deque(7, 6, 5, 4, 0, 1, 2, 3) False 8 7 6 5 4 Deque(0, 1, 2, 3) False 4 3 2 1 0 Deque() True 0 Deque(0) Deque(0, 1) Deque(0, 1, 2) Deque(0, 1, 2, 3) Deque(0, 1, 2, 3, 4) Deque(0, 1, 2, 3, 4, 5) Deque(0, 1, 2, 3, 4, 5, 6) Deque(0, 1, 2, 3, 4, 5, 6, 7) Deque(1, 2, 3, 4, 5, 6, 7, 8) Deque(2, 3, 4, 5, 6, 7, 8, 9) Deque(10, 2, 3, 4, 5, 6, 7, 8) Deque(11, 10, 2, 3, 4, 5, 6, 7)
>>> from heapq import * >>> a = [] >>> for x in [5,6,4,7,3,8,2,9,1]: heappush(a, x) ... >>> a [1, 2, 3, 4, 6, 8, 5, 9, 7] >>> for _ in range(9): print(heappop(a)) ... 1 2 3 4 5 6 7 8 9 >>> a [] >>> a = [9,8,7,6,5,4,3,2,1] >>> heapify(a) >>> a [1, 2, 3, 6, 5, 4, 7, 8, 9] >>> for _ in range(9): print(heappop(a)) ... 1 2 3 4 5 6 7 8 9
>>> a = b'12345678'
>>> a
b'12345678'
>>> a[0]
49
>>> a[7]
56
>>> a[2:6]
b'3456'
>>> bytes(10)
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
>>> bytes(range(10))
b'\x00\x01\x02\x03\x04\x05\x06\x07\x08\t'
>>> bytearray(10)
bytearray(b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00')
>>> b = bytearray(a)
>>> b
bytearray(b'12345678')
>>> b[0] = ord('a')
>>> b
bytearray(b'a2345678')
num.to_bytes(length, byteorder) int.from_bytes(bytes, byteorder)
>>> a = 'あいうえお' >>> b = a.encode() >>> b b'\xe3\x81\x82\xe3\x81\x84\xe3\x81\x86\xe3\x81\x88\xe3\x81\x8a' >>> b.decode() 'あいうえお' >>> a = 97 >>> a.to_bytes(1, 'big') b'a' >>> int.from_bytes(b'a', 'big') 97
>>> import array
>>> a = array.array('l', range(8))
>>> a
array('l', [0, 1, 2, 3, 4, 5, 6, 7])
>>> a[0]
0
>>> a[7]
7
>>> a[5] *= 100
>>> a
array('l', [0, 1, 2, 3, 4, 500, 6, 7])
>>> a.append(1000)
>>> a
array('l', [0, 1, 2, 3, 4, 500, 6, 7, 1000])
>>> a.pop()
1000
>>> a
array('l', [0, 1, 2, 3, 4, 500, 6, 7])
>>> a = array.array('l', [1, 2, 3, 4])
>>> a
array('l', [1, 2, 3, 4])
>>> a.tolist()
[1, 2, 3, 4]
>>> b = a.tobytes()
>>> b
b'\x01\x00\x00\x00\x02\x00\x00\x00\x03\x00\x00\x00\x04\x00\x00\x00'
>>> c = array.array('l')
>>> c.frombytes(b)
>>> c
array('l', [1, 2, 3, 4])
>>> with open('test.dat', 'wb') as f:
... a.tofile(f)
...
>>> d = array.array('l')
>>> d
array('l')
>>> with open('test.dat', 'rb') as f:
... d.fromfile(f, 4)
...
>>> d
array('l', [1, 2, 3, 4])
xs.sort(key = None, reverse = False) => None sorted(iterable, key = None, reverse = False) => sorted_list
>>> a = [5, 6, 4, 7, 3, 8, 2, 9, 1, 0]
>>> a.sort()
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a.sort(reverse=True)
>>> a
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> sorted(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> b = [('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> b.sort(key = lambda x: x[0])
>>> b
[('bar', 2), ('baz', 3), ('foo', 1), ('oops', 4)]
>>> b.sort(key = lambda x: x[1])
>>> b
[('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> sorted(b, key = lambda x: x[0])
[('bar', 2), ('baz', 3), ('foo', 1), ('oops', 4)]
>>> b
[('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> from operator import itemgetter, attrgetter, methodcaller
>>> f1 = itemgetter(1)
>>> f1([1, 2, 3, 4, 5])
2
>>> a = [('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> sorted(a, key = itemgetter(0))
[('bar', 2), ('baz', 3), ('foo', 1), ('oops', 4)]
>>> sorted(a, key = itemgetter(1))
[('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> class Pair:
... def __init__(self, x, y):
... self.fst = x
... self.snd = y
... def get_fst(self): return self.fst
... def get_snd(self): return self.snd
... def __repr__(self): return 'Pair({},{})'.format(self.fst, self.snd)
...
>>> b = list(map(lambda xs: Pair(xs[0], xs[1]), a))
>>> b
[Pair(foo,1), Pair(bar,2), Pair(baz,3), Pair(oops,4)]
>>> sorted(b, key = attrgetter('fst'))
[Pair(bar,2), Pair(baz,3), Pair(foo,1), Pair(oops,4)]
>>> sorted(b, key = attrgetter('snd'))
[Pair(foo,1), Pair(bar,2), Pair(baz,3), Pair(oops,4)]
>>> sorted(b, key = methodcaller('get_fst'))
[Pair(bar,2), Pair(baz,3), Pair(foo,1), Pair(oops,4)]
>>> sorted(b, key = methodcaller('get_snd'))
[Pair(foo,1), Pair(bar,2), Pair(baz,3), Pair(oops,4)]
元のデータ 安定なソート 不安定なソート
(123, 'abc') (123, 'abc') (789, 'abc')
(456, 'def') (789, 'abc') (123, 'abc')
(789, 'abc') (456, 'def') (456, 'def')
図 : ソートの安定性
>>> a = [('foo', 1), ('bar', 3), ('bar', 2), ('bar', 1), ('baz', 4)]
>>> sorted(a, key = itemgetter(0))
[('bar', 3), ('bar', 2), ('bar', 1), ('baz', 4), ('foo', 1)]
>>> sorted(a, key = itemgetter(0, 1))
[('bar', 1), ('bar', 2), ('bar', 3), ('baz', 4), ('foo', 1)]
>>> from bisect import * >>> a = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4] >>> bisect_left(a, 2) 2 >>> bisect(a, 2) 5 >>> insort_left(a, 2) >>> a [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4] >>> insort(a, 2) >>> a [1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4]
>>> def bsearch(xs, x): ... i = bisect_left(xs, x) ... return len(xs) != i and xs[i] == x ... >>> a [1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4] >>> bsearch(a, 1) True >>> bsearch(a, 2) True >>> bsearch(a, 3) True >>> bsearch(a, 4) True >>> bsearch(a, 5) False >>> bsearch(a, 0) False
問題やプログラム (アルゴリズム) の説明は下記ページを参照してください。
#
# sample04.py : 簡単なプログラム (4)
#
# Copyright (C) 2018 Makoto Hiroi
#
import functools, math
# 最大公約数 (モジュール math に gcd() がある)
# 末尾再帰
def gcd_rec(a, b):
if b == 0: return a
return gcd_rec(b, a % b)
# 繰り返し
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
# 最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
print("----- gcd -----")
print(gcd_rec(12345678, 123456789))
print(gcd_rec(1234321, 12345654321))
print(gcd(12345678, 123456789))
print(gcd(1234321, 12345654321))
print(functools.reduce(gcd, [123, 12345, 12345678]))
print("----- lcm -----")
print(lcm(5, 7))
print(lcm(14, 35))
print(functools.reduce(lcm, range(2, 21)))
print(functools.reduce(lcm, range(2, 31)))
# 平方根 (ニュートン法)
def sqrt(x):
def init(x, s = 1.0):
while s < x:
s *= 2.0
x /= 2.0
return s
if x < 0:
raise ValueError('sqrt domain error')
p = init(x) if x > 1.0 else 1.0
while True:
q = (p + x / p) / 2
if q >= p: break
p = q
return p
print('----- sqrt -----')
print(sqrt(0.5))
print(sqrt(2))
print(sqrt(3))
print(sqrt(4))
print(sqrt(5))
print(math.sqrt(0.5))
print(math.sqrt(2))
print(math.sqrt(3))
print(math.sqrt(4))
print(math.sqrt(5))
# めのこ平方
def isqrt(n):
def isqrt_sub(n, m):
while n >= m:
n -= m
m += 2
return m // 2
if n < 100:
return isqrt_sub(n, 1)
else:
m = 10 * isqrt(n // 100)
return isqrt_sub(n - m * m, 2 * m + 1)
print('----- isqrt -----')
print(isqrt(6789))
print(isqrt(123456789))
print(isqrt(1234567890))
#
# 素因数分解
#
def factorization(n):
def factor_sub(n, m):
c = 0
while n % m == 0:
c += 1
n //= m
return c, n
#
buff = []
c, m = factor_sub(n, 2)
if c > 0: buff.append((2, c))
c, m = factor_sub(m, 3)
if c > 0: buff.append((3, c))
x = 5
while m >= x * x:
c, m = factor_sub(m, x)
if c > 0: buff.append((x, c))
if x % 6 == 5:
x += 2
else:
x += 4
if m > 1: buff.append((m, 1))
return buff
#
# 約数の個数
#
def divisor_num(n):
a = 1
for _, x in factorization(n):
a *= x + 1
return a
print('----- divisor_num -----')
print(divisor_num(24))
print(divisor_num(12345678))
print(divisor_num(123456789))
print(divisor_num(1234567890))
print(divisor_num(1111111111))
#
# 約数の合計値
#
# σ(p, n) の計算
def div_sum_sub(p, n):
a = 0
while n > 0:
a += p ** n
n -= 1
return a + 1
def divisor_sum(n):
a = 1
for p, q in factorization(n):
a *= div_sum_sub(p, q)
return a
print('----- divisor_sum -----')
print(divisor_sum(24))
print(divisor_sum(12345678))
print(divisor_sum(123456789))
print(divisor_sum(1234567890))
print(divisor_sum(1111111111))
#
# 約数
#
# p ^ q の約数を求める
def divisor_sub(p, q):
a = []
for i in range(0, q + 1):
a.append(p ** i)
return a
def divisor(n):
xs = factorization(n)
ys = divisor_sub(xs[0][0], xs[0][1])
for p, q in xs[1:]:
ys = [x * y for x in divisor_sub(p, q) for y in ys]
return sorted(ys)
print('----- divisor -----')
print(divisor(24))
print(divisor(12345678))
print(divisor(123456789))
print(divisor(1234567890))
print(divisor(1111111111))
#
# 循環小数
#
# 探索 (リストのメソッド index() は ValueError が送出される)
def position(n, xs):
for i, x in enumerate(xs):
if x == n: return i
return -1
# 循環小数 m/n = ([...],[...])
def repdec(m, n):
xs = []
ys = []
while True:
p = m // n
q = m % n
if q == 0:
ys.append(p)
return ys, [0]
else:
x = position(q, xs)
if x >= 0:
ys.append(p)
return ys[:x+1], ys[x+1:]
xs.append(q)
ys.append(p)
m = q * 10
# 循環小数を分数に直す
def from_repdec(xs, ys):
# 有限小数の部分を分数に直す
p0 = functools.reduce(lambda a, x: a * 10 + x, xs, 0)
q0 = 10 ** (len(xs) - 1)
# 循環節を分数に直す
p1 = functools.reduce(lambda a, x: a * 10 + x, ys, 0)
q1 = (10 ** len(ys) - 1)
# 有限小数 + 循環節
a = q0 * q1
b = q1 * p0 + p1
c = gcd(a, b)
return b // c, a // c
print('----- repdec, from_repdec -----')
for x in range(2, 12):
xs = repdec(1, x)
print(xs)
print(from_repdec(*xs))
xs = repdec(355, 113)
print(xs)
print(from_repdec(*xs))
#
# カッコ列
#
def kakko(f, n):
def kakko_sub(x, y, a):
if x == y == n:
f(a)
else:
if x < n:
kakko_sub(x + 1, y, a + '(')
if y < x:
kakko_sub(x, y + 1, a + ')')
kakko_sub(0, 0, '')
print('----- kakko -----')
kakko(print, 3)
kakko(print, 4)
#
# カタラン数
#
def catalan_num(n):
table = [1] * n
for i in range(1, n):
for j in range(i, n):
table[j] += table[j - 1]
return table[-1]
print('----- Catalan number -----')
for x in range(1, 11):
print(catalan_num(x))
print(catalan_num(50))
print(catalan_num(100))
#
# カッコ列と二分木
#
# 葉
class Leaf:
def __repr__(self): return 'Leaf'
# 節
class Node:
def __init__(self, l, r):
self.left = l
self.right = r
def __repr__(self):
return 'Node({}, {})'.format(self.left, self.right)
# 二分木をカッコ列に変換
def kakko_from_tree(tree):
def sub(tree):
if isinstance(tree, Leaf):
return ')'
else:
return '(' + sub(tree.left) + sub(tree.right)
s = sub(tree)
return s[:-1]
# カッコ列を二分木に変換
def kakko_to_tree(s):
def sub(i):
if len(s) <= i:
return Leaf(), i
elif s[i] == ')':
return Leaf(), i + 1
elif s[i] == '(':
l, j = sub(i + 1)
r, k = sub(j)
return Node(l, r), k
else:
raise Exception('kakko_to_tree: illegal char')
return sub(0)[0]
def test(s):
print(s)
t = kakko_to_tree(s)
print(t)
u = kakko_from_tree(t)
print(u)
print('----- kakko to tree, kakko from tree -----')
kakko(test, 3)
#
# 分割数
#
def part_num(n, k):
if n == 1 or k == 1:
return 1
if n < 0 or k < 1:
return 0
else:
return part_num(n - k, k) + part_num(n, k - 1)
def partition_number(n):
return part_num(n, n)
# 動的法による高速化
def partition_number_fast(n):
table = [1] * (n + 1)
for k in range(2, n + 1):
for m in range(k, n + 1):
table[m] += table[m - k]
return table[n]
# 整数の分割
def part_int_sub(n, k, a):
if n == 0: print(a)
elif n == 1: print(a + [1])
elif k == 1: print(a + [1] * n)
else:
if n >= k:
part_int_sub(n - k, k, a + [k])
part_int_sub(n, k - 1, a)
def partition_of_int(n): part_int_sub(n, n, [])
print('----- partition number -----')
for x in range(1, 11): print(partition_number(x))
print(partition_number_fast(1000))
print(partition_number_fast(2000))
print(partition_number_fast(4000))
partition_of_int(5)
partition_of_int(6)
partition_of_int(7)
#
# 集合の分割
#
def part_sub(f, ls, a):
if not ls:
f(a)
else:
for i in range(len(a)):
a[i].append(ls[0])
part_sub(f, ls[1:], a)
a[i].pop()
a.append([ls[0]])
part_sub(f, ls[1:], a)
a.pop()
def partition_of_set(f, ls):
part_sub(f, ls[1:], [[ls[0]]])
print('----- partition of set -----')
partition_of_set(print, [1,2,3])
partition_of_set(print, [1,2,3, 4])
----- gcd ----- 9 121 9 121 3 ----- lcm ----- 35 70 232792560 2329089562800 ----- sqrt ----- 0.7071067811865475 1.414213562373095 1.7320508075688772 2.0 2.23606797749979 0.7071067811865476 1.4142135623730951 1.7320508075688772 2.0 2.23606797749979 ----- isqrt ----- 82 11111 35136 ----- divisor_num ----- 8 24 12 48 16 ----- divisor_sum ----- 60 27319968 178422816 3211610688 1246404096 ----- divisor ----- [1, 2, 3, 4, 6, 8, 12, 24] [1, 2, 3, 6, 9, 18, 47, 94, 141, 282, 423, 846, 14593, 29186, 43779, 87558, 131337, 262674, 685871, 1371742, 2057613, 4115226, 6172839, 12345678] [1, 3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421, 41152263, 123456789] [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90, 3607, 3803, 7214, 7606, 10821, 11409, 18035, 19015, 21642, 22818, 32463, 34227, 36070, 38030, 54105, 57045, 64926, 68454, 108210, 114090, 162315, 171135, 324630, 342270, 13717421, 27434842, 41152263, 68587105, 82304526, 123456789, 137174210, 205761315, 246913578, 411522630, 617283945, 1234567890] [1, 11, 41, 271, 451, 2981, 9091, 11111, 100001, 122221, 372731, 2463661, 4100041, 27100271, 101010101, 1111111111] ----- repdec, from_repdec ----- ([0, 5], [0]) (1, 2) ([0], [3]) (1, 3) ([0, 2, 5], [0]) (1, 4) ([0, 2], [0]) (1, 5) ([0, 1], [6]) (1, 6) ([0], [1, 4, 2, 8, 5, 7]) (1, 7) ([0, 1, 2, 5], [0]) (1, 8) ([0], [1]) (1, 9) ([0, 1], [0]) (1, 10) ([0], [0, 9]) (1, 11) ([3], [1, 4, 1, 5, 9, 2, 9, 2, 0, 3, 5, 3, 9, 8, 2, 3, 0, 0, 8, 8, 4, 9, 5, 5, 7, 5, 2, 2, 1, 2, 3, 8, 9, 3, 8, 0, 5, 3, 0, 9, 7, 3, 4, 5, 1, 3, 2, 7, 4, 3, 3, 6, 2, 8, 3, 1, 8, 5, 8, 4, 0, 7, 0, 7, 9, 6, 4, 6, 0, 1, 7, 6, 9, 9, 1, 1, 5, 0, 4, 4, 2, 4, 7, 7, 8, 7, 6, 1, 0, 6, 1, 9, 4, 6, 9, 0, 2, 6, 5, 4, 8, 6, 7, 2, 5, 6, 6, 3, 7, 1, 6, 8]) (355, 113) ----- kakko ----- ((())) (()()) (())() ()(()) ()()() (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() ----- Catalan number ----- 1 2 5 14 42 132 429 1430 4862 16796 1978261657756160653623774456 896519947090131496687170070074100632420837521538745909320 ----- kakko to tree, kakko from tree ----- ((())) Node(Node(Node(Leaf, Leaf), Leaf), Leaf) ((())) (()()) Node(Node(Leaf, Node(Leaf, Leaf)), Leaf) (()()) (())() Node(Node(Leaf, Leaf), Node(Leaf, Leaf)) (())() ()(()) Node(Leaf, Node(Node(Leaf, Leaf), Leaf)) ()(()) ()()() Node(Leaf, Node(Leaf, Node(Leaf, Leaf))) ()()() ----- partition number ----- 1 2 3 5 7 11 15 22 30 42 24061467864032622473692149727991 4720819175619413888601432406799959512200344166 1024150064776551375119256307915896842122498030313150910234889093895 [5] [4, 1] [3, 2] [3, 1, 1] [2, 2, 1] [2, 1, 1, 1] [1, 1, 1, 1, 1] [6] [5, 1] [4, 2] [4, 1, 1] [3, 3] [3, 2, 1] [3, 1, 1, 1] [2, 2, 2] [2, 2, 1, 1] [2, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1] [7] [6, 1] [5, 2] [5, 1, 1] [4, 3] [4, 2, 1] [4, 1, 1, 1] [3, 3, 1] [3, 2, 2] [3, 2, 1, 1] [3, 1, 1, 1, 1] [2, 2, 2, 1] [2, 2, 1, 1, 1] [2, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1] ----- partition of set ----- [[1, 2, 3]] [[1, 2], [3]] [[1, 3], [2]] [[1], [2, 3]] [[1], [2], [3]] [[1, 2, 3, 4]] [[1, 2, 3], [4]] [[1, 2, 4], [3]] [[1, 2], [3, 4]] [[1, 2], [3], [4]] [[1, 3, 4], [2]] [[1, 3], [2, 4]] [[1, 3], [2], [4]] [[1, 4], [2, 3]] [[1], [2, 3, 4]] [[1], [2, 3], [4]] [[1, 4], [2], [3]] [[1], [2, 4], [3]] [[1], [2], [3, 4]] [[1], [2], [3], [4]]