Mizar / みざー mizar

# Batcher Odd-Even Mergesort Sorting Network Generator
# https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
# https://en.wikipedia.org/wiki/Sorting_network
gen = lambda N: [
    [
        (i+j, i+j+(1<<k))
        for j in range((1<<k)%(1<<p), N-(1<<k), 2<<k)
        for i in range(min(1<<k, N-j-(1<<k)))
        if (((i+j)^(i+j+(1<<k)))>>(p+1)) == 0

For the calculation of the sum of integers $A, B$ in $N$-decimal, we divide the $(i-1):k$-digit part into $(i-1):j$-digit and $(j-1):k$-digit parts and consider whether the carry-over occurs for each. $(i \gt j \gt k)$

First, the integers $A, B$ are divided into $(i-1):j$ digits in $N$-decimal, and the values $A_{i-1:j}, B_{i-1:j}$ are added to determine whether carry-forward occurs for the digits above the interval, which are classified into three states as follows.

$A_{i-1:j}+B_{i-1:j} \lt N^{i-j}-1$ ; None
$A_{i-1:j}+B_{i-1:j} = N^{i-j}-1$ ; Propagate
$A_{i-1:j}+B_{i-1:j} \gt N^{i-j}-1$ ; Generate

Example for a decimal number:

	"""StLang@Lark 実行環境サンプル standalone版"""

	### TODO: ここからを本番の問題用の正しいコードに書き換える
	PROGRAM = r"""
	# サンプルプログラム: 二項係数 nCk の計算 (N > 62 の時は演算オーバーフローする可能性あり)
	if N >= K # N < K の時の出力は 0 とする
	$0 = 1
	$1 = 1
	$2 = N
	while $1 <= K # for $1 in 1..=K

	"""StLang@Lark 実行環境サンプル standalone版"""

	### TODO: ここからを本番の問題用の正しいコードに書き換える
	PROGRAM = r"""
	# サンプルプログラム: 二項係数 nCk の計算 (N > 62 の時は演算オーバーフローする可能性あり)
	if N >= K # N < K の時の出力は 0 とする
	$0 = 1
	$1 = 1
	$2 = N
	while $1 <= K # for $1 in 1..=K