Comment générer une matrice aléatoire en C++?

Je veux générer une matrice fixe rareté et aléatoire des index et de la valeur.

Afin de simplifier le problème, prendre de tableau par exemple: générer un arr[10] avec seulement 3 emplacement avec une valeur non nulle. Si je viens aléatoire de ces 3 indices un par un, l'efficacité de l'algorithme est mauvais à cause de la répétition.

Plus difficile, j'ai aussi envie de générer une matrice aléatoire avec le rang de k, car nulle cols et rows peut provoquer un bug avec mon code...Comment faire cette fois?

Merci!

InformationsquelleAutor xunzhang | 2012-08-13

algorithm c c++random random-sample

Vous pouvez accomplir cela avec du TSL 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
}

Pourquoi la peine de brassage?

InformationsquelleAutor dmitru

0

N-dimensions tableau peut être aplatie de dehors en dimension 1 (pour les fins de l'énumération de tous ses éléments). Disons que vous avez un 5x7 tableau - ce qui signifie qu'il y a un total de 35 éléments.

Une fois que vous "remplir" le premier élément est le nombre total de places disponibles descend par un afin que vous puissiez visualiser votre tableau comme ayant seulement 34 "vide" spots maintenant - donc tout ce que vous devez faire maintenant est de remplir un élément à l'indice entre 0 et 33, et n'oubliez pas de sauter le déjà rempli lorsque vous êtes localiser cet élément.

Cette deuxième partie peut obtenir de temps donc si vos tableaux sont toujours très rares, vous pouvez simplement la liste de tous ces "prises" spots dans un tableau séparé... non, ce ne serait pas vous aider beaucoup. Un distinct lié liste de tous les endroits sera aussi inefficace, demanderait beaucoup trop de temps (relativement) à allouer et à parcourir pour chaque et chaque itération.

Par essence, le problème est de trouver un moyen rapide d'indexation dans un tableau modifié, dans lequel le nombre total d'éléments est représentant les taches qui ne sont pas encore pris et pour un éparses de la matrice de tout moyen de l'enregistrement de celles prises spots va l'emporter sur le temps qu'il faut pour générer un côté aléatoire de l'indice en cas de collision.

Seulement si le tableau est plus ou moins denses (où "plus ou moins" est un inconnu pour moi de la valeur, mais je m'attends à être au-dessus de 60% -70%) se pourrait-il que tenir un registre des éléments utilisés peuvent l'emporter sur le temps qu'il faut pour générer un non-indice répété.

InformationsquelleAutor YePhIcK
0

Si le tableau est de taille N et K est le nombre de non-zéro entrées viens de le faire:
```
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();
}
```
Comme cela a été souligné, vous pouvez aussi mettre les non-zéro éléments au début du tableau et shuffle il. C'est clairement un meilleur algorithme si vous êtes seulement à l'initialisation d'une fois.

L'avantage de l'algorithme ci-dessus vient quand il faut ré-initialiser a à une autre matrice aléatoire de nombreuses fois. Il suffit de garder r autour. Ré-initialisation n'est pas nécessaire. Chaque insertion ultérieure de K non nul éléments doit seulement K étapes. Si K est petit par rapport à N, ce peut être une grande victoire:
```
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;  
}
```
- Quel est l'avantage de l'utilisation de la r tableau au cours de l'initialisation de K éléments pour une valeur aléatoire, N-K éléments à zéro, et puis brassage de la matrice?
- Si vous devez les initialiser à de nombreuses reprises, vous pouvez garder r. Vous n'avez pas à re-initialiser (première boucle). Toutes les insertions de K éléments doivent seulement K étapes. Le shuffle exigera N. Si vous avez seulement une initialisation à faire, le shuffle est mieux.
InformationsquelleAutor Gene

-1

#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;

}

Bien, je suis nouveau dans la programmation et j'étais à la recherche d'un moyen de créer une matrice avec des participants au hasard, je l'ai fait et effectivement travaillées, espérons que cela est utile pour vous. 😀

Aussi, vous pouvez essayer avec n'importe quelle taille de la matrice.
Il ressemble à votre code met un nombre au hasard dans chaque ligne et colonne. La question d'origine veut mettre un petit nombre de non-zéro des valeurs au hasard dans une matrice. C'est super ce que vous êtes en train d'apprendre la programmation, mais ce n'est pas une réponse à la question d'origine.
Ne pas utiliser rand(), c'est considéré comme nocif.

InformationsquelleAutor Jareth León Santiago

Vous devez vous connecter pour publier un commentaire.