-1
I need to do a program that generates N numbers without repetition between a set of 1 to 600000 numbers. the values of N are 50000,10000,50000,100000 and 500000. These numbers will be stored in a vector. What is the most efficient way to do this?
1 answer
1
You can fill this vector sequentially and then shuffle its contents, for example:
#include <cstdlib>
#include <ctime>
#include <iostream>
int main( int argc, char * argv[] )
{
//
// Recupera N como argumento da linha de comando
//
int N = std::atoi( argv[1] );
//
// Vetor contendo N posições
//
int vetor[ N ];
//
// Preenche vetor sequencialmente de 1 até N
//
for( int i = 1; i <= N; i++ )
vetor[ i - 1 ] = i;
//
// "Embaralha" vetor sorteando duas posicoes aleatórias e invertendo seus conteúdos
// por N * 2 vezes
//
std::srand(std::time(NULL));
for( int i = 0; i < (N * 2); i++ )
{
int a = std::rand() % N;
int b = std::rand() % N;
int tmp = vetor[a];
vetor[a] = vetor[b];
vetor[b] = tmp;
}
//
// Evia conteudo do vetor para a saida padrao
//
for( int i = 0; i < N; i++ )
std::cout << vetor[i] << " ";
std::cout << std::endl;
return 0;
}
Testing (N=10):
$ ./shuffle 10
2 3 1 6 8 10 7 5 9 4
Testing (N=100):
$ ./shuffle 100
23 58 21 88 15 99 35 44 79 37 4 2 9 60 5 33 27 34 73 95 32 65 8 72 59 24 86 81 36 90 71 68 76 53 82 17 91 70 67 75 94 42 92 13 61 100 98 80 10 74 3 39 49 18 63 97 84 62 69 48 55 77 16 29 87 11 56 14 22 25 41 51 45 43 85 66 1 47 28 7 96 19 54 40 31 30 46 38 57 20 83 50 6 26 52 64 89 12 93 78
Testing (N=1000):
$ ./shuffle 1000
348 621 835 444 606 614 781 360 253 234 292 10 165 11 736 551 974 393 574 70 723 555 667 495 369 758 870 877 118 389 676 552 272 558 783 963 809 331 850 904 139 629 147 108 952 482 740 859 44 670 51 662 309 593 885 135 600 703 684 60 975 965 169 64 589 310 399 398 232 576 378 132 744 77 149 454 107 582 931 111 235 421 174 447 898 427 89 439 972 796 392 1000 721 247 411 842 724 897 448 42 772 780 324 701 26 763 966 840 978 342 316 175 372 822 200 999 56 431 806 829 511 811 15 375 86 812 127 862 709 437 97 714 340 697 834 673 337 883 549 745 957 126 708 471 327 264 499 435 197 795 520 354 817 173 230 481 254 948 546 155 540 237 201 371 682 280 788 312 958 82 924 524 831 769 742 646 700 526 203 428 969 734 488 881 776 138 187 205 713 906 474 853 271 699 901 373 490 777 596 65 35 994 876 688 38 397 637 991 430 592 150 180 158 960 314 707 449 295 679 674 405 990 202 808 468 216 305 121 303 250 268 735 61 426 170 443 638 928 307 93 640 30 80 391 466 370 704 43 509 366 616 151 313 766 480 62 212 450 404 333 839 848 818 837 379 160 429 677 191 921 751 856 289 79 109 417 628 932 215 384 980 346 255 318 756 681 152 828 786 21 304 46 607 651 844 568 617 465 344 613 13 875 359 624 78 656 206 413 671 601 819 211 414 594 715 608 825 687 286 266 525 764 189 130 878 409 911 402 198 213 219 210 879 39 37 872 571 903 422 961 615 896 407 418 577 225 347 535 661 76 597 492 208 319 182 479 285 644 45 323 334 503 433 364 365 504 912 251 88 496 386 161 738 194 238 16 352 712 752 762 512 117 997 630 94 22 66 81 693 947 880 400 869 998 368 145 142 498 973 339 133 690 868 533 110 945 209 226 188 40 395 168 610 343 137 236 871 826 694 789 813 749 472 622 425 486 328 807 791 258 166 550 493 573 913 984 380 556 523 910 17 353 335 779 893 332 223 243 442 530 557 131 461 500 508 317 487 445 695 655 181 140 69 824 299 177 84 58 440 408 105 603 261 153 698 71 29 519 269 192 460 891 306 619 706 485 381 731 854 279 491 737 367 846 757 938 124 178 256 102 917 668 410 665 578 612 159 631 281 567 345 802 239 114 717 759 288 9 521 941 588 385 68 753 527 420 326 259 6 561 586 920 611 635 267 916 790 388 691 106 985 100 605 119 33 591 942 438 888 55 970 977 284 804 827 657 462 659 220 23 663 748 244 362 477 104 297 246 995 727 116 478 798 801 356 642 517 675 609 463 581 843 988 584 643 725 664 231 241 240 129 195 497 908 702 579 899 936 355 641 273 294 730 633 338 814 432 74 618 711 123 564 935 939 167 857 257 836 716 27 92 99 855 522 453 962 274 387 358 501 489 993 179 803 290 18 821 128 933 415 602 146 506 456 943 510 184 976 847 374 144 12 537 473 357 308 851 755 547 351 514 185 494 728 63 572 886 394 599 361 122 196 747 423 792 754 377 654 560 934 760 424 54 672 833 892 765 475 689 52 554 949 311 604 83 669 464 85 19 32 125 529 7 296 953 103 761 190 696 894 538 587 363 98 513 852 768 41 739 799 222 982 767 1 959 625 627 996 302 172 810 989 683 90 800 476 580 293 301 964 186 162 570 575 320 626 775 163 262 648 971 865 336 434 446 330 741 95 954 900 918 134 207 436 951 774 396 249 350 685 275 101 36 298 909 983 968 227 718 467 820 176 889 794 771 543 787 710 300 944 907 171 652 3 562 832 516 884 265 412 401 532 743 565 653 680 484 660 923 816 778 5 563 719 927 376 34 458 845 57 528 204 154 882 981 536 502 518 157 585 955 902 785 221 87 926 459 838 595 830 841 75 283 849 598 815 686 141 986 925 263 8 515 325 383 645 59 115 390 863 559 403 451 914 548 866 539 650 382 531 873 797 634 242 164 248 692 341 218 469 782 858 287 566 720 470 773 252 874 229 915 507 620 639 770 245 930 452 406 457 199 750 956 705 217 53 732 291 545 505 276 183 887 895 569 553 270 260 49 322 4 96 91 541 861 544 649 967 14 666 67 992 28 890 48 441 937 113 746 940 636 623 632 946 416 729 583 112 483 72 733 50 143 278 2 193 860 47 156 315 136 823 120 148 534 419 864 321 590 73 647 214 929 678 277 31 805 784 979 919 905 25 726 228 329 233 793 867 722 455 349 282 987 950 24 658 922 542 20 224
Browser other questions tagged c++
You are not signed in. Login or sign up in order to post.
Fisher-Yates, and other variants that do shuffle. Already have a lot of answers on the site explaining: https://answall.com/search?q=sem+repeti%C3%A7%C3%A3o - Note that if you need a few values of a large range, you have to optimize the algorithm to not waste memory for nothing. For "few of many" I always draw starting from n, and decreasing 0 to n - 1 at each draw, inserting the new value in the right position compared to the previous ones.
– Bacco