A Data Science Central Community

In my recent article on a new, robust coefficient of correlation and R Squared, I mentioned an algorithm to generate random permutations:

**Rudimentary**** algorithm** to generate a random permutation (p(0), p(1), ... , p(n-1))

For k=0 to n-1, do:

- Step 1. Generate p(k) as a random number on {0, ... , n-1}
- Step 2. Repeat Step 1 until p(k) is different from p(0), p(1), ... , p(k-1)

End

I also asked what is the computational complexity of this algorithm, as I was comparing it with two

**Alternate algorithms**:

- Create n random numbers on [0,1], then p(k) is simply the rank of the k-th deviate (k=0, ... , n-1). From a computational complexity point of view, this is equivalent to sorting, and thus it is O(n log n).
- Use the one-to-one mapping between n-permutations and numbers in 1...n! However, transforming a number into a permutation, using the factorial number representation, is O(n^2).

You would expect my rudimentary algorithm to be terribly slow. Actually, it might never end, running indefinitely, even just to produce p(1), let alone p(n-1) which is considerably harder to produce.

Yet it turns out that my rudimentary algorithm is also O(n log n). Proving this fact would actually be a great job interview question. Here's the outline:

For positive k strictly smaller than n, you can create p(k) either

- on the first shot with probability L(k,1) = 1 - k/n.
- on the second shot with probability L(k,2) = (k/n) * (1 - k/n)
- on the third shot with probability L(k,3) = (k/n)^2 * (1 - k/n)
- on the fourth shot with probability L(k,4) = (k/n)^3 * (1 - k/n)

etc. Note that the number of shots required might be infinite (with probability 0).

Thus, on average, you need M(k) = SUM{ j * L(k,j) } = n/(n-k) shots to create p(k), where the sum is over all positive integers j = 0, 1, 2... The total number of operations is thus (on average) SUM{M(k)} = n * {1 +1/2 + 1/3 + ... + 1/n}, where the sum is on k=0,1,...,n-1. This turns out to be O(n log n). Note that in terms of data structure, we need an auxiliary array A of size n, initialized to 0. When p(k) is created (in the last, successful shot at iteration k), we update A as follows: A[p(k)]=1. This array is used to check if p(k) is different from p(0), p(1), ... , p(k-1), or in other words, if A[p(k)]=0.

Is O(n log n) the best that we can achieve? No, the algorithm below is O(n):

**Fast Algorithm** (Fisher–Yates shuffle)

p(k) ← k, k=0,...,n-1

For k=n-1 down to 1, do:

- j ← random integer with 0 ≤ j ≤ k
- exchange p(j) and p(k)

End

By the way, what is the name of my algorithm? It must have been invented long ago, althought it takes less time to reinvent it and assess its computational complexity, then it takes to find it in the literature.

**Related articles**

© 2019 AnalyticBridge.com is a subsidiary and dedicated channel of Data Science Central LLC Powered by

Badges | Report an Issue | Privacy Policy | Terms of Service

**Most Popular Content on DSC**

To not miss this type of content in the future, subscribe to our newsletter.

**Technical**

- Free Books and Resources for DSC Members
- Learn Machine Learning Coding Basics in a weekend
- New Machine Learning Cheat Sheet | Old one
- Advanced Machine Learning with Basic Excel
- 12 Algorithms Every Data Scientist Should Know
- Hitchhiker's Guide to Data Science, Machine Learning, R, Python
- Visualizations: Comparing Tableau, SPSS, R, Excel, Matlab, JS, Pyth...
- How to Automatically Determine the Number of Clusters in your Data
- New Perspectives on Statistical Distributions and Deep Learning
- Fascinating New Results in the Theory of Randomness
- Long-range Correlations in Time Series: Modeling, Testing, Case Study
- Fast Combinatorial Feature Selection with New Definition of Predict...
- 10 types of regressions. Which one to use?
- 40 Techniques Used by Data Scientists
- 15 Deep Learning Tutorials
- R: a survival guide to data science with R

**Non Technical**

- Advanced Analytic Platforms - Incumbents Fall - Challengers Rise
- Difference between ML, Data Science, AI, Deep Learning, and Statistics
- How to Become a Data Scientist - On your own
- 16 analytic disciplines compared to data science
- Six categories of Data Scientists
- 21 data science systems used by Amazon to operate its business
- 24 Uses of Statistical Modeling
- 33 unusual problems that can be solved with data science
- 22 Differences Between Junior and Senior Data Scientists
- Why You Should be a Data Science Generalist - and How to Become One
- Becoming a Billionaire Data Scientist vs Struggling to Get a $100k Job
- Why do people with no experience want to become data scientists?

**Articles from top bloggers**

- Kirk Borne | Stephanie Glen | Vincent Granville
- Ajit Jaokar | Ronald van Loon | Bernard Marr
- Steve Miller | Bill Schmarzo | Bill Vorhies

**Other popular resources**

- Comprehensive Repository of Data Science and ML Resources
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- 100 Data Science Interview Questions and Answers
- Cheat Sheets | Curated Articles | Search | Jobs | Courses
- Post a Blog | Forum Questions | Books | Salaries | News

**Archives**: 2008-2014 | 2015-2016 | 2017-2019 | Book 1 | Book 2 | More

**Most popular articles**

- Free Book and Resources for DSC Members
- New Perspectives on Statistical Distributions and Deep Learning
- Time series, Growth Modeling and Data Science Wizardy
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- Comprehensive Repository of Data Science and ML Resources
- Advanced Machine Learning with Basic Excel
- Difference between ML, Data Science, AI, Deep Learning, and Statistics
- Selected Business Analytics, Data Science and ML articles
- How to Automatically Determine the Number of Clusters in your Data
- Fascinating New Results in the Theory of Randomness
- Hire a Data Scientist | Search DSC | Find a Job
- Post a Blog | Forum Questions

## You need to be a member of AnalyticBridge to add comments!

Join AnalyticBridge