Ordering permutations in javascript

Question

I have objects that have such fields id and position.

const items = [{id: 11, position: 1}, {id: 12, position: 2}, {id: 13, position: 3}, {id: 14, position: 4}, {id: 15, position: 5}, {id: 16, position: 6}];

These items are basically folders stacked one on top of another, it's possible to move these folders relative to each other which means changing their position property.

I need a function like this:

const moveDir = (idIn: number, idOut: number, currentList: Dir[]): Dir[] => {
    // some code;
    return;
}

that would return a new list of folders after the change has taken place. As for the idIn and idOut params: I want to drag a folder with id idIn to the position of a folder with id idOut.

Example:

--------
Folder 1
--------
Folder 2
--------
Folder 3
--------
Folder 4
--------
Folder 5
--------

If idIn = 2, idOut = 4, the result should be:

--------
Folder 1
--------
Folder 3
--------
Folder 4
--------
Folder 2
--------
Folder 5
--------

If idIn = 4, idOut = 2, the result should be:

--------
Folder 1
--------
Folder 4
--------
Folder 2
--------
Folder 3
--------
Folder 5
--------

Any ideas on how to implement that behaviour would be helpful.

EDIT:

The initial list of objects looks like this:

const items = [{id: 11, position: 1}, {id: 12, position: 2}, {id: 13, position: 3}, {id: 14, position: 4}, {id: 15, position: 5}];

I know items ids and if I want to change two of them, I should be able to pass the ids of those items the positions of which I want to change.

The edited example:

--------
Folder 1 (id = 11, position = 1)
--------
Folder 2 (id = 12, position = 2)
--------
Folder 3 (id = 13, position = 3)
--------
Folder 4 (id = 14, position = 4)
--------
Folder 5 (id = 15, position = 5)
--------

If I change Folder 2 and Folder 4, it means idIn = 12 and idOut = 14.

The result should be:

--------
Folder 1 (id = 11, position = 1)
--------
Folder 3 (id = 13, position = 2)
--------
Folder 4 (id = 14, position = 3)
--------
Folder 2 (id = 12, position = 4)
--------
Folder 5 (id = 15, position = 5)
--------

That's the function should return this list (ordered by position):

[{id: 11, position: 1}, {id: 13, position: 2}, {id: 14, position: 3}, {id: 12, position: 4}, {id: 15, position: 5}];

Btw your samples are missing folder 6 and you have ids with the same value which is quite odd. — F. Müller, Jul 01 '20 at 16:24
Yeah, that's what I suspected. I just noticed it while I was looking at my result and thought that I made a mistake haha. — F. Müller, Jul 01 '20 at 16:31
haha yeah sorry, my bad...by the way, I've just run a few tests and yet something strange happens when you set `idIn=4` and `idOut=2`, that's to say, when we drag the fourth folder to the position of the second one. Would you please check it out? — Albert, Jul 01 '20 at 16:34

F. Müller · Answer 1 · 2020-07-01T21:14:28.473

My solution is just pure javascript. But as typescript will be compiled down to javascript in the end, it might just work with a few modifications. I am not sure if this is the best way of doing it, but it certainly works:

const items = [
    {id: 11, position: 1},
    {id: 12, position: 2},
    {id: 13, position: 3},
    {id: 14, position: 4},
    {id: 15, position: 5},
    {id: 16, position: 6}
];
        
const moveDir = function(idIn, idOut, currentList) {
    const list = [...currentList]; // clone, we don't want the original array to be edited
    const copyEl = list[idIn - 1];
    list.splice(idOut, 0, copyEl); // insert the folder to copy at index idOut
    // we have to differ the delete index here
    // because when we add an element before the copied element the index goes up 1 - otherwise it stays
    const deleteIndex = idIn > idOut ? idIn : idIn - 1;
    list.splice(deleteIndex, 1);
    return list;
}

const result = moveDir(2, 4, items);
const result2 = moveDir(4, 2, items);
console.log('result', result);
console.log('result2', result2);

<!DOCTYPE html>
<html>
<head>
    <meta http-equiv="charset" charset="UTF-8">
</head>
<body>
</body>
</html>

EDIT

The only struggle I had was that I could not deep clone the freaking array with objects in it (blame js!). I found a workaround for this issue that does not rely on JSON.parse(). Just to provide an alternative.

const items = [
    {id: 11, position: 1},
    {id: 12, position: 2},
    {id: 13, position: 3},
    {id: 14, position: 4},
    {id: 15, position: 5}
];

const toArray = function(obj) {
    let array = [];
    for (const [key, value] of Object.entries(obj)) {
        array[key] = [value.id, value.position];
    }
    return array;
}

const toObjectArray = function(obj) {
    let objectArray = [];
    for (let i = 0; i < obj.length; i++) {
        objectArray[i] = {id: obj[i][0], position: i + 1};
    }
    return objectArray;
}

