Solving the "Reverse" Assignment Problem with an Added Constraint?

Question

Note: This is a continuation of my previous question, found here

As written, my previous question was too unconstrained: @BaderAbuRadi showed that depending on the $C$ chosen, there can be multiple valid assignments that all have the same sums, no matter the $f$ chosen.

To remedy this (and to avoid endless UPDATES to the previous question), I want to add an additional constraint on $C$: for a given $a$, there is exactly one $y \in T$ where $C(a,y)=1$; similarly, for a given value of $b$, there is exactly one value of $x \in A$ there $C(x,b)=1$.

The motivation behind these two questions is an attempt at solving the formalization of a problem where you are trying to line a group of objects in a pre-determined sequence, but you are only told how many objects are in the correct locations (it's like Wordle, but if all squares are either yellow or green, and you only know how many squares are green, but not which squares are green. You could also think of this as a modified version of the Mastermind game, where there are no white pegs (this was brought up in a comment by @justhalf in the original question)).

My Approach:

Building off the "it's Wordle" approach, one (not neccessarily optimal) approach is to simply enumerate all possible sequences, and as guesses are made, remove any sequence that does not match the "scores" provided so far. Guesses should be chosen so that is eliminates the largest number of possible sequences.

Answer 1

Let $|S|=|T|=n$. Rename the elements of $S $ and $T$ to be $1,...,n$. Then our equations are

$$ \forall \sigma\in S_{n}:\quad \sum_{i=1}^{n} \underbrace{C(i,\sigma(i))}_{:=x_{i,\sigma(i)}}= c_\sigma $$

, and $x_{i,j}$ are our unknowns.

Using your additional conditions $$\forall i:\exists!j:\quad x_{i,j}=1$$ and $$\forall j:\exists!i:\quad x_{i,j}=1$$ we define a permutation $\sigma^*\in S_n$ as follows: For each $i\in[n]$ let $\sigma^*(i)$ be the unique $j\in[n]$ which fulfills $x_{i,j}=1$.

Note that with this, $x_{1,\sigma^*(1)}=...=x_{n,\sigma^*(n)}=1$ and all other unknowns are 0.

So finding $\sigma^*$ gives the values of all unknowns.

---

Now, let's compute $\sigma^*$.

Pick a permutation $\sigma\in S_n$.

Next fix $i,j\in[n]$ with $j\neq i$ and define $\sigma'$ via $\sigma$ by swapping the values $\sigma(i)$ and $\sigma(j)$: $$ \sigma'(z):= \begin{cases} \sigma(z)&,&\text{if } z\notin \{i,j\} \\ \sigma(i)&,&\text{if } z=j \\ \sigma(j)&,&\text{if } z=i \end{cases} $$

Then $$c_{\sigma}-c_{\sigma'} = \sum_{i=1}^n x_{i,\sigma(i)}- \sum_{i=1}^n x_{i,\sigma'(i)} = x_{i,\sigma(i)}+x_{j,\sigma(j)}- x_{i,\sigma(j)}-x_{j,\sigma(i)} \tag{1}$$

Per your restriction, if $x_{i,\sigma(i)}=1$, then we must have $x_{i,\sigma(j)}=0$, and similarly $x_{j,\sigma(j)}=1\Rightarrow x_{j,\sigma(i)}=0$.

So if you try out $n^2$ permutations $\sigma_1,...,\sigma_{n^2}\in S_n$ such that $\bigcup_{k=1}^{n^2} \sigma_k(\{i,j\}) = [n]^2$ (i.e. $(\sigma_k(i),\sigma_k(j))$ runs over all pairs in $[n]^2$), you will find one such permutation $\sigma_{k^*} $ among them for which (1) sums to 2, and with that you will have found two values of $\sigma^*$, namely $\sigma^*(i)=\sigma_{k^*}(i)$ and $\sigma^*(j)=\sigma_{k^*}(j)$

You'll have to repeat this $n/2$ times for the remaining choices for $i$ and $j$, so you can determine $\sigma^*$ in $\mathcal O(n^3)$.

Answer 2

Let's reformulate this problem as ordering $n$ distinct balls in a particular sequence $b$ --- you do not know what $b$ is, but given an attempt $a$, you are given a "score" $S$, which is equal to the number of indices $1 \le i \le n$ where $a[i]=b[i]$. Our goal is to find an $a$ such that $S=n$ (this would also mean that $a$ is equal to $b$). We will assume that calculating $S$ for a given $a$ is $O(1)$ (in practice, it will be $O(n)$).

Given this formulation, there is a deterministic algorithm that runs in $O(n^3)$ time.

There are three parts to this algorithm:

Getting $\ge 2$ matches

1. Let $P$ be an empty set.
2. Let $S_P$ be the score at the start of this iteration.
3. If $S \ge 2$, we are done.
4. Swap pairs that are not in $P$ until $ S \ge S_P+1$.
5. Add the last pair you swapped to $P$.
6. Go back to step 1

Step 2 will take at most $O(n^2)$ swaps, and there will be at most $2$ iterations of the loop.

Finding the locations of $2$ matches

This is the easiest part:

1. Let $S_P$ be the score at the start of this part.
2. Swap pairs until $S=S_P-2$.
3. Label the balls you swapped A and B.
4. Swap A and B back.
5. You now know the location of two balls in $b$.

Like the first part, this will also take $O(n^2)$.

(EDIT: While writing this answer, I have noticed that you could just repeat the first two parts over and over again to find the rest of the positions (I think ConnFus's answer was trying to use this method), but I already wrote the rest out, so... enjoy!)

Finding the locations of the rest of the balls

This is the "meat" of the algorithm.

1. Let the set of indices of balls you know the positions of in $b$ be $P$.

2. Continue until $|P|=n$:

3. Let $S_P$ be the score at the start of this iteration.

4. Take a pair of two other balls not in $P$, label them $A$ and $B$, and swap them:

   a. If $S=S_P+2$ correct matches, add $A$ and $B$ to $P$. Go back to step 2.

   b. If $S=S_P$, swap back $A$ and $B$, and go back to step 2.

c. If $S=S_P+1$ matches: take a ball from $P$ and call it $C$. Swap $C$ and $A$. If there are $S=S_P-1$ matches, swap back $A$ and $C$, and add $A$ to $P$; else, add $B$ to $P$. In either case, go back to step 2.

d. If $S=S_P-2$ correct matches, swap back $A$ and $B$ and add $A$ and $B$ to $P$. Go back to step 2.

e. If $S=S_P-1$ correct matches, swap A and B back. Take a ball from $P$ and call it $C$. Swap $A$ and $C$. If $S=S_P-2$ matches, swap back $A$ and $C$, and add $A$ to $P$; else, add $B$ to $P$. In either case, go back to step 2.