Does anyone have an algorithm that generates all 10-digit integers that have at least one digit repeated? Trawling through all 9000000000 of them and checking them individually is too slow. Thanks.
stinkypete
VernonDozier 2,218 Posting Expert Featured Poster
Does anyone have an algorithm that generates all 10-digit integers that have at least one digit repeated? Trawling through all 9000000000 of them and checking them individually is too slow. Thanks.
10 digit number, 10 digits, none repeated, sounds like you can generate all permutations of 0123456789, then throw out the ones that start with 0. The set of ten digit numbers MINUS this set is your answer. The set of all 10-digit integers that have at least one digit repeated is far larger than the set if 10-digit integers without repeats, so you're dealing with close to 9000000000 anyway, so if you have to "generate" them all (what precisely does "generate" mean here?), you can either "trawl" through them as you said or you can start with all of them, then remove the ones I mentioned. Either way seems like a long runtime.
stinkypete
By generate I mean that each time round the algorithm, another 10-digit number pops out.
VernonDozier 2,218 Posting Expert Featured Poster
10! is 3,628,800. 10 to the 10th power is 10 billion. Take away the numbers that start with 0 and that's what you're working with. You have, again, two options. One way or another, you have a loop of 9 billion if you need to "pop out" a number each time. You can either have an array or vector or set or whatever of the numbers that don't have repeated digits and check against that 9 billion times, or you can test each number by going through all ten digits 9 billion times. I imagine the former is faster than the latter, but a little testing will tell.
jaskij 45 Junior Poster in Training
To be honest with you, I'd say it's not a task for C++, rather a computer algebra system - they tend to cope with similar tasks really well.
Anywas, there is next_permutation() in the STL algorithm header, this should help you using what VernonDozier wrote. Just pick a digit to repeat, make an array(or vector) of them, sort it, then iterate through it's permutations using next_permutation() . Still, you have 10*9!=10!=3,628,800 iterations on your hands.
Zvjezdan23 -13 Junior Poster
generate random numbers from 1 to 9??? easy. make a random number generator from 1 to 9 then make an int number_array[10] and have the arrays = random numbers.
stinkypete
generate random numbers from 1 to 9??? easy. make a random number generator from 1 to 9 then make an int number_array[10] and have the arrays = random numbers.
I want all the numbers, not a random selection.
stinkypete
I'm going to mark this thread as solved. Not that my question has been answered, but I don't think it has an answer other then "no-one knows, and probably not".
VernonDozier 2,218 Posting Expert Featured Poster
It does have an answer, lots of people do know how to do it, including me, and I tried to explain how I would do it.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.