Question 375978 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Efficient algorithm for partial reordering

Consider the following array of objects:

[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]

Some of the objects contain a ptr property, referencing the v property value of an object that it should directly preceed. Two objects will never attempt to directly preceed the same object, and there will never be a loop (e.g. a->b->c->a) in the array.

Therefore, here are two possible valid rearrangements of the objects:

[
{v: 'e'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'c', ptr: 'b'},
{v: 'b'},
]

[
{v: 'c', ptr: 'b'},
{v: 'b'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'e'}
]

It doesn’t matter at all where objects appear in the output, if there is no ptr property referencing it. All that matters is that certain objects directly preceed others where the ptr property requests it.

What is a reasonably efficient algorithm to perform this kind of rearrangement?

Although the data is guaranteed to not contain loops, the rearrangement should be careful not to get into an infinite loop where it keeps rearranging the objects forever.

Note that although these examples use strings for v and ptr, the actual application will involve DOM elements as the values for v and ptr references. Therefore, the solution should only be able to compare v and ptr properties for equality.

Tags:

3

Answers


  1. 0

    Figure out which objects have another object pointing to them. Then, for each object that doesn’t have another object pointing to it, add that object and everything in the following ptr chain to the output:

    let val_to_obj = new Map();
let has_predecessor = new Set();
for (let obj of arr) {
    val_to_obj.set(obj.v, obj);
    if ('ptr' in obj) {
        has_predecessor.add(obj.ptr);
    }
}
let res = [];
for (let obj of arr) {
    if (has_predecessor.has(obj.v)) {
        continue;
    }
    while (obj !== undefined) {
        res.push(obj);
        obj = val_to_obj.get(obj.ptr);
    }
}
    Login or Signup to reply.
  2. 0

    I know this has been answered but I still want to post mine :p

    Added a few more chains for testing as well. The root of each chain is where the resulting chain will stem, so even though the chain starting at c is defined before the unchained g, the last element i is the root of chain c, thus its entire chain is positioned there.

    var st = [
    {v: 'a'},
    {v: 'f', ptr: 'e'},
    {v: 'b', ptr: 'h'},
    {v: 'c', ptr: 'b'},
    {v: 'd', ptr: 'a'},
    {v: 'e'},
    {v: 'h'},
    {v: 'g'},
    {v: 'i', ptr: 'c'}
]

function createChain(x) {
    let i = 0;
    while (i < x.length) {
        // if chaining
        if (x[i]?.ptr) {
            // find index of chained element
            let follows = x.findIndex(y => y.v == x[i].ptr);
            if (follows > -1) {
                // if element found, move it directly after current
                // decremented post-use to re-run chain on inserted element
                x.splice(i--, 0, x.splice(follows, 1)[0]);
            }
        }
        i++;
    }
    return x;
}

console.log(createChain(st));
    Login or Signup to reply.
  3. 0

    I think this is straightforward to do with sort. Put items with a ptr property matching the other item’s v property in order. If the ptr properties both exist, just compare them normally.

    const items = [
  {v: 'a'},
  {v: 'b'},
  {v: 'c', ptr: 'b'},
  {v: 'd', ptr: 'a'},
  {v: 'e'},
]

items.sort((a, b) => {
  if (a.ptr === b.v) return -1;
  if (b.ptr === a.v) return 1;
  if (a.ptr && b.ptr) return a.ptr.localeCompare(b.ptr);
  return 0;
});

console.log(items);

    Output:

    [
  { v: 'd', ptr: 'a' },
  { v: 'a' },
  { v: 'c', ptr: 'b' },
  { v: 'b' },
  { v: 'e' }
]
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search