Since we look for a matrix up to a symmetric permutation, we can fix the order of rows and assume that $S$ is a list and $S_i$ represents the elements of $i$-th row of $M$. Then, we can put the diagonal elements $d_i$ at positions $M_{ii}$ and define $S'_i := S_i\setminus \{d_i\}$.

Our goal is find at the placement of elements of each $S'_i$ at the non-diagonal positions of the $i$-th row of $M$. Below I describe an ILP approach to this problem.

Let $T_i$ the set of distinct elements corresponding to multiset $S'_i$ and $m_{is}$ be the multiplicity of $s$ in $S'_i$. Then let $x_{ijt}\in\{0,1\}$ for $i,j\in[n]$, $i\ne j$, and $t\in T_i$ be an indicator variable for the equality $M_{ij}=t$. The ILP problem can be posed as follows: $$\begin{cases} \sum_{t\in T_i} t x_{ijt} = \sum_{t\in T_j} t x_{jit} \qquad (1\leq i<j\leq n),\\ \sum_{t\in T_i} x_{ijt} = 1 \qquad (i,j\in [n],\ i\ne j),\\ \sum_{j=1\atop j\ne i}^n x_{ijt} = m_{it}\qquad (i\in[n],\ t\in T_i). \end{cases} $$ There is no objective function here, so any feasible solution will do the job. However, an objective function can be used to quickly check if there exist more than one solution by solving the problem with a linear objective function with random coefficients and then with the same function but negated (and to repeat this multiple times with different choices of coefficients). It should catch different solutions (if they exist) with high probability.

P.S. There is a somewhat related NP-complete problem: Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?

Since we look for a matrix up to a symmetric permutation, we can fix the order of rows and assume that $S$ is a list and $S_i$ represents the elements of $i$-th row of $M$. Then, we can put the diagonal elements $d_i$ at positions $M_{ii}$ and define $S'_i := S_i\setminus \{d_i\}$.

Our goal is find a placement of the elements of each $S'_i$ at the non-diagonal positions of the $i$-th row of $M$. Below I describe an ILP approach to this problem.

Let $T_i$ the set of distinct elements corresponding to multiset $S'_i$ and $m_{is}$ be the multiplicity of $s$ in $S'_i$. Then let $x_{ijt}\in\{0,1\}$ for $i,j\in[n]$, $i\ne j$, and $t\in T_i$ be an indicator variable for the equality $M_{ij}=t$. The ILP problem can be posed as follows: $$\begin{cases} \sum_{t\in T_i} t x_{ijt} = \sum_{t\in T_j} t x_{jit} \qquad (1\leq i<j\leq n),\\ \sum_{t\in T_i} x_{ijt} = 1 \qquad (i,j\in [n],\ i\ne j),\\ \sum_{j=1\atop j\ne i}^n x_{ijt} = m_{it}\qquad (i\in[n],\ t\in T_i). \end{cases} $$ There is no objective function here, so any feasible solution will do the job. However, an objective function can be used to quickly check if there exist more than one solution by solving the problem with a linear objective function with random coefficients and then with the same function but negated (and to repeat this multiple times with different choices of coefficients). It should catch different solutions (if they exist) with high probability.

P.S. There is a somewhat related NP-complete problem: Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?

Since we look for a matrix up to a symmetric permutation, we can fix the order of rows and assume that $S$ is a list and $S_i$ represents the elements of $i$-th row of $M$. Then, we can put the diagonal elements $d_i$ at positions $M_{ii}$ and define $S'_i := S_i\setminus \{d_i\}$.

Our goal is find at the placement of elements of each $S'_i$ at the non-diagonal positions of the $i$-th row of $M$. Below I describe an ILP approach to this problem.

Let $T_i$ the set of distinct elements corresponding to multiset $S'_i$ and $m_{is}$ be the multiplicity of $s$ in $S'_i$. Then let $x_{ijt}\in\{0,1\}$ for $i,j\in[n]$, $i\ne j$, and $t\in T_i$ be an indicator variable for the equality $M_{ij}=t$. The ILP problem can be posed as follows: $$\begin{cases} \sum_{t\in T_i} t x_{ijt} = \sum_{t\in T_j} t x_{jit} \qquad (1\leq i<j\leq n),\\ \sum_{t\in T_i} x_{ijt} = 1 \qquad (i,j\in [n],\ i\ne j),\\ \sum_{j=1\atop j\ne i}^n x_{ijt} = m_{it}\qquad (i\in[n],\ t\in T_i). \end{cases} $$ There is no objective function here, so any feasible solution will do the job. However, an objective function can be used to quickly check if there exist more than one solution by solving the problem with a linear objective function with random coefficients and then with the same function but negated (and to repeat this multiple times with different choices of coefficients). It should catch different solutions (if they exist) with high probability.

Since we look for a matrix up to a symmetric permutation, we can fix the order of rows and assume that $S$ is a list and $S_i$ represents the elements of $i$-th row of $M$. Then, we can put the diagonal elements $d_i$ at positions $M_{ii}$ and define $S'_i := S_i\setminus \{d_i\}$.

Our goal is find at the placement of elements of each $S'_i$ at the non-diagonal positions of the $i$-th row of $M$. Below I describe an ILP approach to this problem.

Let $T_i$ the set of distinct elements corresponding to multiset $S'_i$ and $m_{is}$ be the multiplicity of $s$ in $S'_i$. Then let $x_{ijt}\in\{0,1\}$ for $i,j\in[n]$, $i\ne j$, and $t\in T_i$ be an indicator variable for the equality $M_{ij}=t$. The ILP problem can be posed as follows: $$\begin{cases} \sum_{t\in T_i} t x_{ijt} = \sum_{t\in T_j} t x_{jit} \qquad (1\leq i<j\leq n),\\ \sum_{t\in T_i} x_{ijt} = 1 \qquad (i,j\in [n],\ i\ne j),\\ \sum_{j=1\atop j\ne i}^n x_{ijt} = m_{it}\qquad (i\in[n],\ t\in T_i). \end{cases} $$ There is no objective function here, so any feasible solution will do the job. However, an objective function can be used to quickly check if there exist more than one solution by solving the problem with a linear objective function with random coefficients and then with the same function but negated (and to repeat this multiple times with different choices of coefficients). It should catch different solutions (if they exist) with high probability.

P.S. There is a somewhat related NP-complete problem: Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?