Given an arbitrary Mathematica expression, how can I choose a random part of the expression and replace it with another symbol of my choosing?
For example, given $a x^3 +2y\cos(x)- \tanh(x^{y+3})/(x^4-\sqrt{b})$, I want to select a single randomly chosen part of the expression that involves an $x$ term and replace it with $\mathbf{u}$. This part could be any sub-expression with an $x$ such as $x^3,a x^3, 2y\cos(x),\cos(x),x, x^{y+3},\tanh(x^{y+3}),x^4,(x^4-\sqrt{b})$, or even the whole expression. Examples:
$$ \mathbf{u}\\ \mathbf{u} +2y\cos(x)- \tanh(x^{y+3})/(x^4-\sqrt{b})\\ a x^3 +2y\cos(x)- \tanh(x^{y+3})/\mathbf{u}\\ a x^3 +2y\cos(x)- \tanh(\mathbf{u})/(x^4-\sqrt{b})\\ a x^3 +\mathbf{u}- \tanh(x^{y+3})/(x^4-\sqrt{b})\\ a x^3 +2y\cos(x)- \mathbf{u}/(x^4-\sqrt{b})\\ \mathbf{u} - \tanh(x^{y+3})/(x^4-\sqrt{b})\\ a x^3 + 2y\cos(x) - \mathbf{u}\\ a x^3 + \mathbf{u} $$
Also I'd like to know which subexpression was chosen for replacement with $\mathbf{u}$. So far I've been able to generate random replacements like this:
expr = a x^3 + 2 y Cos[x] - Tanh[x^(y + 3)]/(x^4 - Sqrt[b]);
Table[ReplacePart[expr,
RandomChoice[Position[expr, _, Heads -> False]] -> u],
1000] // DeleteDuplicates
...but I have not been able to 1) only select expressions involving $x$, and 2) record which subexpression was chosen.
For clarification, the following image shows the expression tree for the example I gave above. Green nodes are eligible for replacement with $\mathbf{u}$ because they contain $x$ or some sub-expression involving $x$. Red nodes do not contain any $x$ and are not eligible for replacement: