We analyse the combinatorial aspect of global optimisation for multicomponent systems, which involves searching for the optimal chemical ordering by permuting particles corresponding to different species. The overall composition is presumed fixed, and the geometry is relaxed after each permutation in order to relieve local strain. From ideas used to solve graph partitioning problems we devise a deterministic search scheme that outperforms (by orders of magnitude) conventional and self-guided basin-hopping global optimisation. The search is guided by the energy gain from either swapping particles i and j (ΔEij) or changing the identity of particles i (ΔEi). These quantities are derived from the underlying (arbitrary) energy function, hence not constituting external bias, and for site-separable force fields each ΔEi can be approximated simply and efficiently. In our self-guided variant of basin-hopping, particles are weighted by an approximate ΔEi when randomly selected for an exchange, yielding a significant improvement for segregated multicomponent systems with modest particle size mismatch.