Algorithm to find efficient swaps between nodes

Question

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.

Answer 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*.