A
A
antares40452021-11-02 18:46:57
JavaScript
antares4045, 2021-11-02 18:46:57

How to sort elements based on compatibility criteria?

There is a dictionary (actually a js object) that can contain thousands of elements. Each element has a set of non-normalized "wishes" to be closer to certain nodes. something like "I, id0, rate the desire to be closer to element id1 at 10 points, toward id9 at 123832 points, and toward id5 at 8". It is necessary to reorganize the structure into a ring, taking into account the wishes of proximity as much as possible (and I note that it is necessary not only to select neighbors, but to take into account the wish to be closer: that is, in this example, id5 from id0 should not be at the opposite end of the ring).
Moreover, the additional complexity is that the task (ideally) should be solved in the browser at runtime, although if necessary it can be carried away to the backend.

Most likely, there is an algorithm that solves problems of this type, but all my attempts to google something run into Google's insistent desire to sell me qsort.

in other words

{
    id0 : {
        weights: {
            id1: 10,
            id9: 123832,
            id5: 8
        }
    },
    id1: {
        weights: {
            id0 : 10
        }
    },
    id5: {
        weights: {
            id0 : 8
        }
    },
    id9 : {
        weights: {
            id0 : 123832
        }
    }
}

must be converted to any of the arrays
['id0', 'id9', 'id5', 'id1']
['id9', 'id5', 'id1', 'id0']
['id5', 'id1', 'id0', 'id9']
['id1', 'id0', 'id9', 'id5']

['id0', 'id1', 'id5', 'id9']
['id1', 'id5', 'id9', 'id0']
['id5', 'id9', 'id0', 'id1']
['id9', 'id0', 'id1', 'id5']

Answer the question

In order to leave comments, you need to log in

1 answer(s)
K
Konstantin, 2021-11-16
@antares4045

You can use the annealing method or the genetic algorithm (you can read about them on Wikipedia or search for an article on Habr). In fact, both algorithms solve the problem of maximizing / minimizing a function.
For example, you can enter a metric of how "good" a solution is. Let f(p) be the sum over all pairs of id (let's denote them as i and j) values weiht(i, j) / |i - j|​​, where weiht(i, j)is how much i "wants to be closer" to j, and |i - j|is the minimum distance between i and j in the ring. Here p is a permutation of id. Then the solution to the problem is p for which f(p) is maximal.
Unfortunately, there is one problem: annealing and / or genetic algorithm may not work, but it is likely that they will help in this task. If you don't try, you won't know)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question