2

我想生成一个具有固定稀疏度和随机索引和值的矩阵。

为了简化问题，以数组为例：生成一个 arr[10] 只有 3 个位置且非零值。如果我只是将这 3 个索引一一随机，由于重复，算法的效率很差。

更困难的是，我还想生成一个秩为 k 的随机矩阵，因为 null cols 和 rows 可能会导致我的代码出现错误......这次如何做到？

谢谢！

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 并且 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 回答
0

任何 N 维数组都可以展平为一维（为了枚举其所有元素）。假设您有一个 5x7 数组 - 这意味着其中总共有 35 个元素。

一旦你“填充”了第一个元素，可用槽的总数就会减少一个，所以你可以看到你的数组现在只有 34 个“空”点 - 因此你现在需要做的就是在索引在 0 到 33 之间，并记住在定位该元素时跳过已经填充的索引。

第二部分可能会很耗时，所以如果你的数组总是非常稀疏，你可以在一个单独的数组中列出所有那些“采取”的点......不，这对你没有多大帮助。所有点的单独链接列表也将效率低下 - 将需要太多时间（相对）来分配和遍历每次迭代。

本质上，问题是在修改后的数组中找到一种快速索引方法，其中元素的总数表示尚未拍摄的点，对于稀疏数组，记录这些点的任何方式都将超过发生碰撞时生成下一个随机索引所需的时间。

只有当数组或多或少密集填充时（“或多或少”对我来说是一个未知值，但我希望它高于 60%-70%）才能保持记录使用的元素的数量可能超过生成非重复索引所需的时间。

于 2012-08-13T14:50:44.180 回答
-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 回答