Cartesian product function

[ustk]

@d-healey said in Cartesian product function:

Thanks, I need it to work with an unknown number of arrays but I think this gets me in the right direction.

I was sure of that, damn it

[d.healey]

I feel I'm getting close with this but I'm missing something. Any ideas?

const var data = [
    [1, 2, 3],
    ["dog", "cat", "fish"]
];

const var cp = cartesianProduct(data);

inline function cartesianProduct(array)
{
    local i;
    local j;
    local k;
    
    local result = [[]];

    for (i = 0; i < array.length; i++)
    {
        local subArray = array[i];
        local temp = [];
        
        for (j = 0; j < result.length; j++)
        {
            for (k = 0; k < subArray.length; k++)
            {
                concatArrays(result[j], [subArray[k]]);
                temp.push(result[j]);
            }
        }
        result = temp;
    }

    return result;
}

inline function concatArrays(a, b)
{
    local i;    
    for (i = 0; i < b.length; i++) a.push(b[i]);
}

[ustk]

@d-healey Will the inner arrays inside data have the same size?

[d.healey]

@ustk Not always.

[d.healey]

I just did a test in jsfiddle using the proper javascript concat function temp.push(result[j].concat(array[i][k])); and it worked. So I think it's something to do with the way I've implemented my concat function in HISE.

[ustk]

@d-healey Ouch...
Do you mean like:

[
[1, 2, 3],
[a, b, c, d, e, f],
[15, 16]
]

That complicates the beast a wee bit...

[d.healey]

@ustk Yeah like that.

My function works in normal JS once I swap out the concat function. You can see it here - https://jsfiddle.net/aktLe5d9/ - open your developer tools console (F12) to see the output.

[ustk]

@d-healey Found this, it may help:
https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists

[d.healey]

@ustk I found that too :) I'm currently using it to make a new concat function.

[d.healey]

Yippie, I got it working.

const var data = [
    [1, 2, 3],
    ["dog", "cat", "fish"]
];

const var cp = cartesianProduct(data);

inline function cartesianProduct(array)
{
    local i;
    local j;
    local k;
    
    local result = [[]];

    for (i = 0; i < array.length; i++)
    {
        local subArray = array[i];
        local temp = [];
        
        for (j = 0; j < result.length; j++)
        {
            for (k = 0; k < subArray.length; k++)
            {
                local c = concatArrays(result[j], [subArray[k]]);
                temp.push(c);
            }
        }
        result = temp;
    }

    return result;
}

inline function concatArrays(a, b)
{    
    local c = [];
    local i;
    
    for (i = 0; i < a.length; i++)
    {
        c[i] = a[i];
    }
    
    for (i = 0; i < b.length; i++)
    {
        c.push(b[i]);
    }
    
    return c;
}

[ustk]

@d-healey Woww! Good job man! That was a hard one!
Could I ask what for you need it?

[d.healey]

@ustk I'm trying to find ways to generate playable guitar chords. I came up with one method already but I was looking for a more efficient way and found this article which uses the cartesian product.

I just tried it in HISE but I'm getting an execution time out error. I think it's quite a slow method to implement in HISE so I'll stick with my existing function for now. Still I'm sure it will come in useful for other things in the future.

This is how it looks so far

[ustk]

@d-healey Very interesting solution indeed, although I thought there was a simpler solution (just saying, I don't know how...)
Especially since with the cartesian product solution, you have a lot of filtering to implement, apparently.

[d.healey]

My function requires filtering too.

[d.healey]

I realised I'd made a mistake implementing Pete Corey's method so I'm attempting it again.

[Natan]

@d-healey Sir David, Any Chance You Suplly The Sacles Interval Numbers?
Thanks

[d.healey]

@Natanr Not sure what you mean. In the image above it's just a C major chord, so the intervals would be 0, 4, and 7.