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.

  • 1
    $\begingroup$ I am not sure I understand your spec and requirements, but see if this helps. stackoverflow.com/questions/1851716/… $\endgroup$ – Amzoti Nov 25 '12 at 18:45
  • 1
    $\begingroup$ Do you receive the numbers and have to check them for duplicate digits or do you generate the numbers given a minimum and maximum? If you write the question clearly, it helps make sure we are answering the right one. $\endgroup$ – Ross Millikan Nov 12 '14 at 19:07

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.


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.