JAVASCRIPT reorder an array by group of consecutive values

Question

I'm looking for a way to reorder an array by a set of consecutive fixed values. For example:

I have got an array of items:

items = [
  {id: 1, name: "Test 1", group: 1},
  {id: 2, name: "Test 2", group: 2},
  {id: 3, name: "Test 3", group: 2},
  {id: 4, name: "Test 4", group: 2},
  {id: 5, name: "Test 5", group: 1},
  {id: 6, name: "Test 6", group: 2},
  {id: 7, name: "Test 7", group: 1},
  {id: 8, name: "Test 8", group: 3},
  {id: 9, name: "Test 9", group: 1},
  {id: 10, name: "Test 10", group: 3}
];

I know also that I've got three groups:

groups = [
  {id: 1, name: "Group 1"},
  {id: 2, name: "Group 2"},
  {id: 3, name: "Group 3"}
];

And what I want to do looks like to that:

new_array = [
 {id: 1, name: "Test 1", group: 1},
 {id: 2, name: "Test 2", group: 2},
 {id: 8, name: "Test 8", group: 3},
 {id: 5, name: "Test 5", group: 1},
 {id: 3, name: "Test 3", group: 2},
 {id: 10, name: "Test 10", group: 3}
 {id: 7, name: "Test 7", group: 1},
 {id: 4, name: "Test 4", group: 2},
 {id: 9, name: "Test 9", group: 1},
 {id: 6, name: "Test 6", group: 2},
];

I want to sort my array by "group" of 3 items following the order of group 1, 2, 3

Would you know a smart way of doing this ? I don't know where to start...

http://stackoverflow.com/questions/1129216/sort-array-of-objects-by-string-property-value-in-javascript is your starting point — epascarello, Jul 27 '16 at 18:57
@epascarello I don't see how that question would help at all. — user94559, Jul 27 '16 at 19:09
@smarx really? It seems blatantly on topic.. Sorting arrays of objects by a sub-property? You could try the same compare method to implement the sorting algorithm. — dckuehn, Jul 27 '16 at 19:28
@dckuehn But the sort here isn't by a property... the goal is to alternate among the groups (skipping as necessary for smaller groups). I could just be missing the suggested algorithm, now that two people have said it's related. If you can think of a way to use a `sort` with a custom comparator here, would you mind posting it as an answer? — user94559, Jul 27 '16 at 19:31
@smarx Well, I blatantly mis-interpreted the question. I mis-read the desired results. I do think it's still possible to implement a sort, but I'll have to think about it much more than I thought. Might be fun! — dckuehn, Jul 27 '16 at 19:48
Looks to me like you would want to group the results in separate arrays first, then loop through and `push` one from each group to a new array on each cycle. — brichins, Jul 27 '16 at 20:01

user94559 · Answer 1 · 2016-07-27T19:42:32.627

var items = [
  {id: 1, name: "Test 1", group: 1},
  {id: 2, name: "Test 2", group: 2},
  {id: 3, name: "Test 3", group: 2},
  {id: 4, name: "Test 4", group: 2},
  {id: 5, name: "Test 5", group: 1},
  {id: 6, name: "Test 6", group: 2},
  {id: 7, name: "Test 7", group: 1},
  {id: 8, name: "Test 8", group: 3},
  {id: 9, name: "Test 9", group: 1},
  {id: 10, name: "Test 10", group: 3}
];

// grouped will map group IDs to arrays of items
// e.g. { '1': [ { id: 1, name: 'Test 1', group: 1 }, ... ], '2': ... }
var grouped = {};

for (var i = 0; i < items.length; i++) {
  var item = items[i];
  if (grouped[item.group] === undefined) {
    grouped[item.group] = [];
  }
  grouped[item.group].push(item);
}

// definition of groups and their order
var groups = [
  {id: 1, name: "Group 1"},
  {id: 2, name: "Group 2"},
  {id: 3, name: "Group 3"}
];

// we'll start with the first group
var groupIndex = 0;

var output = [];
for (var i = 0; i < items.length; i++) {
  // skip any empty groups
  while (grouped[groups[groupIndex].id].length === 0) {
    groupIndex = (groupIndex + 1) % groups.length;
  }

  // pull the first item from the group and add it to our output
  output.push(grouped[groups[groupIndex].id].shift());

  // move to the next group
  groupIndex = (groupIndex + 1) % groups.length;
}

console.log(output);
// Output:
// [ { id: 1, name: 'Test 1', group: 1 },
//   { id: 2, name: 'Test 2', group: 2 },
//   { id: 8, name: 'Test 8', group: 3 },
//   { id: 5, name: 'Test 5', group: 1 },
//   { id: 3, name: 'Test 3', group: 2 },
//   { id: 10, name: 'Test 10', group: 3 },
//   { id: 7, name: 'Test 7', group: 1 },
//   { id: 4, name: 'Test 4', group: 2 },
//   { id: 9, name: 'Test 9', group: 1 },
//   { id: 6, name: 'Test 6', group: 2 } ]

