I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should contain only distinct digits and of course process of generating those numbers is a bit too slow and it's a bit frustrating since it's not even a main function. I was able too speed things up by using parallel computing yet I wonder if there is any way other than trying to evaluate each consecutive sequence of numbers to determine if it contains any digit more than once?
I tried looking through internet for some similar problem or algorithm but found nothing helpful.
Best Answer
I don't know your attempts, but here is a simple, not too efficient algorithm.
To select a k digit number with distinct digits (of course k $\le$ n), fill an array A[10] with zeros. This represents the digits chosen, with 0 meaning not chosen. Set your generated number N = 0.
Do this k times: Generate a random integer m from 0 to n-1 until A[m] = 0. Set A[m] = 1 and N = 10*N+m.
The key to making this more efficient is generating a digit that has not been used before. Another possibility is to have an array with [0,1,2,3,4,5,6,7,8,9] and, each time choose a random entry and then remove the chosen entry, moving all the following one up.
This can probably be done in time O(k), but I can't think of one right now and my copy of Knuth is in the next room.