python - 使用列表理解来解决 Collat​​z 猜想

Question

有没有一种方法可以在不使用 while 语句的情况下使用列表推导式来验证 Collat​​z 猜想，或者不使用其他方法将 n 值附加到 ls 而无需在每个语句后添加 ls？

from random import choice
from time import sleep

n = choice([x for x in range(2, 99*99) if all(x%y != 0 for y in range(2, x))])
ls = []
ls.append(n)
while True:
    if n % 2 == 0:
        n = n // 2
        ls.append(n)
    elif n % 2 != 0:
        n = (3 * n) + 1
        ls.append(n)
    if n == 1:
        break
print(ls)

Answer 1

一种方式(“缺少”初始数字，但我认为这对目的而言并不重要):

print(f'{n}:')
print([n := 3*n+1 if n%2 else n//2
       for _ in iter(lambda: n, 1)])

n = 92 的输出:

92:
[46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

还有一个(ab)使用基于 kolypto 的列表合成:

print([memo
       for memo in [[n]]
       for n in memo
       if n == 1 or memo.append(n//2 if n%2==0 else n*3+1)
      ][0])

n = 92 的输出:

[92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

我仍然认为 while 循环是合适的方式，但事实证明它并没有快很多。解出 1 到 5000 中所有 n 的次数:

 78 ms  while_loop_ewz93
 87 ms  list_comp_Kelly
126 ms  list_comp_kolypto
 82 ms  list_comp_kolypto_Kellied

我的 iter(lambda: n, 1) 模拟 while n != 1:。更一般地，while condition: 可以用 iter(lambda: bool(condition), False) 模拟。 (如果条件已经是 bool，则显式 bool 不是必需的，例如 iter(lambda: mystring.startswith('x'), False) 。)

将 ewz93 和 kolypto 的基准代码 ( Try it online! ) 修改为也不包括起始编号(为了更公平的比较):

from timeit import repeat

def while_loop_ewz93(n):
    ls = []
    while n != 1:
        n = n // 2 if n % 2 == 0 else (3 * n) + 1
        ls.append(n)
    return ls

def list_comp_Kelly(n):
    return [n := 3*n+1 if n%2 else n//2
            for x in iter(lambda: n, 1)]

def list_comp_kolypto(n):
    return [
        *(lambda memo: [
            memo.append(n // 2 if n%2==0 else n*3+1) or memo[-1]
            for n in memo
            if memo[-1] != 1
        ])([n])
    ]

def list_comp_kolypto_Kellied(n):
    return [
        memo
        for memo in [[n]]
        for n in memo
        if n == 1 or memo.append(n//2 if n%2==0 else n*3+1)
    ][0]

funcs = [
    while_loop_ewz93,
    list_comp_Kelly,
    list_comp_kolypto,
    list_comp_kolypto_Kellied,
]

for _ in range(3):
    for func in funcs:
        t = min(repeat(lambda: list(map(func, range(1, 5001))), number=1))
        print('%3d ms ' % (t * 1e3), func.__name__)
    print()