Populating array with random "Pre-Defined" values , non repeating and fast

Question

My question is a performance one:

• I want to fill a N x N array, where N goes from 2 ... 10;
• The values must be from a alphabet [a,b,c], all of those are integers;
• The objective is to generate a sample of all available permutations of those arrays with that alphabet.

I want to generate 5M different unique arrays. for a arbitary N. If ( N < 4) I want to generate all of them since there are 43046721 unique combinations.

My attempts, I have tried tackling this is a myriad of ways:

Representing the matrix as a ternary number ( which it actually is). Basically I pass a integer and convert it to its ternary representation (Its slow as hell) do to the modules/divisions.

I also tried, creating a array[NxN] and the recursively loop through the alphabet changing the index I am on, which will generate all the matrices, and can't actually generate random samples when N is larger value.

I created a function that seems to be the most efficient to create a random sample when N is large: granted it generates a ton of repeated values which I tried to mitigate with the js object/hashset, since the matrice is basicly a ternary number, I can calculate the ID from the digits in the matrix.

function ipow( base,  exp)
{
    var result = 1;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}


var alphabet = [0, 1, -1];
var array = [];
var N = 4;
var repeated = 0;
var hashset = {};
var correct = 0;


for (var j = 0; j < 43046721; j++) {
    var matrixId = 0;
        array= [];
    for (var i = 0; i < N * N; i++) {
        var index = Math.floor(Math.random() * alphabet.length);
        var alph = array[index];
        array[i] = alph;
        matrixId += ipow(3,i) * index;
    } 
    if (hashset[matrixId] != null)
    {
        repeated++;
        if ( repeated < 5000000)
            j--;
    }    
    else
    {
        hashset[matrixId] = true;
        matrixId = 0;
        correct++;
    }        
}

The sample code is in JS ,but I don't honesly care , I just want to find a better/much faster way of doing this.

Answer 1

I'd prefer ternary representation approach. To overcome performance issues:

You have already spent a lot of memory to store hash table for used combinations. But it is possible to make a table with ternary representation for some number range.

Calculate this table once and use it to fill every row of your array from new generated number.

Perhaps, behavior and period of in-built random generator in JS is not very good (I don't know) - so try more advanced PRNG like Mersenne twister to diminish (neglect?) the probability of repeating the same sequence of numbers (shifted by K*number_of_rows).