2

I have the following problem: There is an amount of nodes each containing elements of different kinds. Each node has a max amount of elements it can hold. I want to sort the elements between the nodes so that they are grouped by element kind, rather than scattered between all nodes. To execute the sorting I can do swaps which can exchange an amount of elements for the same amount of elements from another node. I already programmed an algorithm which finds my exit goal (a list of nodes and what elements I want them to have at the end).

Now I can generate a list of swaps in multiple ways, but I'm interested if there is some known algorithm that I can use for finding an efficient list of swaps (which means as few swaps as possible to reach my end goal)?

Example:

before sorting:
(1) A, A, A, B, C
(2) A, B, B, C, D, E, F
(3) A, C, C, D, E
sorted:
(1) A, A, A, A, A
(2) B, B, B, C, C, C, C
(3) D, D, E, E, F

example list of swaps to reach the end goal
1. (1) C     <--> (3) A
2. (2) D,E,F <--> (3) C,C,C
3. (1) B     <--> (2) A

or better (1 less swap):
1. (2) D, E, F <--> (3) A, C, C
2. (1) B, C <--> (2) A, A

The final order is something that I can calculate already and can pass it to the algorithm. I'm looking for help mostly just with generating the list of swaps. Either way here's more info on the sorting part. If there are more elements of a kind than can fit in a single node, they should be spread between multiple nodes, as few as possible. The order of elements inside nodes or even which nodes they belong to is not important, I just want them to be grouped instead of scattered.

Each node can hold a set amount of elements, different from node to node. In reality the amount of space might be larger than the amount of things it holds but I thought of the problem in a way where every space is an element (whether it has something in it or not). So an empty space might be element A, and actual things B, C etc. That simplifies thinking about it in my opinion.

2
  • 1
    Can you edit the question and elaborate on some missing details? In particular, what shall happen if there are more elements of a kind any node can take? Is the the order of the element types important? Or is the final order given as an input to the algorithm, so we don't have to solve this part of the problem? What about the maximum number of elements per node - in the example case, I assume it is equal to the initial number of elements we see - but is this always the case? Please clarify.
    – Doc Brown
    Jun 18, 2021 at 5:38
  • @DocBrown Hello. Thank you for trying to help! I edited the question and provided more context. In short yes, no need to solve that part of the problem, and yes you can assume the max amount of elements is the same as how many elements are inside since I think of empty spaces as a certain element type. Please let me know if you have any other questions. I don't quite know how to approach this problem and I'm very curious as to how other people would tackle it.
    – Mark R
    Jun 18, 2021 at 13:49

1 Answer 1

1

As far as I can see, this boils down to a graph traversal:

  • each possible node configuration is a vertex of that graph

  • each possible, nontrivial swap defines an edge in the graph

Such problems can be approached, for example, by Dijkstra`s algorithm - which is more or less a brute-force breadth-first approach, or A* search. For the latter, to guarantee the algorithm finds the minimum of swaps, one requires an admissible heuristic for the number of remaining swaps (that means, one which never overestimates the number of remaining swaps required).

If this is really practical for your case depends heavily on the total number of nodes, the number of elements per node and number of different elements in total. But even for moderate size of these numbers, the number of possible swaps can become quite huge.

This also depends on if you really need the optimal solution, or if a "good" solution is sufficient. The only admissible heuristic I can imagine right know here is the number of nodes which are sill not ordered, divided by two (rounded up in case the number of nodes is odd), since one swap can only change two nodes. Non-admissible heuristics may take into account how "different" the content of a node is from the expected content, but those will not guarantee to find the best solution in A*.

1
  • 1
    Thank you for the idea. I would have never thought to use A*/Djikstra here. Sadly I don't think this solution is viable for me, a list of all possible combinations to go through would be way too large. Currently I have a few hundred nodes, each containing up to 100 elements. I've written my own algorithm which tries to group up elements first onto nodes which already have some of its type and later a second pass just moving elements to its desired place. both passes generate swaps in order largest to smallest. Seems to work well enough for me, although no idea how efficient it is.
    – Mark R
    Jul 5, 2021 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.