Tantangan:
Keluarkan semua permutasi berbeda dari daftar, mungkin panjang, dari bilangan bulat positif. Anda dapat mengasumsikan bahwa vektor memiliki kurang dari 1.000 angka saat pengujian, tetapi prosesnya secara teori seharusnya bekerja untuk vektor apa pun dengan lebih dari satu angka terlepas dari ukurannya.
Pembatasan:
- Anda harus membatasi penggunaan memori menjadi O (n ^ 2) , di mana n adalah jumlah elemen dalam vektor input. Anda tidak dapat memiliki O (n!) . Itu berarti Anda tidak dapat menyimpan semua permutasi dalam memori.
- Anda harus membatasi kompleksitas waktu hingga O (ukuran hasil * n) . Jika semua angka sama, maka ini akan menjadi O (n) , dan jika semua berbeda, maka ini akan menjadi O (n! * N) . Itu berarti Anda tidak dapat membuat permutasi dan memeriksanya terhadap semua permutasi lainnya untuk memastikan perbedaan (itu adalah O (n! ^ 2 * n) ).
- Pengukuran empiris untuk menunjukkan bahwa batasan waktu dan memori terpenuhi diterima.
- Anda harus benar-benar mencetak / mengeluarkan permutasi (karena tidak mungkin untuk menyimpannya).
Jika Anda menjalankan program Anda cukup lama, maka semua permutasi harus dikeluarkan (secara teori)!
Permutasi berbeda:
Daftar [1, 1, 2] memiliki tiga permutasi, bukan enam: [1, 1, 2] , [1, 2, 1] dan [2, 1, 1] . Anda dapat memilih urutan output.
Kasus uji yang dapat dikelola:
Input:
[1, 2, 1]
Output:
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
Input:
[1, 2, 3, 2]
Output:
[1, 2, 2, 3]
[1, 2, 3, 2]
[1, 3, 2, 2]
[2, 1, 2, 3]
[2, 1, 3, 2]
[2, 2, 1, 3]
[2, 2, 3, 1]
[2, 3, 1, 2]
[2, 3, 2, 1]
[3, 1, 2, 2]
[3, 2, 1, 2]
[3, 2, 2, 1]
Input:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Kasus uji yang lebih besar:
Tidak mungkin untuk mengeluarkan semua permutasi untuk yang ini, tetapi harus bekerja secara teori jika Anda memberinya cukup waktu (tetapi bukan memori tidak terbatas).
Input:
[1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900]
Anda harus menjelaskan bagaimana Anda tahu bahwa semua permutasi berbeda, dan pada akhirnya semua permutasi akan dicetak.
Ini adalah kode-golf sehingga kode terpendek dalam byte menang.
sumber
Jawaban:
JavaScript (ES6),
177169 byteMenggunakan algoritma generasi permutasi leksikografis berikutnya yang terkenal, yang saya yakini memiliki memori O (len (array)) dan waktu O (len (array) * len (output)). (Perhatikan bahwa elemen-elemen array dianggap dalam urutan terbalik, sehingga mis.
2, 2, 1, 1
Akan disebutkan2, 1, 2, 1
;1, 2, 2, 1
dll.sumber
Python 3 dengan sympy , (50?) 81 byte
Cobalah online!
50 byte jika fungsi generator dapat diterima:
Implementasinya adalah open source dan saat ini tersedia di hub git , pada saat penulisan fungsi ini berada di baris 983 .
Saya pikir memang demikian, tetapi beri tahu saya jika tidak, penuhi batasan asimptotik.
Python 2, (411?) 439 byte
Versi golf (juga mengabaikan case yang tidak perlu kita bahas) dengan Python 2 (masih menggunakan built-in
itertools.permutations function
) muncul pada 439 byte , atau 411 tanpa pelat tambahan untuk mencetak daripada menghasilkan (:)for v in h(input()):print v
:(catatan: ini menggunakan golf Python 2 tab dan spasi bolak-balik untuk indentasi)
sumber
C ++ (gcc) , 203 byte
Rupanya C ++ memiliki ini sebagai fungsi bawaan ...
Cobalah online!
Kode tidak dikunci: TIO link.
Ini menggunakan
O(n)
memori (dijamin olehstd::vector
) dan runtime optimal.Beberapa optimasi dalam kode:
import
sebagai gantiinclude
(ekstensi G ++ tidak digunakan)bits/stdc++.h
(header yang dikompilasi berisi semua header lainnya) alih-alih beberapa header yang diperlukan. Seringkali ini membuat waktu kompilasi lebih lambat.using namespace std
yang dikenal sebagai ide yang buruk .puts("")
sebagai ganticout<<'\n'
untuk menulis baris baru. Ini normal untuk program C, tetapi terasa aneh bagi saya. Jadi saya pikir ini harus disebutkan.main
nilai balik (int
) dapat dihilangkan.Kalau tidak (terlepas dari penghapusan spasi putih) itu adalah cara yang sama bagaimana saya sering memprogram dalam C ++.
Beberapa kemungkinan optimasi: (Saya tidak tahu apakah itu diizinkan secara default):
1 1 2 3 1 1 3 2 1 2 1 3 1 2 3 1 1 3 1 2 1 3 2 1 2 1 1 3 2 1 3 1 2 3 1 1 3 1 1 2 3 1 2 1 3 2 1 1
untuk1 2 1 3
. Ini memungkinkan menghemat lebih banyak 9 byte.#import
header di C ++, atau nama header yang lebih pendek.sumber
std::sort
kompleksitas waktu tidak meluapusing namespace std;main(){vector<int>v;for(int x;cin>>x;v.push_back(x));sort(v.begin(),v.end());do for(int y:v)cout<<y<<' ';while(puts(""),next_permutation(v.begin(),v.end()));}
#import<bits/stdc++.h>@#define Q v.begin(),v.end())@using namespace std;main(){vector<int>v;for(int x;cin>>x;v.push_back(x));sort(Q;do for(int y:v)cout<<y<<' ';while(puts(""),next_permutation(Q);}
@ adalah baris baruScala (48 byte)
Cobalah online
permutasi mengembalikan iterator melalui permutasi yang berbeda.
sumber
JavaScript (Node.js) ,
137128123 byteCobalah online!
sumber
APL (NARS), 156 karakter, 312 byte
Mereka, F dan G akan menjadi 2 fungsi untuk menggunakan togheter ... G pertama memesan array daripada berlaku untuk array yang ditahbiskan fungsi F dan menulis permutasi menggunakan pengamatan bahwa jika elemen sudah ditemukan, lebih baik tidak pergi ke rekursi (karena semua hasilnya pasti sudah ditemukan). Saya tidak tahu apakah ini cocok dengan semua restritions ... Uji:
sumber