How to find an arrangement of a sequence that has the lowest cost
Unfortunately, this problem is NP-hard, which can be seen by transforming it into a question on graphs.

To see this, construct the graph $G=(V,E)$ with $V=\{x_1,x_2,\ldots,x_n\}$, $(v,w)\in E$ for all $v,w\in V$ and a cost function $c:E\rightarrow \mathbb{R}$ given by $c((x_i,x_j)) : =f(x_i,x_j)$. Observe that any path visiting all vertices in $V$ exactly once corresponds uniquely to an arrangement of the original set.

To show NP-hardness, we must first formulate a decision problem corresponding to the optimization problem. One such formulation is:


  Given set $X$ of $n$ items and function $f:X\times X\rightarrow \mathbb{R}$ and an integer $T$, does there exist an arrangement such that the total cost of the arrangement is at most $T$?


By our discussion above, this problem is equivalent to


  Given the full graph $G=(V,E)$ (i.e. $E=V\times V$) of $n$ vertices and cost function $c:E\rightarrow \mathbb{R}$ and an integer $T$, does there exist an Hamiltonian path such that the total cost of the edges of this path is at most $T$?


This problem is very similar to the traveling salesman problem (TSP), but isn't quite the same, as that problem requires a Hamiltonian cycle instead of a path. 

However, as @j_random_hacker mentioned, this problem is in fact equivalent to the TSP problem on a different graph, namely $G'=(V',E')$ with $V' = V\cup \{z\}$, $E'=V'\times V'$ and $c'$ such that $c'(x,y)=c(x,y)$ for all $x,y\in V$ and $c(z,x)=c(x,z)=0$ for all $x\in V'$.

Therefore, the arrangement problem is indeed equivalent to TSP, which is NP-hard.



Although NP-hardness means that there are no efficient algorithms to find an exact solution, there are still heuristics that can find decent solution in reasonable time. There are many such approaches for the TSP problem. 

The fact that we know that $f$ is 'fully' non-symmetric doesn't really help, it has the same use as knowing there is no guarantee for symmetry here, which only means some approaches won't work.