Match iteration number to values of non existent Cartesian Product Array-CodePudding

Lets say we have the following arrays.

[1,2] & [1,2,3] & [1,2,3,4]

Then let's say we want to loop through all unique possible combinations of this.

The results should look something like this.

        //     IP1  IP2  IP3
        //0     0  - 0  - 0
        //1     0  - 0  - 1
        //2     0  - 0  - 2
        //3     0  - 0  - 3
        //4     0  - 1  - 0
        //5     0  - 1  - 1
        //6     0  - 1  - 2
        //7     0  - 1  - 3
        //8     0  - 2  - 0
        //9     0  - 2  - 1
       //10     0  - 2  - 2
       //11     0  - 2  - 3
       
       //12     1  - 0  - 0
       //13     1  - 0  - 1
       //14     1  - 0  - 2
       //15     1  - 0  - 3
       //16     1  - 1  - 0
       //17     1  - 1  - 1
       //18     1  - 1  - 2
       //19     1  - 1  - 3
       //20     1  - 2  - 0
       //21     1  - 2  - 1
       //22     1  - 2  - 2
       //23     1  - 2  - 3

It should produce 24 different combinations that are unique.

I can generate an array like this using the following cartersian function.

function cartesian() {
    console.log("Running cartesian()...");
    var r = [], arg = arguments, max = arg.length-1;
    
    function helper(arr, i) {
        try{
            for (var j=0, l=arg[i].length; j<l; j  ) {
                var a = arr.slice(0); // clone arr
                a.push(arg[i][j])
                if (i==max) {
                    r.push(a);
                } else
                    helper(a, i 1);
            }
        }catch(error){
            console.log(error);
        }
    }
    helper([], 0);
    return r;
};

You would call this array something like this cartesian(...array_of_arrays) which uses the spread operator to send each array in the array as an argument.

The problem with this method is this uses a large memory footprint. If the arrays start to exceed in the millions of values my applications start running out of memory and crashing. So while I could use this and simply just point to an index and know what my values would be in the Cartesian array I can't do this with large arrays.

My goal is if I choose a number like 14 for the index that it will return an array with the values [1,0,2] but without creating the array to know this to save on memory.

I created another interesting scenario to show how this might be possible. Let's say I have 3 arrays [1,2] & [1,2] & [1,2]. Now every combination might look like below.

        //     IP1  IP2  IP3
        //0     0  - 0  - 0
        //1     0  - 0  - 1
        //2     0  - 1  - 0
        //3     0  - 1  - 1
        //4     1  - 0  - 0
        //5     1  - 0  - 1
        //6     1  - 1  - 0
        //7     1  - 1  - 1

Technically if we use number 5 we could assume the binary form of it and read the bits.

This would tell us that for iteration 5 without knowing anything else that simply by it being the number 5 that the resultant array has a [1,0,1] which is the binary representation of 5 ironically enough. So if I had an array of nothing but pairs this technique could be used perhaps. Maybe this is a clue to how to solve this though.

I'm not sure what to do when the arrays are varying sizes and not always binary pairs?

To be clear I need a function that does not take an array, but instead is given 'start', 'end' & 'step' and can deduce from these what the array returned value would be from an index.

Something like: cartesianElementPosition([[start,end,step],[start,end,step],[start,end,step]],14) and this should return [1,0,2] from my example with the 24 possibilities where start end step are the rules describing how the arrays would be created without actually creating it

What is the best way to approach this?

CodePudding user response：

you can do something like this to extract the element

const cartesianElementPosition = (data, position) => {

  const arrayLengths = data.map(a => a.length)

  const positions = arrayLengths.reduceRight((pos, l) => {
    const newRemain = Math.floor(pos.remain / l)

    return {
      result: [ pos.remain % l, ...pos.result],
      remain: newRemain
    }
  }, {
    result: [],
    remain: position
  })

  return positions.result.map((p, i) => data[i][p])
}

console.log(cartesianElementPosition([[1, 2, 3], [1, 2, 3]], 2))

console.log(cartesianElementPosition([[0,1], [0,1, 2], [0,1,2,3]], 14))

CodePudding user response：

I found an elegant solution this is very efficient. This answer works well because its not creating any arrays just doing math and knowledge of the start,end,step values to account for how many entries make up the arrays.

function cartesianPositionAt(arraysOfSES,position){
  let arraySizes = [];
  let returnArray = [];
  
    for(let i=0;i<arraysOfSES.length;i  ){
    let end = arraysOfSES[i][1];
    let start = arraysOfSES[i][0];
    let step = arraysOfSES[i][2];
    let maxIterationsOfInput = parseInt((( end - start) / step   1).toFixed(2))
    arraySizes.push(maxIterationsOfInput);
  }
  
  function recurse(r_arraySizes,r_position){
    if(r_arraySizes.length>1){
      var block_size=r_arraySizes.slice(-1)[0];
        for(let j=r_arraySizes.length;j>2;j--){
        block_size = block_size * r_arraySizes[j-2];
      }
      returnArray.push(0);//@JA - Assume skip value 0
 
      while(r_position>=block_size){
        r_position = r_position - block_size
        returnArray[returnArray.length-1] = returnArray[returnArray.length-1]  1
      }
      
      r_arraySizes.shift()//remove the first item in the array.
      recurse(r_arraySizes,r_position);
    }else{ //Final section of array to process
      returnArray.push(r_position);
    }
  }
  
  recurse(arraySizes,position);
    return returnArray
}
//[start,end,step]
let data = [[1,2,1],[10,12,1],[0.86,0.89,0.01]];
let result = cartesianPositionAt(data,14);
console.log("result below");
console.log(result);

Example of the code here via JSFiddle as well: https://jsfiddle.net/gentleman_goat66/mwur5jx9/163/