How to generate nine digits numbers in which each digit differ from the others

Question

I am making a program and I need to generate all 9 digits numbers which have each digit different to the other digits, the 0 is not a valid digit in this case so I am only considering digits from 1 to 9.

So far I have this solution using random number generation, but I am facing performance issues

using namespace std;
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <string>
#include <map>

int main()
{
    srand (time(NULL));

    int secret;
    string number = "";

    map <string, bool> m;
    int count = 0;

    int nine_permutation = 362880;

    vector <int> v{0,1,2,3,4,5,6,7,8,9};
    int x = 9;

    while(count < nine_permutation)
    {
      for(int i = 0; i < 9; i++)
      {
          secret = rand() % x +1;
          number += to_string(v[secret]);
          v.erase(v.begin() + secret);

          x--;
      }
      x = 9;
      v = {0,1,2,3,4,5,6,7,8,9};
      if(m.count(number) == 0)
      {
        m[number] = true;
        count ++;
      }


      cout << count << endl;
    }


    cout << number;
}

The program suddendly stops generating after 43,000 numbers aprox. Then it crashes and I have to close it via Task Manager because the window is completely frozen. — Just Half, Jun 20 '18 at 01:17
Possible duplicate of [How to shuffle a std::vector?](https://stackoverflow.com/questions/6926433/how-to-shuffle-a-stdvector) — , Jun 20 '18 at 01:45
Generating all permutations by random is going to take a while – especially using `rand` and `%, since your random digits aren't uniformly distributed. Be systematic instead of random. — molbdnilo, Jun 20 '18 at 02:42
Reading more closely, you're not even generating nine-digit numbers - print `number` inside the loop and look. — molbdnilo, Jun 20 '18 at 13:35
I suggest you to shuffle your vector as describe here : https://stackoverflow.com/questions/6926433/how-to-shuffle-a-stdvector — Arnault Le Prévost-Corvellec, Jun 21 '18 at 10:12

score 1 · Accepted Answer · answered Jun 20 '18 at 22:08

So you have 10 digits 0,1,2,3,4,5,6,7,8,9 and number you want to get numbers with nine digits. I think you can start with 123456789, generate all permutations and then replace each character with '0' which would give set: {023456789, 103456789, 120456789, 123056789, 123406789, 123450789, 123456089, 123456709, 123456780}. And for each element from this set also generate all permutations. Something like this:

void allNumbersWithDistinctDigits() {
    int idxForZero = 0;
    std::string initial("123456789");

    std::string local(initial);
    do {
        while (std::next_permutation(local.begin(), local.end())) {
            if (local[0] != '0') {
                std::cout << local << std::endl;
            }
        }
        local = initial;
        local[idxForZero] = '0';
    } while(++idxForZero <= initial.size());

}

Condition if (local[0] != '0') is optional and it gets rid of numbers starting with 0, like: 012345678 which is in fact 8 digits 12345678 or octal number.

How to generate nine digits numbers in which each digit differ from the others

1 Answers1