1
$\begingroup$

input : $array[1...n]$
output: permutated array
Our algorithm should be probablistic and complexity should be $O(n)$.

Could you give me hint ? My weakness is probability theory and it is why I have a problem.

$\endgroup$
  • $\begingroup$ Hint : ​ Your algorithm should be on a word RAM, since otherwise that is provably impossible. ​ ​ ​ ​ $\endgroup$ – user12859 Aug 10 '15 at 20:15
  • $\begingroup$ You may assume, that we have procedure, such that guess number from interval 1..n $\endgroup$ – M.Swe Aug 10 '15 at 20:17
  • $\begingroup$ @RickyDemer Why is it provably impossible without word RAM? $\endgroup$ – JustAnotherSoul Aug 10 '15 at 20:33
  • $\begingroup$ @JustAnotherSoul : ​ ​ The amount of randomness it needs and the amount of output it produces are both ​ $\Omega(n\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))$ . ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Aug 10 '15 at 21:09
  • $\begingroup$ The ideal algorithm due to Fisher and Yates needs n-1 pseudo-random numbers to permute an array of n elements. Could it be, that you have in mind in your question to reduce the number of prns required, while yet obtaining a not too bad pseudo-random permutation in practice? $\endgroup$ – Mok-Kong Shen Aug 13 '15 at 14:50
2
$\begingroup$

First we need to define the algorithm a bit more stringently. I prefer this one.

Choose a $N$-permutation $P$ with probability $U(P)$ where $U$ is a uniform distribution of the space of $N!$ permutations on $N$ values.

I like to solve this in an inductive fashion.

First we think about how we can do this with 1 value. Well how many permutations are there over 1 value? There is 1 such permutations. Because our uniform distribution needs to sum to unity it follows that the permutation must occur with probability. So we select it with probability 1. That is to say we always select it.

Second we think about how we can generate an $N$-permutation given an $(N-1)$-permutation? How can we do this? It isn't hard to see that there are an equal number of $N$-permutations in which a number $X$ occurs in position $i$ as there are where $X$ occurs at position $j$. So if the number is the same and the permutations are uniformly distributed then it must be equally likely for a number $X$ to occur anywhere in the permutation. Thus we just need to figure out how to insert our $N$th number into the smaller permutation in a uniformly distributed way.

If you want to look it up this is called the Fisher-Yates shuffle

$\endgroup$
3
$\begingroup$

I'm not exactly certain what you mean by probabilistic procedure as pertains to array permutation, and I'm going to assume you're looking for a random permutation of the array. I'm basing this off the formulation of the problem being very similar to an algorithm for that purpose.

So lets say as a person I'd like to do this task: Well, I'd probably just write down all the possible numbers, and then pick a random one. Then I'd cross of the one I'd picked and continue until I'd crossed them all off.

Spoiler as to the name of the algorithm which I mentioned:

See Fisher-Yates Shuffle algorithm or Knuth Shuffle.

$\endgroup$
  • $\begingroup$ Tell me: Is it this algorithm tricky ? $\endgroup$ – M.Swe Aug 10 '15 at 20:30
  • $\begingroup$ It isn't so much so. If that sounds like it is a possible solution I can explain it more fully here. $\endgroup$ – JustAnotherSoul Aug 10 '15 at 20:31
  • $\begingroup$ Ok, could you tell more about it ? $\endgroup$ – M.Swe Aug 10 '15 at 20:34
  • $\begingroup$ Alright so you'd do something like so: The input is 1..n. Create a set that contains the values 1..n. Generate a random value up to the size of the set. Remove that element and place it at position 0 in your solution. Repeat until the set is empty. $\endgroup$ – JustAnotherSoul Aug 10 '15 at 20:36
  • $\begingroup$ Ok, it looks like full algorithm. Am i wrong ? $\endgroup$ – M.Swe Aug 10 '15 at 20:38
1
$\begingroup$

Try this: // Shuffle a collection, using the modern version of the // Fisher-Yates shuffle.

translated from: http://underscorejs.org/underscore.js shuffle function

In this case we use $A$ to denote input array and $B$ to shuffled output array

1. Function $\text{shuffle} : A \mapsto B$:

2. let $n$ the length of $A$

3. let $B$ shuffled empty array, with $n$ size

4. for each index $i \leftarrow 0$ until $n-1$ do:

1. set random value $r \leftarrow \text{random}(0, i)$

2. if ( $r \neq i$) $\implies$ $B[i] \leftarrow B[r]$

3. $B[r] \leftarrow A[i]$

5. end for block;
6. return $B$;

$\endgroup$
  • $\begingroup$ Presumably OP wants a proof that the procedure is correct, not just a code snippet. $\endgroup$ – vonbrand Aug 11 '15 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.