how to check a matrix for duplicate numbers C++

Question

I'm trying to generate a 5x20 matrix filled with random numbers. How can I make sure none of the random numbers are duplicates? This is the code I have for filling the matrix with random numbers.

srand(time(0));
int matrix[5][20];
int i = 0;
int j = 0;
for (i = 0; i < 5; i++)
{
    for (j = 0; j < 20; j++) 
    {
        matrix[i][j] = 1 + (rand() % 100);
        cout << matrix[i][j] <<"_";
    } 
    cout << endl;
}

the code works but there are sometimes duplicates. If this were an array I could make use of a simple for loop and compare all of the elements in the array. but I have no idea how to do so with a matrix. I have searched everywhere but cant seem to find a solution.

Your final purpose is creating a matrix without element-duplicated, right? But your title restrict the answer to one approach. — khôi nguyễn, Nov 03 '16 at 04:14
if you want to fill 100 array elements with 100 different numbers then it's about [shuffling](http://stackoverflow.com/q/6926433/995714), not about generating random numbers in general, because `1 1 1 1 1... 1` is a completely random sequence http://stackoverflow.com/q/27791474/995714 — phuclv, Nov 03 '16 at 04:34

khôi nguyễn · Answer 1 · 2016-11-03T04:15:08.947

It's not quite fit your question title but I think you should take a look.

   for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 20; j++) 
        {
        matrix[i][j] = 1 + (rand() % 100);
        cout << matrix[i][j] <<"_";
        } 
        cout << endl;
    }

I don't know the 5x20 and 100 (in rand() % 100) is compulsory or just an example you want to give. So I suggest for all case I can consider:

Let call the number of matrix elements is a, the number of set (contains all possible generated number) is b. In your is example, a is 5x20=100 and b is 100 (from 1 to 100).

a > b: no valid matrix without duplicates since Dirichlet principle
a == b: take a look at http://en.cppreference.com/w/cpp/algorithm/random_shuffle. Just create an 1-dimension array containing consecutive number from 0 to b-1 (or from min and max of your range) and permute them. Then use it to fill in the matrix.
a < b: similar to case a==b, but you just take a part of the permutation.

Of course, when a =< b then you can use rand() but you have to check duplicate and retry rand(), which is quite complicated. You can create a mark array (which cost memory) or iterate through your matrix again (which cost time).

Even better than `random_shuffle`/`shuffle` would be [`sample`](http://en.cppreference.com/w/cpp/algorithm/sample); sadly, it's a C++17 feature, so it's sufficiently bleeding edge that many compilers won't support it. — ShadowRanger, Nov 03 '16 at 04:35

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

0

not exactly answer your question but for your purpose you can try something like this:

#include <iostream>
#include <string>
#include <algorithm>

int main()
{
    srand(time(0));
    int matrix[5][20];
    int *pmatrix = &matrix[0][0];
    int i = 0;
    for (i = 0; i < 100; i++)
    {
        pmatrix[i] = i+1;
    } 
    
    std::random_shuffle(pmatrix, pmatrix+100);
    
    for (i = 0; i < 100; i++)
    {
        std::cout<<pmatrix[i]<<",";
    } 
    
}

cpp.sh/5bnyt

Update fixed memory out of bounds problem.

edited Jun 20 '20 at 09:12

Community

1
1

answered Nov 03 '16 at 04:20

Logman

4,031
1
23
35

You're accessing the array `matrix` out of bounds. – druckermanly Nov 03 '16 at 04:24
@user2899162 yes you right I have got some of kind temporal mental retardation. I will correct the code. – Logman Nov 03 '16 at 04:31

druckermanly · Accepted Answer · 2016-11-03T04:28:42.023

as a heads up, you shouldn't use rand() unless you've got explicit reasons to (such as a professor's requirements).

The following approach uses a GetIndex function to simulate an int[5][20] with an int[100]. See if you can figure out how to use the code I wrote to create an int[5][20].

Your code fills the matrix with random numbers between 1 and 100 (1 + (rand() % 100)) inclusively, but you do no work to ensure you don't get duplicates! So you won't be able to guarantee that you don't get duplicates (in fact, it's very unusual for you to get no duplicates).

If you first initialize all your values to 1,...,100 and then later shuffle them, you know you have no duplicates.

#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>

constexpr size_t kDefaultMatrixHeight = 20;
constexpr size_t kDefaultMatrixWidth = 5;

constexpr size_t GetIndex(size_t i, size_t j) {
  return i * kDefaultMatrixWidth + j;
}

int main() {
  int matrix[kDefaultMatrixWidth * kDefaultMatrixHeight];

  for (size_t i = 0 ; i < kDefaultMatrixHeight * kDefaultMatrixWidth ; i++) {
    matrix[i] = i + 1;
  }

  std::mt19937 rng(std::random_device{}());

  std::shuffle(std::begin(matrix), std::end(matrix), rng);

  for (size_t i = 0 ; i < kDefaultMatrixHeight ; i++) {
    for (size_t j = 0; j < kDefaultMatrixWidth ; j++) {
      std::cout << std::setw(4) << matrix[GetIndex(i,j)];
    }
    std::cout << '\n';
  }
}

And for example output:

Test@Test:/tmp/example$ g++ example.cpp && ./a.out
  93  28  70  14  39
  83   3  80  95  58
  42  69  71  16  49
  75  63  41  82  46
  26  50  81  33  97
  65  10  77  68  12
   8  19  30  86  37
  57  24  78  31  88
   2  90   4  13  56
  36  15  35  32  85
  29  76  99  45  18
  54  11  44  62  98
   9  96  79  34  27
  40  21  52  22  55
  72   1  47  92  59
  94   7  64  91  53
  74   5  61 100  89
  48  23  66  67  51
  38   6  87  17  20
  60  25  84  43  73

how to check a matrix for duplicate numbers C++

3 Answers3