EDIT

Here's an alternative solution, using lodash:

var grouped = _.groupBy(items, function (item) { return item.group; });
var groupLists = _.map(groups, function (group) { return grouped[group.id]; });
var output = _.filter(_.flatten(_.zip.apply(null, groupLists)));
console.log(output);

score 0 · Answer 2 · answered Jul 27 '16 at 19:50

A solution using underscore for grouping.

Step 1: group
Step 2: sort each group by id
Step 3: pop from each group in order to resultant array

EXAMPLE:

I've shuffled your items to confirm that grouping is in ascending order of id even if not at the source.

items = [
  {id: 1, name: "Test 1", group: 1},
  {id: 3, name: "Test 3", group: 2},
  {id: 4, name: "Test 4", group: 2},
  {id: 6, name: "Test 6", group: 2},
  {id: 2, name: "Test 2", group: 2},
  {id: 9, name: "Test 9", group: 1},
  {id: 10, name: "Test 10", group: 3},
  {id: 5, name: "Test 5", group: 1},
  {id: 7, name: "Test 7", group: 1},
  {id: 8, name: "Test 8", group: 3}
];
var grouped = _.groupBy(items, function(obj) {
  return obj.group;
});

for (var index in grouped) {
  var attr = grouped[index];
  attr.sort(function(a, b) {
    return (a.id - b.id);
  });
}
var res = [];
for (var i = 0; i < items.length; i++) {
  for (var index in grouped) {
    if (grouped[index].length > 0) {
      res.push(grouped[index].shift());
    };

  }
}
console.log(res);

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

Arnauld · Accepted Answer · 2016-07-27T19:58:36.080

For reasonably small sets of data, you may want to go with a simple algorithm such as this one. Just keep in mind that findIndex() and splice() are rather costly methods, though.

var items = [
      {id: 1,  name: "Test 1",  group: 1},
      {id: 2,  name: "Test 2",  group: 2},
      {id: 3,  name: "Test 3",  group: 2},
      {id: 4,  name: "Test 4",  group: 2},
      {id: 5,  name: "Test 5",  group: 1},
      {id: 6,  name: "Test 6",  group: 2},
      {id: 7,  name: "Test 7",  group: 1},
      {id: 8,  name: "Test 8",  group: 3},
      {id: 9,  name: "Test 9",  group: 1},
      {id: 10, name: "Test 10", group: 3}
    ],
    groups = [
      {id: 1, name: "Group 1"},
      {id: 2, name: "Group 2"},
      {id: 3, name: "Group 3"}
    ];

var res = [], i, n;

for(n = 0; items.length; n = (n + 1) % groups.length) {
  if((i = items.findIndex(function(v) { return v.group == groups[n].id; })) != -1) {
    res.push(items.splice(i, 1));
  }
}

// displaying formatted output
console.log(JSON.stringify(res).split('}],').join('}],\n'));

Thomas · Answer 4 · 2016-07-27T21:23:58.273

//init positions by groupId
var positionsByGroupId = {}, numGroups = groups.length;
groups.forEach(({id}, i) => { positionsByGroupId[id] = i });

//compute the position of each item in the sorted Array.
//compose the item with the computed value we are sorting by
items.map(item => {
    return {
        value: item,
        //get value and update the index for this group
        //since we use this value only for sorting, it doesn't matter 
        //that it is actually offset by one row
        position: positionsByGroupId[ item.group ] += numGroups 
    }
})
//sort by the position, to get the right order
.sort((a, b) => a.position - b.position)
//return the ordered items
.map(obj => obj.value);

Imagine a grid where the columns represent your groups. If you now unroll this grid, row by row, you get the order you're asking for. A bit like smarx explained: group and zip.

But we can do that without actually grouping the items, because we can calculate their index in the output as col + row * numColumns. Since the columns may not be entirely filled, these position may not match the actual output-index, but we can still use them to determine the order of the items.

But how do we know the position of each item, the input-array is shuffled. We store the indices by column, and track/update these indices as we iterate over the input-array, by incrementing the index for this group by the number of columns/groups.

Edit: I'm not sure wether this is entirely clear, but the majority of this code is a sort-by-computed-value, so if you use some lib that supports that, like lodash for example, you can shorten it to:

var positionsByGroupId = {}, numGroups = groups.length;
_.forEach(groups, ({id}, i) => { positionsByGroupId[id] = i });
_.sortBy(items, item => positionsByGroupId[ item.group ] += numGroups);

JAVASCRIPT reorder an array by group of consecutive values

4 Answers4