Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x | /**
* @license Apache-2.0
*
* Copyright (c) 2022 The Stdlib Authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
'use strict';
// MODULES //
var resolveGetter = require( '@stdlib/array/base/resolve-getter' );
var pow = require( '@stdlib/math/base/special/pow' );
// MAIN //
/**
* Returns the Cartesian power.
*
* ## Notes
*
* - The Cartesian power is an n-fold Cartesian product involving a single array. The main insight of this implementation is that the n-fold Cartesian product can be represented as an n-dimensional array stored in row-major order. As such, we can
*
* - Compute the total number of tuples, which is simply the size of the provided array (set) raised to the specified power `n`. For n-dimensional arrays, this is the equivalent of computing the product of array dimensions to determine the total number of elements.
* - Initialize an array for storing indices for indexing into the provided array. For n-dimensional arrays, the index array is equivalent to an array of subscripts for indexing into each dimension.
* - For the outermost loop, treat the loop index as a linear index into an n-dimensional array and resolve the corresponding subscripts.
* - Continue iterating until all tuples have been generated.
*
* @param {Collection} x - input array
* @param {NonNegativeInteger} n - power
* @returns {Array<Array>} list of ordered tuples comprising the Cartesian product
*
* @example
* var x = [ 1, 2 ];
*
* var out = cartesianPower( x, 2 );
* // returns [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 2 ] ]
*/
function cartesianPower( x, n ) {
var get;
var out;
var tmp;
var idx;
var len;
var N;
var s;
var i;
var j;
var k;
N = x.length;
if ( N <= 0 || n <= 0 ) {
return [];
}
// Resolve an array element accessor:
get = resolveGetter( x );
// Compute the total number of ordered tuples:
len = pow( N, n );
// Initialize a list of indices for indexing into the array (equivalent to ndarray subscripts):
idx = [];
for ( i = 0; i < n; i++ ) {
idx.push( 0 );
}
// Compute the n-fold Cartesian product...
out = [];
for ( i = 0; i < len; i++ ) {
// Resolve a linear index to array indices (logic is equivalent to what is found in ndarray/base/ind2sub for an ndarray stored in row-major order; see https://github.com/stdlib-js/stdlib/blob/215ca5355f3404f15996fd0ced58a98e46f22be6/lib/node_modules/%40stdlib/ndarray/base/ind2sub/lib/assign.js)...
k = i;
for ( j = n-1; j >= 0; j-- ) {
s = k % N;
k -= s;
k /= N;
idx[ j ] = s;
}
// Generate the next ordered tuple...
tmp = [];
for ( j = 0; j < n; j++ ) {
tmp.push( get( x, idx[ j ] ) );
}
out.push( tmp );
}
return out;
}
// EXPORTS //
module.exports = cartesianPower;
|