Outer Product: Difference between revisions
m (remove reference to matrix multiplication, that should be for Inner Product instead) 
m (Tone ("notably" is usually superfluous and "should be" is usually not neutral); wiki links) 

Line 1:  Line 1:  
{{BuiltinOuter Product<nowiki>∘.</nowiki>}}, or '''Table''' is a [[monadic operator]], which will produce a [[dyadic function]] when applied with a [[dyadic function]].  {{BuiltinOuter Product<nowiki>∘.</nowiki>}}, or '''Table''' is a [[monadic operator]], which will produce a [[dyadic function]] when applied with a [[dyadic function]]. Outer product applies the [[operand]] function on each [[element]] of the left array with each element of the right array. It can be described as a shortcut for constructing nested [[wikipedia:for loopfor loop]]s.  
=== Syntax ===  === Syntax ===  
Outer Product differs from all other [[monadic operator]]s, which are written as a single [[glyph]], with the operand on the left. For [[backwards compatibilityhistorical reasons]], the outer product operator is a [[biglyph]] denoted as <source lang=apl inline>∘.</source>, and its appears on the right.  
This syntactical inconsistency is resolved in [[J]] and [[BQN]], where the outer product operator, called Table, and denoted <source lang=j inline>/</source> and <code>⌜</code> respectively, have the usual operator syntax.  
=== Examples ===  === Examples ===  
Line 48:  Line 48:  
=== Applications ===  === Applications ===  
Outer product is useful for solving problems that intuitively  Outer product is useful for solving problems that intuitively require a [[wikipedia:Time_complexity#Polynomial_timepolynomial time]] algorithm. This may also indicate that such an algorithm is not the fastest solution.  
For example, suppose we want to find duplicated elements in an non[[nested array]]. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.  For example, suppose we want to find duplicated elements in an non[[nested array]]. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.  
Line 78:  Line 77:  
primes 20  primes 20  
2 3 5 7 11 13 17 19  2 3 5 7 11 13 17 19  
</source>  </source>  
Here there are faster solutions such as the [[wikipedia:Sieve of EratosthenesSieve of Eratosthenes]].  
== External links ==  == External links ==  
Revision as of 19:16, 6 September 2021
∘.

Outer Product (∘.
), or Table is a monadic operator, which will produce a dyadic function when applied with a dyadic function. Outer product applies the operand function on each element of the left array with each element of the right array. It can be described as a shortcut for constructing nested for loops.
Syntax
Outer Product differs from all other monadic operators, which are written as a single glyph, with the operand on the left. For historical reasons, the outer product operator is a biglyph denoted as ∘.
, and its appears on the right.
This syntactical inconsistency is resolved in J and BQN, where the outer product operator, called Table, and denoted /
and ⌜
respectively, have the usual operator syntax.
Examples
x ← 1 2 3
y ← 4 5 6
x ∘., y ⍝ visualizing outer product
┌───┬───┬───┐
│1 4│1 5│1 6│
├───┼───┼───┤
│2 4│2 5│2 6│
├───┼───┼───┤
│3 4│3 5│3 6│
└───┴───┴───┘
⍝ works for multidimensional arrays as well
y←2 3 ⍴ 'abcdef'
x←2 2 ⍴ ⍳4
x∘.,y
┌───┬───┬───┐
│1 a│1 b│1 c│
├───┼───┼───┤
│1 d│1 e│1 f│
└───┴───┴───┘
┌───┬───┬───┐
│2 a│2 b│2 c│
├───┼───┼───┤
│2 d│2 e│2 f│
└───┴───┴───┘
┌───┬───┬───┐
│3 a│3 b│3 c│
├───┼───┼───┤
│3 d│3 e│3 f│
└───┴───┴───┘
┌───┬───┬───┐
│4 a│4 b│4 c│
├───┼───┼───┤
│4 d│4 e│4 f│
└───┴───┴───┘
Applications
Outer product is useful for solving problems that intuitively require a polynomial time algorithm. This may also indicate that such an algorithm is not the fastest solution.
For example, suppose we want to find duplicated elements in an nonnested array. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.
x ← 1 2 3 2
⎕ ← matrix ← x∘.=x ⍝ compare elements with each other using equal
1 0 0 0
0 1 0 1
0 0 1 0
0 1 0 1
⎕ ← count ← +/matrix ⍝ get the number of occurence of each element
1 2 1 2
⎕ ← indices ← count ≥ 2 ⍝ get the indices of elements which occured more than once
0 1 0 1
⎕ ← duplicated ← ∪ indices/x
2
∪((+/x∘.=x)≥2)/x ⍝ everything above in one line
2
(⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ pointfree/tacit version
2
Using similar techniques, we can define a function that generates prime numbers by using an outer product of Residue.
primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.x)/x}
primes 10
2 3 5 7
primes 20
2 3 5 7 11 13 17 19
Here there are faster solutions such as the Sieve of Eratosthenes.
External links
Documentation