const getItemById = function(id, list) {
    for (let i = 0; i < list.length; i++) {
        const item = list[i];
        if (item[0] === id) {
            return [item, i];
        }
    }
}

const moveDir = function(idIn, idOut, currentList) {
    if (idIn !== idOut) {
        // we convert the objects inside currentList to an array to ensure a deep clone
        const arrayList = toArray(currentList);

        // first, we fetch the object that we want to clone
        const itemToCopy = getItemById(idIn, arrayList);
        const itemToCopyRef = itemToCopy[0];
        const itemToCopyIndex = itemToCopy[1];

        // next, we fetch the object that we want to inject our moving object to
        const itemDestination = getItemById(idOut, arrayList);
        const itemDestinationIndex = itemDestination[1];

        // we add the object at index of the destination + 1 because it should be injected right after
        arrayList.splice(itemDestinationIndex + 1, 0, itemToCopyRef);

        // we delete the object at the previous position
        const deleteIndex = itemToCopyIndex > itemDestinationIndex ? itemToCopyIndex + 1 : itemToCopyIndex;
        arrayList.splice(deleteIndex, 1);

        // convert back to an array of objects and update the position aswell
        return toObjectArray(arrayList);
    }
}

const result = moveDir(12, 14, items);
const result2 = moveDir(14, 12, items);
console.log('result', result);
console.log('result2', result2);

<!DOCTYPE html>
<html>
<head>
    <meta http-equiv="charset" charset="UTF-8">
</head>
<body>
</body>
</html>

I don't get what's happening :)) maybe it's my bad and I was not clear enough when explaining the issue....look, let's say `idIn = 2` and `idOut = 4`, basically it means that we are moving the second folder to the position of the fourth one. In case with the numeration chosen above it means that we're moving the folder with the `id = 12` to the place of the folder with `id = 14`. In this case the result (ordered by position) should be this: `[{id: 11, position: 1}, {id: 13, position: 2}, {id: 14, position: 3}, {id: 12, position: 4}, {id: 15, position: 5}, {id: 16, position: 6}]`. — Albert, Jul 01 '20 at 17:21
The folders 1, 2, 3, 4, 5 are just names, they can be anything and have no relation to the numeration. I just decided to name them with numbers cos it seemed easier to explain what I need. — Albert, Jul 01 '20 at 17:21
@Albert Ok well then the order is correct, but the position attribute needs to be updated as well. I can do that. But why would you need this info? You already know it -> the array is in the correct order it implies the position unless the position has a different meaning to you. — F. Müller, Jul 01 '20 at 17:45
Gosh...I got stupid by the end of the day and confused everything...partly cos I copy pasted a piece of code from the course and the rest just typed on the site and it got mixed...I got back to this issue , took a look at the code and realised that I was explaining it all wrong, `idIn` and `idOut` should be folders ids, namely , not 2 and 4, but 12 and 14. I'm sorry, it was a crazy day... — Albert, Jul 01 '20 at 18:01
@Albert Don't worry. Please update your post and provide 1 perfect example of how it should look like otherwise we might end up with something different. — F. Müller, Jul 01 '20 at 18:06
@F.Muller: const list = [...currentList]; This is ok for ['a','b','test','bla']. But wont work for [{id: 11, position: 1}, {id: 13, position: 2}]. A bug will occur when you modify the clone and you expect the original not to be modified. The solution is to do a deep copy when you are cloning an array of objects. To do a deep copy of an object we can use cloneDeep from 'loadash'. Or pure vanila one line solution could be JSON.parse(JSON.stringify(currentList)). — Rahul Singh, Jul 01 '20 at 18:21
@RahulSingh Yeah, I just did some research about 20 min ago. Did not know that. Well my workaround was to duplicate items. Does typescript take care of this? (have not updated the answer yet, cause OP said he explained something wrong so I will adapt later). — F. Müller, Jul 01 '20 at 18:30
No it does'nt. But there are several ways of doing it.(I personally prefer "cloneDeep"). Reference,in case you like to read: ]https://stackoverflow.com/questions/597588/how-do-you-clone-an-array-of-objects-in-javascript — Rahul Singh, Jul 01 '20 at 18:37

score 0 · Accepted Answer · edited Jul 01 '20 at 20:34

0

Added a javascript code(not the cleanest implementation though). I am updating all other positions too after inserting the required object at the correct position.

