3

我正在寻找一个 J 代码来执行以下操作。

假设我有一个随机整数列表（已排序）， 2 3 4 5 7 21 45 49 61 我想从第一个元素开始并删除列表中元素的任何倍数，然后移动到下一个元素取消它的倍数， 等等等等。

因此，我正在查看的输出是 2 3 5 7 61。基本上是 Eratosthenes 的筛子。如果有人也可以解释代码将不胜感激，因为我正在学习 J 并且发现很难获得大多数代码:(

问候， babsdoc

4

2 回答 2

4

这不完全是您所要求的，但这里有一个更惯用（而且速度更快）的 Sieve 版本。

基本上，您需要检查哪个数字是哪个数字的倍数。你可以从模数表中得到这个：|/~

l =: 2 3 4 5 7 21 45 49 61
|/~ l
  0 1 0 1 1  1  1  1  1
  2 0 1 2 1  0  0  1  1
  2 3 0 1 3  1  1  1  1
  2 3 4 0 2  1  0  4  1
  2 3 4 5 0  0  3  0  5
  2 3 4 5 7  0  3  7 19
  2 3 4 5 7 21  0  4 16
  2 3 4 5 7 21 45  0 12
  2 3 4 5 7 21 45 49  0

每对倍数都会0在桌子上给出一个。现在，我们对0对应于自模的 s（2 mod 2、3 mod 3 等；0对角线上的 s）不感兴趣，所以我们必须删除它们。一种方法是1在它们的位置添加 s，如下所示：

=/~ l
  1 0 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0 0
  0 0 1 0 0 0 0 0 0
  0 0 0 1 0 0 0 0 0
  0 0 0 0 1 0 0 0 0
  0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 1 0 0
  0 0 0 0 0 0 0 1 0
  0 0 0 0 0 0 0 0 1
(=/~l) + (|/~l)
  1 1 0 1 1  1  1  1  1
  2 1 1 2 1  0  0  1  1
  2 3 1 1 3  1  1  1  1
  2 3 4 1 2  1  0  4  1
  2 3 4 5 1  0  3  0  5
  2 3 4 5 7  1  3  7 19
  2 3 4 5 7 21  1  4 16
  2 3 4 5 7 21 45  1 12
  2 3 4 5 7 21 45 49  1

这也可以写成(=/~ + |/~) l。

从这个表中，我们得到了最终的数字列表：列中包含0, 的每个数字都被排除在外。

我们只需乘以列即可构建此排除列表。如果一列包含 a 0，则其乘积为0正数：

*/ (=/~ + |/~) l
   256 2187 0 6250 14406 0 0 0 18240

在执行最后一步之前，我们必须对此进行一些改进。没有理由执行长乘法，因为我们只对0s 和not-0s 感兴趣。因此，在构建表格时，我们将只保留0s 和1s 通过获取每个数字的“符号”（这是signum:*）：

* (=/~ + |/~) l
  1 1 0 1 1 1 1 1 1
  1 1 1 1 1 0 0 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 1 1
  1 1 1 1 1 0 1 0 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1

所以，

*/ * (=/~ + |/~) l
  1 1 0 1 1 0 0 0 1

从排除列表中，您只需copy：#将数字添加到最终列表中：

l #~ */ * (=/~ + |/~) l
   2 3 5 7 61

或者，

(]#~[:*/[:*=/~+|/~) l
   2 3 5 7 61
于 2012-11-29T00:38:37.193 回答
2

默示迭代通常使用连词Power完成。当完成测试需要不是达到一个固定点时，Do While构造运行良好。

在这个解决方案filterMultiplesOfHead中，重复应用，直到没有更多的数字没有被应用或过滤。已应用的数字将累积在部分答案中。当要处理的列表为空时，部分答案是结果，在剥离用于将已处理数据与未处理数据分离的装箱之后。

   filterMultiplesOfHead=: {. (((~: >.)@ %~) # ]) }.
   appendHead=: (>@[ , {.@>@])/
   pass=: appendHead ; filterMultiplesOfHead@>@{:
   prep=: a: , <
   unfinished=: [: -. a: -: {:
   sieve=: [: ; [: pass^:unfinished^:_ prep

   sieve 2 3 4 5 7 21 45 49 61 
2 3 5 7 61

   prep 2 3 4 7 9 10
┌┬────────────┐
││2 3 4 7 9 10│
└┴────────────┘
   appendHead prep 2 3 4 7 9 10
2
   filterMultiplesOfHead 2 3 4 7 9 10
3 7 9
   pass^:2 prep 2 3 4 7 9 10
┌───┬─┐
│2 3│7│
└───┴─┘
   sieve 1-.~/:~~.>:?.$~100
2 3 7 11 29 31 41 53 67 73 83 95 97
于 2012-11-28T20:31:45.617 回答