使用线性搜索为二维数组生成唯一数字

Question

程序编译，我可以输入一个数字，但它不生成或显示数组。当我在 randomFillUnique 函数中使用线性搜索取出 while 条件时，它会生成并显示数组，但不是唯一数字。我需要一个没有重复数字的二维数组。

#include <iostream>
#include <string>
#include <random>
#include <ctime>
using namespace std;

int** gen2Array(int n);
void randomFillUnique(int** arr, int n);
bool lSearch(int** arr, int n, int target);
void display(int** arr, int n);

int main()
{
    int number;
    cout << "Enter a number: ";
    cin >> number;
    randomFillUnique(gen2Array(number), number);
    system("pause");
    return 0;
}
int** gen2Array(int n)
{
    int** arr2D = new int*[n];
    for (int index = 0; index < n; index++)
        arr2D[index] = new int[n];
    return arr2D;
}
void randomFillUnique(int** arr, int n)
{
    static default_random_engine e;
    uniform_int_distribution<int> u(1, n*n);
    e.seed(static_cast<int>(time(NULL)));

    bool result = false;
    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < n; col++)
        {
            arr[row][col] = u(e);   //generate random number
            result = lSearch(arr, n, arr[row][col]);
            while (result == true)
            {
                arr[row][col] = u(e);   //generate random number
                result = lSearch(arr, n, arr[row][col]);
            }
        }
    }
    display(arr, n);
    delete[] arr;
}
bool lSearch(int** arr, int n, int target)
{
    bool found = false;
    for (int row = 0; row < n; row++)
        for (int col = 0; col < n; col++)
        {
            if (arr[row][col] == target)
            {
                found = true;
                return found;
            }
        }
    return found;
}
void display(int** arr, int n)
{
    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < n; col++)
            cout << arr[row][col];
        cout << endl;
    }
}

Answer 1

因为您在 lsearch 之前将数组中的条目设置为 u(e)，lsearch 始终 returns true 并且您的 while 将永远循环。下面的代码改编自您的代码，应该可以解决这个问题（我假设其余代码的行为与预期的一样）。正如 user4581301 指出的那样，可能有更好的方法，但我希望你的方法足以让它发挥作用。

void randomFillUnique(int** arr, int n)
{
static default_random_engine e;
uniform_int_distribution<int> u(1, n*n);
e.seed(static_cast<int>(time(NULL)));
int nextEntry;
bool result = false;
for (int row = 0; row < n; row++)
{
    for (int col = 0; col < n; col++)
    {
        result = true;
        while (result == true)
        {
            nextEntry = u(e);   //generate random number
            result = lSearch(arr, n, nextEntry);
            if (result != true)
               {arr[row][col]=nextEntry;}
        }
    }
}
display(arr, n);
delete[] arr;
}

Answer 2

另一种方法是使用 iota:

创建一个包含所有将进入数组的唯一整数的容器

std::vector<int> invalues(n*n, 0);
std::iota(invalues.begin(), invalues.end(), 1);

然后洗牌那个容器：

std::shuffle(invalues.begin(), invalues.end(),
             std::mt19937{std::random_device{}()});

然后将值一一输入矩阵。

您也可以使用 vector<vector<int>> 而不是内置数组：

using matrix = std::vector<std::vector<int>>;

// initialising a vector<vector<int>> to be a certain size is a bit clumsy
matrix m(size_y, std::vector<int>(size_x, 0));

然后将输入值输入矩阵：

for (auto &row : m) {
  for (auto &elem : row) {
    elem = invalues.back();
    invalues.pop_back();
  }
}

然后显示矩阵：

for (const auto &row : m) {
  for (const auto &elem : row) {
    std::cout << elem << " ";
  }
  std::cout << std::endl;
}

Here's a full example in an online compiler.

Answer 3

好的。这是我评论过的更简单的方法。如果不允许使用 std::vector，一个简单的一维向量就足够了，但是一个理智的软件工程师在选择它而不是 vector 之前会非常非常认真地思考。

我做了一些其他更改以修复其他几个错误。

#include <iostream>
#include <string>
#include <random>
#include <vector>
#include <algorithm> // std::shuffle and std::iota
#include <ctime>
using namespace std;

int** gen2Array(int n);
void randomFillUnique(int** arr, int n);
bool lSearch(int** arr, int n, int target);
void display(int** arr, int n);
//Added to properly delete the 2dArray
void del2Array(int ** arr, int n);

int main()
{
    int number = 10;
    randomFillUnique(gen2Array(number), number);
    system("pause");
    return 0;
}
int** gen2Array(int n)
{
    int** arr2D = new int*[n];
    for (int index = 0; index < n; index++)
        arr2D[index] = new int[n];
    return arr2D;
}

//Added to properly delete the 2dArray
void del2Array(int ** arr,
               int n)
{
    for (int index = 0; index < n; index++)
        delete arr[index];
    delete arr;
}
void randomFillUnique(int** arr, int n)
{
    //do the seeding here
    static default_random_engine e(static_cast<int>(time(NULL)));
// otherwise
//    e.seed(static_cast<int>(time(NULL)));
// runs every time reseeding the RNG to potentially the give the same results
// if run more than once in a second. Plus the seeding is expensive.

    std::vector<int> v(n*n); // make and size vector
    std::iota (v.begin(), v.end(), 0); // init vector with 1 through n*n
    std::shuffle(v.begin(), v.end(), e);

    size_t index = 0;
    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < n; col++)
        {
            arr[row][col] = v[index++];   //generate random number
        }
    }
    display(arr, n);
    del2Array (arr, n); // frankly I don't think you want his here
                        // why fill an array only to delete it?
                        // more logical to display and delete back in main.
}

void display(int** arr, int n)
{
    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < n; col++)
            cout << arr[row][col] << "\t"; //added a tab to make the printing easier to read
        cout << endl;
    }
}

Documentation on std::vector

Documentation on std::shuffle

Documentation on std::iota. 正是使用这种技术来演示 iota。有趣吧？

使用线性搜索为二维数组生成唯一数字

generate unique numbers to 2-Dimensional array using linear search

c++

arrays

algorithm

multidimensional-array

linear-search