ObjectMutator.js: Generating All (or some subset) of Combinations an Object at the Property (or Key/Value pair) Level

Greetings, internet.  I’m in the middle of a project moving some old Qt stuff to the browser (using Javascript and React.js.)  The project isn’t all that exciting, but sometimes even the most boring projects can turn into delightful programming games and yield insights on where to increase productivity.  Case in point:  how a language’s type system can make a horrible problem much nicer in terms of programmer-time involved.  Oh, and I’m releasing code — in Javascript!  (The impatient can just go right here for the code.)

The specific problem I was required to solve was coming up with a flexible way to generate numerous combinations of a given object.  The reason I needed all these combinations was two-fold:  for genetic algorithms and for brute-force testing back-end API endpoints.  (For the purpose of discussion, I’m using problems encountered while programming in C++ as a backdrop.  If you don’t know C++, just assume the struct is sort of similar to a Javascript object.)

Framing the Problem

Consider the following problem:

You have an object with 3 members.  You initialize it to some value.  Now, you want variations of that object such that you want all possible combinations (or a subset of combinations)  for some (or even all) of the 3 members.   How do you do this?

In probability and statistics, this problem is just a straightforward application of “The Counting Rule.”  So maybe in C++, you’d have some object “Foo” like:

struct Foo {
    int a;
    float b;
    bool c;
};

Suppose Foo’s ‘a’ can take ranges between 0 through 4.  And let’s also say ‘b’ can take a range between 0 and 1 in increments of 0.2, and ‘c’ can be true or false.  To get all combinations of Foo with the mentioned constraints on ‘a’, ‘b’, and ‘c’, you would just program a set of nested for-loops, iterate over the combinations, and then add Foo to some list-like structure and use the combinations.  But what happens if another programmer comes along and changes your code so that it’s now this:

struct Foo {
    int a;
    float b;
    bool c;
    std::complex<float> d;
};

Now what?  Well, if you want the existing program to work but also want to support the ability to generate all combinations of Foo including ‘d’, you’d have to add another loop to generate the next level of combinations for the set of values ‘d’ can take.  If this structure (‘Foo’) changes often in your code at the hands of many developers, then you have a nuisance on your hands in terms of maintenance.  It would be nice to generalize this behavior for a general object.

Being able to “look inside” an object and figure out its composition is referred to as reflection.  People who’ve been using C++ for years probably recognize that, since the language hasn’t historically had good support for reflection, it’s often been painful to implement code that deals with objects in a very general way.  More specifically, it hasn’t been easy to look at the contents of a given object, enumerate the properties, and generate general code based on knowledge of those properties.  People have been working around these problems for years (with things like meta-object compilers, interface description languages, protobufs for message encoding, etc.)  The truth is that reflection is just not that easy in C++.  (In fact, this thorough and insightful article by Jackie Kay details the problem quite nicely.  While I haven’t looked into specifics, it does seem as if there is hope for the future.)

During my porting project, the not-so-easy-to-reflect element of C++ essentially “went away” when I moved my code to Javascript.  While I was using Qt, not all of the objects I was using were Qt objects.  In fact, they were generated by yet another tool that had no awareness of the meta-object system.  For my needs, re-coding functions whenever an object’s composition  changed was quickly turning into a serious maintenance headache.  It was one of those times where I was happier to be using Javascript than C++.  Performance not being necessary, Javascript was a much more natural choice.

Easy Mode:  Enter Javascript

Javascript’s objects are effectively dictionaries.  That’s it.  You have an object.  You can enumerate the keys of that object, and those keys essentially tell you the members of the object.  So, given the following:

let lala = { a: 1, b: 2, c: 3 }

You can figure out all the members simply by:

Object.keys( lala ); // Gives [ 'a', 'b', 'c' ]

Obviously, this is a lot easier than having some kind of meta-object compiler or framework and fishing around for information about an object.  What I needed was a generalized way to enumerate properties and generate combinations of an object’s member variables.

Since my first use case was a form of genetic algorithm, I’m going to discuss my solution in biological terms:

Given some object (chromosome) (… e.g, { a: 0, b: 1, c: 2 }) , I wanted to be able to generate all versions (mutations) of the object (chromosome) where I could specify a bunch of values for ‘a’, a bunch of values for ‘b’, and so on and so forth until all combinations were generated.  I also wanted the ability to leave some properties alone or untouched (unmutated.)  Finally, given that there could be relationships between properties and that some combinations (invalid mutations) were not permissible, I also wanted a cull function to loop through the result set and get rid of invalid combinations (chromosomes).

