On some randomized algorithms and their evaluation
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914905778552832 |
|---|---|
| author | Yordzhev, Krasimir |
| author_facet | Yordzhev, Krasimir |
| contents | The paper considers implementations of some randomized algorithms in connection with obtaining a random $n^2 \times n^2$ Sudoku matrix with programming language C++. For this purpose we describes the set $Π_n$ of all $(2n) \times n$ matrices, consisting of elements of the set $\mathbb{Z}_n =\{ 1,2,\ldots ,n\}$, such that every row is a permutation. We emphasize the relationship between these matrices and the $n^2 \times n^2$ Sudoku matrices. An algorithm to obtain random $Π_n$ matrices is presented in this paper. Several auxiliary algorithms that are related to the underlying problem have been described. We evaluated all algorithms according to two criteria - probability evaluation, and time for generation of random objects and checking of belonging to a specific set. This evaluations are interesting from both theoretical and practical point of view because they are particularly useful in the analysis of computer programs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04445 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On some randomized algorithms and their evaluation Yordzhev, Krasimir Discrete Mathematics Data Structures and Algorithms Combinatorics 05B20, 65C05, 68W40 F.2; G.2 The paper considers implementations of some randomized algorithms in connection with obtaining a random $n^2 \times n^2$ Sudoku matrix with programming language C++. For this purpose we describes the set $Π_n$ of all $(2n) \times n$ matrices, consisting of elements of the set $\mathbb{Z}_n =\{ 1,2,\ldots ,n\}$, such that every row is a permutation. We emphasize the relationship between these matrices and the $n^2 \times n^2$ Sudoku matrices. An algorithm to obtain random $Π_n$ matrices is presented in this paper. Several auxiliary algorithms that are related to the underlying problem have been described. We evaluated all algorithms according to two criteria - probability evaluation, and time for generation of random objects and checking of belonging to a specific set. This evaluations are interesting from both theoretical and practical point of view because they are particularly useful in the analysis of computer programs. |
| title | On some randomized algorithms and their evaluation |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics 05B20, 65C05, 68W40 F.2; G.2 |
| url | https://arxiv.org/abs/2408.04445 |