Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I am not sure I understand your spec and requirements, but see if this helps. stackoverflow.com/questions/1851716/… –  Amzoti Nov 25 '12 at 18:45
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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