So for example (a very contrived example), given a simple object:

{a:0,b:0,c:12}

Suppose I wanted ‘a’ from range [0,2) and ‘b’ from [5,7), I would want results like this:

{a: 0, b: 5, c: 12}
{a: 0, b: 6, c: 12}
{a: 1, b: 5, c: 12}
{a: 1, b: 6, c: 12}

To accomplish this, I wrote ObjectMutator.js.  Using ObjectMutator.js, I simply had to do this:

let chromosome = {
    a: 0,
    b: 0,
    c: 12,
};

let mutationGroup = [
    { gene: "a", start: 0, checkRange: (i) => (i < 2 ), step: (i) => i+1 },
    { gene: "b", start: 5, checkRange: (i) => ( i < 7 ), step: (i) => i+1 }
];

let mutationBag = new Mutator( chromosome, mutationGroup );
console.log( mutationBag.mutations );

The output is then (from VS Code’s debug console):

Array(4) [Object, Object, Object, Object]
index.js:64
length:4
__proto__:Array(0) [, …]
0:Object {a: 0, b: 5, c: 12}
1:Object {a: 0, b: 6, c: 12}
2:Object {a: 1, b: 5, c: 12}
3:Object {a: 1, b: 6, c: 12}

To keep it simple, I didn’t use the ability to filter unwanted mutations.  For example, you could remove all mutations where the member ‘a’ was greater than ‘b’ by passing in a culling function to be used in a final filter pass (Array’s filter()).

The code for Mutator is below.  I had three parameters:  a chromosome, a mutation group defining the range of mutations, and a cull function for filtering out invalid chromosomes as a result of the mutations (not used above).  I  took advantage of how Javascript objects worked and wrote some code to generate my mutations — below.  (Note that I am not as deeply versed in the pros and cons of various javascript approaches, so you’re welcome to provide optimizations and feedback in the comments.  I’d appreciate it!)

class Mutator {
    /**
     * @constructs Mutator
     * @description Constructs mutator object
     * @param {chromosome} The base object that gets mutated
     * @param {mutationGroup} The set of (joint) mutations to apply to a chromosome
     * @param {cullFunction} The function passed to a filter to remove any invalid/unwanted genes in the mutation set
     */
    constructor( chromosome, mutationGroup, cullFunction ) {
        this.mutations = [];     
        this.chromosome = chromosome;

        this.assertGenesToMutatePresent( mutationGroup );
        function generateMutations( chromosome, mutationGroup ) {
            function internalGenerateMutations( mutationGroup ) {
                let mutationGroupClone = mutationGroup.slice(0);
                let frameGene = mutationGroupClone.shift();
                
                let nextGeneration = [];
                for( let i = frameGene.start; frameGene.checkRange(i); i = frameGene.step(i) ) {
                    if( mutationGroupClone.length > 0 ) {
                        let subMutations = internalGenerateMutations( mutationGroupClone );
                        nextGeneration.push.apply( nextGeneration, subMutations.map( (submutation ) => {
                            submutation[ frameGene.gene ] = i;
                            return submutation;
                        }));
                    } else {
                        let mutation = {};
                        mutation[ frameGene.gene ] = i;
                        nextGeneration.push( mutation );
                    }
                }
                return nextGeneration;
            }
    
            let baseMutations = internalGenerateMutations( mutationGroup );
            return (baseMutations.map( (value) => {
                return {
                    ...chromosome,
                    ...value
                };
            }));
        };

        this.mutations = (typeof( cullFunction ) === 'function') ?
            generateMutations( chromosome, mutationGroup ).filter( cullFunction ) :
            generateMutations( chromosome, mutationGroup );
    }

    /**
     * @function assertGenesToMutatePresent
     * @memberOf Mutator
     * 
     * @param {mutationGroup} Mutation group that needs to be checked
     */
    assertGenesToMutatePresent( mutationGroup ) {
        mutationGroup.forEach(element => {
            if( !this.chromosome.hasOwnProperty( element.gene ) )
                throw Error( `Missing gene ${ element.gene }` );
        });
    }
};

Hopefully, you find some utility in this blog post.  If you find any bugs or have pull requests, let me know.