const moveDir = (idIn, idOut, currentList) => {
    if (idIn === idOut)
        return currentList;
    let list = JSON.parse(JSON.stringify(currentList));
    const find1 = list.find((obj) => obj.position == idIn);
    list = list.filter(function (obj) {
        return obj.position != idIn;
    });
    find1.position = idOut;
    list.splice(idOut - 1, 0, find1);
    list.forEach(function (obj, index) {
        if (idIn > idOut) {
            if (index >= idOut && index < idIn)
                obj.position++;
        }
        else {
            if (index >= idIn - 1 && index < idOut - 1)
                obj.position--;
        }
    });
    return list;
};
const items = [{ id: 11, position: 1 }, { id: 12, position: 2 }, { id: 13, position: 3 }, { id: 14, position: 4 }, { id: 15, position: 5 }, { id: 16, position: 6 }];

   // const result1 = moveDir(2, 4, items);
//const result2 = moveDir(4, 2, items);
//Code edited for changes in question.Just get the index from ids 
const index1 = items.findIndex(x => x.id == 12);
const index2 = items.findIndex(x => x.id == 14);
const result1 = moveDir(index1+1, index2+1, items);

const result2 = moveDir(index2+1, index1+1, items);
console.log("result1 is" + JSON.stringify(result1));
console.log("result2 is" + JSON.stringify(result2));

<!DOCTYPE html>
<html>
<head>
    <meta http-equiv="charset" charset="UTF-8">
</head>
<body>
</body>
</html>

edited Jul 01 '20 at 20:34

Wai Ha Lee

8,598
83
57
92

answered Jul 01 '20 at 16:38

Rahul Singh

690
1
5
10

it's closer to what I need, yeah but there's still a bug, I've run just one test, namely if I pass `idIn = 2` and `idOut = 4`, the object with `position = 2` is missing. – Albert Jul 01 '20 at 17:24
oh and just in case, please check my comments under another answer, just for the sake of clearness of my explanation. – Albert Jul 01 '20 at 17:25
Will chack and revert..Thanks!! – Rahul Singh Jul 01 '20 at 17:29
@Albert :Please check if it works....I am editing the same source list. – Rahul Singh Jul 01 '20 at 17:39
Gosh...I got stupid by the end of the day and confused everything...partly cos I copy pasted a piece of code from the source and the rest just typed on the site and it got mixed...I got back to this issue , took a look at the code and realised that I was explaining it all wrong, `idIn` and `idOut` should be folders ids, namely , not 2 and 4, but 12 and 14. So it works almost as expected but the factual params should be folders ids. The result is correct. – Albert Jul 01 '20 at 18:01
No worries..Could you please accept the answer in that case...Also FYI, to clone a list of objects,(say[...currentList] in your example) won't work.This is ok for [1,2,'test','bla'].But wont work for [{a:1}, {b:2}]). To do a deep copy you can use external library like "cloneDeep" from loadsh. – Rahul Singh Jul 01 '20 at 18:15
@Albert : Have updated the answer for the changes in requirements. Please check!! – Rahul Singh Jul 01 '20 at 19:43
@Oh, yeah, no problem. Thank you, Lemme run a few tests. – Albert Jul 01 '20 at 19:47
1

@Albert I have also updated my answer. Looks like I am too late after all ... but you may want to look at it. I use a non-JSON approach. – F. Müller Jul 01 '20 at 20:26
@F.Müller yep =( but I will check it out, by the way yesterday I've implemented it in my own way and posted here, don't know if it's worse or better, gonna figure this out later. I will need to run performance tests on all the solutions. – Albert Jul 02 '20 at 12:36
@Albert When you do the performance tests. You also have to take into consideration multiple function calls (e.g. call moveDir(12, 14) and call moveDir(14, 12)) with the same items reference -> otherwise the action is permanent on each call -> you need to copy the items array in a way. For the tests I used: console.time('bla') and console.timeEnd('bla'). – F. Müller Jul 02 '20 at 13:02
@F.Müller Ah, yeah apparently! I will surely take care of that. When I've done them I will try to post them here. – Albert Jul 02 '20 at 13:52

score 0 · Answer 3 · answered Jul 02 '20 at 12:32

Here is my implementation (not the cleanest though):

const items = [
    {id: 11, position: 1},
    {id: 12, position: 2},
    {id: 13, position: 3},
    {id: 14, position: 4},
    {id: 15, position: 5},
];

const changePositionOrder = (idIn, idOut, items) => {
    if (idIn === idOut) return items;
    const inItem = items.find(item => item.id === idIn);
    const withExcluded = items.filter(item => item.id != idIn).map(
                item => {
                    if (item.id > idIn) {
                        item.position--;
                    }
                    return item;
                }
            );
    const outItem = withExcluded.find(item => item.id === idOut);
    inItem.position = outItem.id > idIn ? outItem.position + 1 : outItem.position;
    items = withExcluded.map(item => {
        if (item.position >= inItem.position) item.position++;
        return item;
    });

    items.push(inItem);

    return items;
};

console.log(changePositionOrder(12, 15, items).sort((a, b) => a.position - b.position));

Ordering permutations in javascript

3 Answers3