2

スパース性が固定され、インデックスと値がランダムなマトリックスを生成したいと考えています。

問題を単純化するために、配列を例にとります。ゼロ以外の値を持つ 3 つの場所だけで arr[10] を生成します。これら 3 つのインデックスを 1 つずつランダムにすると、繰り返しのためにアルゴリズムの効率が悪くなります。

さらに難しいのは、ランク k のランダム行列を生成したいということです。これは、null 列と行がコードにバグを引き起こす可能性があるためです...今回はどのように作成しますか?

ありがとう！

4

4 に答える 4

5

これは、STL の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
}
于 2012-08-13T06:12:20.883 に答える
0

すべてのN次元配列は、（すべての要素を列挙するために）1次元にフラット化できます。5x7の配列があるとします。これは、合計35個の要素が含まれていることを意味します。

最初の要素を「埋める」と、使用可能なスロットの総数が1つ減り、アレイに34個の「空の」スポットしかないように表示できます。したがって、ここで要素を埋めるだけです。 0から33までのインデックスを作成し、その要素を見つけるときに、すでに入力されているものをスキップすることを忘れないでください。

この2番目の部分は時間がかかる可能性があるため、アレイが常に非常にまばらである場合は、それらの「取得された」スポットをすべて別のアレイにリストするだけで済みます...いいえ、あまり役に立ちません。すべてのスポットの個別のリンクリストも非効率的です。反復ごとに割り当ててトラバースするには、（比較的）時間がかかりすぎます。

本質的に、問題は、変更された配列でインデックスを作成する高速な方法を見つけることです。この場合、要素の総数はまだ取得されていないスポットを表し、スパース配列の場合、これらの取得されたスポットを記録する方法は、衝突の場合に次のランダムインデックスを生成するのにかかる時間。

配列が多かれ少なかれ密集して満たされている場合（「多かれ少なかれ」は私には不明ですが、60％〜70％を超えると予想されます）、記録を保持することができます。使用される要素の数は、繰り返されないインデックスの生成にかかる時間を上回る場合があります。

于 2012-08-13T14:50:44.180 に答える
0

配列のサイズがNで、Kがゼロ以外のエントリの数である場合は、次のようにします。

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();
}

指摘したように、ゼロ以外の要素を配列の先頭に配置してシャッフルすることもできます。一度だけ初期化する場合、これは明らかに優れたアルゴリズムです。

上記のアルゴリズムの利点はa、別のランダム行列に何度も再初期化する必要がある場合に得られます。ただ歩き回っrてください。再初期化は必要ありません。K個の非ゼロ要素の後続の挿入はすべてKステップのみを必要とします。KがNに比べて小さい場合、これは大きな勝利になる可能性があります。

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;  
}
于 2012-08-13T03:45:25.827 に答える
-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;

}

さて、私はプログラミングが初めてで、ランダムなエントリを持つマトリックスを作成する方法を探していました.これを実行して実際に機能しました.これがあなたに役立つことを願っています. :D

于 2017-03-07T23:00:19.253 に答える