Randomize List with guaranteed Index Change I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple:
Shuffle/Randomize an array/list
conditions:

each Index has to change; an Item which was at index 0 before the shuffle has to be at an index != 0 after the shuffle
all possible resulting permutations which satisfy the first condition should be distributed equally

I am unable to find a satisfying solution. Brute force (shuffling the array with Fisher-Yates until first condition is met) obviously works but is not a solution I am looking for. Brute Force with an array with four elements resulted in following number of permutations (which is roughly distributed equally) for one million tries: [111467, 111172, 111497, 111047, 111114, 111053, 110699, 110655, 111296]
Another thing I tried was something like this:

iterate through the array object by object and randomly choose a new index for the object
the randomly chosen index must not have been chosen before and must not be same as the original index
if the last element would fall on its original index, swap the last element with a random other element

Using this approach, the distribution looks really bad: [74166, 110734, 83581, 129486, 83210, 101904, 111305, 111235, 194379].
In theory, there must be a better solution than brute force but unfortunately everybody I asked so far (including google) didn't have a solution, or just had another non uniform solution comparable to my second approach.
Can anyone help me please? I would appreciate it a lot.
NOTE: updated (before it had low=i+1 always, this missed some valid results, and missed the extra check needed for the last index)
**NOTE: update 2 - randomize order to ensure uniformity **
Consider the following approach:
loopIndex[0..n-1] = permute([0..n-1])
index[0..n-1] = [0..n-1] // track indices
for i=0..n-2
   idx = loopIndex[i]
   if index[idx] == idx
      low = i+1
   else low = i
   swapIdx = random(low,n) // random(start,end) --&gt; start &lt;= i &lt; end
   swapElement(index, idx, loopIndex[swapIdx])
   swapElement(array, idx, loopIndex[swapIdx])
finalIdx = loopIndex[n-1]
if index[finalIdx] == finalIdx
   finalSwapIdx = random(0,n-1)
   swapElement(index, finalSwapIdx, finalIdx)
   swapElement(array, finalSwapIdx, finalIdx)

PROOF NOT YET UPDATED
Note the following:

loopIndex is used to give a random ordering on which we process the elements. This ensures that any non-uniformity is &quot;smoothed out&quot;.
If an index $j$ is selected as swapIdx then that element is swapped to a place where it's not processed again in the loop.
If an index $j &lt; n-1$ is never selected as swapIdx then when $i==j$ the element will be swapped out from $j$ and never can return to $j$.
The final check handles the case where the final element was never selected. In this case, we swap between $n-1$ and some other random element.

Proof of uniformity by induction on the index -
Let $p(j,k)$ be the probability that after completing $i=j$, the element at index $j$ is the element that originally had index $k \neq j$ (clearly $p(j,j)=0$).
Then $p(0,k)=\frac{1}{n-1}$ clearly.
Assume then that the statement holds for all $j \leq t$ and we now prove for $j=t+1$.
$p(t+1,k)$ is the probability the element with original index $k$ is not in the first $t$ elements at step $i=t+1$, times the probability that $k$ is swapIdx now. By the assumption, this is then:
$$
\left(\frac{n-2}{n-1}\right)\left(\frac{n-3}{n-2}\right)\dots\left(\frac{n-t-1}{n-t}\right)\left(\frac{1}{n-t-1}\right) = \frac{1}{n-1}
$$
(Note that there is a minor difference between $k \leq t$ and $k &gt; t+1$. For the former, it must not have been selected as a swapIdx for $j \neq k \leq t$, and it must not have selected $t+1$ as its swapIdx. For the latter, it must not have been selected as a swapIdx. The result though is the same in terms of the math).