JavaScript: array order by alternately selecting an object of each type

Question

I have an array of such objects (sorted by type, objects of the same type are identical):

[ { "type":"A", "height":50, "width":80 }, { "type":"A", "height":50, "width":80 }, { "type":"B", "height":20, "width":100 }, { "type":"B", "height":20, "width":100 }, { "type":"C", "height":90, "width":10 } ] 

I want to have all of these objects in an array that is ordered by alternately selecting an object of each type:

 [ { "type":"A", "height":50, "width":80 }, { "type":"B", "height":20, "width":100 }, { "type":"C", "height":90, "width":10 }, { "type":"A", "height":50, "width":80 }, { "type":"B", "height":20, "width":100 } ] 

Answer 1

You can take a Map and iterate until all the elements are processed in the correct order.

 var array = [{ type: "A", height: 50, width: 80 }, { type: "A", height: 50, width: 80 }, { type: "B", height: 20, width: 100 }, { type: "B", height: 20, width: 100 }, { type: "C", height: 90, width: 10 }], order = ['A', 'B', 'C'], types = new Map(order.map(k => [k, []])), result = []; array.forEach(o => types.get(o.type).push(o)); while (types.size) { types.forEach((a, k) => (result.push(a.shift()), a.length || types.delete(k))); } console.log(result); 

 .as-console-wrapper { max-height: 100% !important; top: 0; } 

Answer 2

Here is my attempt. This is not the most efficient, but as long as the input is not too large, it should do well.

It is assumed that the type will always be a string, but it does not assume that they will always be A, B, and C. It iterates over the input data to determine the types and collects the matching types together as "sections". Once this is completed, it iterates over the types that move entries from each section in turn, until it is done. If partitions have a different number of records that do not have a problem, but they will spend time shifting objects that do not exist.

You note that the objects of each type are identical, but I did not take this detail into account. If “identical” means “the same object” (ie obj1 === obj2 ), then you can probably use this to simply track the number of samples, rather than create all of these partition arrays.

 var input = [ { "type":"A", "height":50, "width":80 }, { "type":"A", "height":50, "width":80 }, { "type":"B", "height":20, "width":100 }, { "type":"B", "height":20, "width":100 }, { "type":"C", "height":90, "width":10 } ]; var types = []; var partitions = {}; input.forEach(function(row) { var type = row.type; if (partitions[type]) { partitions[type].push(row); } else { partitions[type] = [row]; types.push(type); } }); var output = []; while (output.length < input.length) { types.forEach(function(type) { var next = partitions[type].shift(); if (next) { output.push(next); } }); } console.log(output); 

Answer 3

Wrote a small snippet in ES6. It should be fairly easy to trace through

 const getAlternate = (ar) => { const types = []; const objects = {}; const typeCounts = {}; let totalCount = 0; ar.forEach((object) => { if(!types.includes(object.type)) { types.push(object.type); objects[object.type] = object; typeCounts[object.type] = 1; } else { typeCounts[object.type]++; } totalCount++; }); /** * at this point, the state variables will look like this: * types ['A', 'B', 'C'] * objects { A: { type: 'A', height: 50, width: 80 }, * B: { type: 'B', height: 20, width: 100 }, * C: { type: 'C', height: 90, width: 10 } } * typeCounts { A: 2, B: 2, C: 1 } * totalCount 5 * * now we can use this data to get the alternation! */ const newAr = []; let typeIndex = 0; while(totalCount > 0) { totalCount--; let type = types[typeIndex]; newAr.push(objects[type]); typeCounts[type]--; if(typeCounts[type] <= 0) { types.splice(typeIndex, 1); typeIndex--; delete objects[type]; delete typeCounts[type]; } typeIndex = (typeIndex + 1) % types.length; } return newAr } 

The first thing I do is set some state so that it is easier to iterate over types later, and this includes a list of each type, a copy of an object of each type, and an amount of each type.

From there, I declare a new array and just follow the striping using modulo, deleting everything I no longer need

 // here we invoke the function console.log(getAlternate([ { "type":"A", "height":50, "width":80 }, { "type":"A", "height":50, "width":80 }, { "type":"B", "height":20, "width":100 }, { "type":"B", "height":20, "width":100 }, { "type":"C", "height":90, "width":10 } ])); // and, as expected, we get [ {"type":"A","height":50,"width":80}, {"type":"B","height":20,"width":100}, {"type":"C","height":90,"width":10}, {"type":"A","height":50,"width":80}, {"type":"B","height":20,"width":100} ] 

Answer 4

Try this (explanation in comments)

 var inputArr = [ { "type":"A", "height":50, "width":80 }, { "type":"A", "height":50, "width":80 }, { "type":"B", "height":20, "width":100 }, { "type":"B", "height":20, "width":100 }, { "type":"C", "height":90, "width":10 } ]; //create an index by type var typeMap = {}; inputArr.forEach( function( item ){ typeMap[ item.type ] = typeMap[ item.type ] || []; typeMap[ item.type ].push( item ); }); //get sorted type-list var sortedKeyList = Object.keys( typeMap ); //assuming that keys are always going to be uppercase strings var output = []; var noMoreItems = false; //iterate till there is nothing to iterate while( !noMoreItems ) { //add the top item of every key of the map sortedKeyList.forEach( function( key ){ var arr = typeMap[ key ]; output = output.concat(arr.splice(0,1)); typeMap[ key ] = arr; }); //remove the empty array keys in the map sortedKeyList = sortedKeyList.filter( function( key ){ return typeMap[ key ].length > 0; }); noMoreItems = ( output.length == inputArr.length ); } console.log( output ); 

Answer 5

So, since you have objects arriving ordered, you can also do the following:

 function braide(a){ // get the chunks ie [a,a,a,a,a,b,b,b,c,c,d] -> [[a,a,a,a,a],[b,b,b],[c,c],[d]] var chunks = a.reduce((r,o,i,a) => a[i+1] && o.type !== a[i+1].type ? (r[r.length-1].push(o),r.push([]),r) : (r[r.length-1].push(o),r),[[]]); // find the longest chunk by appending items from every chunk at the same index position return chunks.reduce((p,c) => p.length > c.length ? p : c) .reduce((r,_,i) => (chunks.forEach(c => c[i] && r.push(c[i])),r), []); } var data = [{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"B","height":20,"width":100},{"type":"B","height":20,"width":100},{"type":"B","height":20,"width":100},{"type":"C","height":90,"width":10},{"type":"C","height":90,"width":10},{"type":"D","height":30,"width":70}]; console.log(braide(data));