CODEWITHSUNDEEP
c++calgorithmrandom
xunzhang
xunzhang

Reputation: 2926

How to generate a random matrix in C++?

I want to generate a matrix with fixed sparsity and random indexes and value.

In order to simplify the problem, take array for example: generate a arr[10] with just 3 location with non-zero value. If I just random these 3 indexes one-by-one, the efficiency of the algorithm is bad because of the repetition.

More difficult, I also want to generate a random matrix with rank k because null cols and rows may cause a bug with my code...How to make it this time?

Thanks!

Upvotes: 2

Views: 20228

Answers (4)

Jareth León Santiago
Jareth León Santiago

Reputation: 11

#include <iostream>
#include <stdlib.h>

using namespace std;
int main(){
    int A[100][100],filas,columnas,m,k,n;
    cout<<"filas";
    cin>>filas;
    cout<<"columnas";
    cin>>columnas;
    n=filas*columnas;
    srand(time(NULL));
    for(int i=0;i<filas;i++){
        for(int j=0;j<columnas;j++){
            for (k=1; k<=n; k++){
                m= 1+rand()% (n - 1);
            A[i][j]= m;
            }
        }
    }
    for(int i=0;i<filas;i++){
        for(int j=0;j<columnas;j++){
            cout<<A[i][j]<<" ";
        }
        cout<<"\n";
    }

    return 0;

}

Well, I'm new in programming and I was a looking a way to create a matrix with random entries, I did this and actually worked, hope this is useful to you. :D

Upvotes: -1

Gene
Gene

Reputation: 46960

If the array is of size N and K is the number of non-zero entries just do this:

ARRAY_ELT_TYPE a[N];
int r[N];
for (i = 0; i < N; i++) { a[i] = 0; r[i] = i; }
for (i = 0; i < K; i++) {
  swap(r[i], i + random_nonneg_less_than(N - i));
  a[r[i]] = nonzero_value();
}

As has been pointed out, you can also put the non-zero elements at the beginning of the array and shuffle it. This is clearly a better algorithm if you're only initializing once.

The advantage of the above algorithm comes when you must re-initialize a to a different random matrix many times. Just keep r around. Re-initialization is not needed. Every subsequent insertion of K non-zero elements needs only K steps. If K is small compared to N, this can be a big win:

ARRAY_ELT_TYPE a[N];
int r[N];

// Initialize one time.
for (i = 0; i < N; i++) { a[i] = 0; r[i] = i; }
j = 0;

for (many, many iterations) {

  // Insert non-zero values in K steps.
  for (i = 0; i < K; i++) {
    swap(r[i], i + random_nonneg_less_than(N - i));
    a[r[i]] = nonzero_value();
  }

  //
  // USE RANDOM ARRAY a HERE
  //

  // Re-zero a in only K steps.
  for (i = 0; i < K; i++) a[r[i]] = 0;  
}

Upvotes: 0

YePhIcK
YePhIcK

Reputation: 5856

Any N-dimensional array can be flattened-out into a 1-dimensional (for the purposes of enumerating all of its elements). Say you have a 5x7 array - this means there's a total of 35 elements in it.

Once you "fill in" the first element the total number of available slots goes down by one so you can view your array as having only 34 "empty" spots now - thus all you need to do now is to fill-in an element at index between 0 and 33 and remember to skip the already filled in ones when you are locating that element.

This second part may get time-consuming so if your arrays are always very sparse you can just list all those "taken" spots in a separate array... no, that would not help you much. A separate linked list of all the spots will also be inefficient - would require way too much time (relatively) to allocate and traverse for each and every iteration.

In essence the problem is to find a fast way of indexing in a modified array, in which the total number of elements is representing the spots that are not taken yet and for a sparse array any way of recording those taken spots is going to outweigh the time it takes to generate a next random index in case of a collision.

Only if the array is more-or-less densely filled (where "more-or-less" is an unknown to me value, but I'd expect it to be above 60%-70%) could it be that keeping a record of used elements may outweigh the time it takes to generate a non-repeated index.

Upvotes: 0

dmitru
dmitru

Reputation: 371

You can accomplish this with STL's random_shuffle:

#include <vector>
#include <algorithm>

// Function that generates random array elements
int random_element();

const int n = 10;  // Size of the array
const int k = 4;   // Number of random (non-zero) elements in the array
int a[n];          // The array, filled with zeros

int main()
{
  for (size_t i = 0; i < k; ++i)
    a[i] = random_element();

  std::random_shuffle(a, a + n);

  // Now 'a' contains k random elements and (n-k) zeros, in a random order
}

Upvotes: 5

Related Questions