Herausforderung:
Geben Sie alle unterschiedlichen Permutationen einer möglicherweise langen Liste positiver Ganzzahlen aus. Sie können davon ausgehen, dass der Vektor beim Testen weniger als 1.000 Zahlen hat, aber der Prozess sollte theoretisch für jeden Vektor mit mehr als einer Zahl unabhängig von der Größe funktionieren.
Beschränkungen:
- Sie müssen die Speichernutzung auf O (n ^ 2) beschränken , wobei n die Anzahl der Elemente im Eingabevektor ist. Du kannst kein O (n!) Haben . Das heißt, Sie können nicht alle Permutationen im Speicher speichern.
- Sie müssen die Zeitkomplexität auf O beschränken (Ergebnisgröße * n) . Wenn alle Zahlen gleich sind, ist dies O (n) , und wenn alle verschieden sind, ist dies O (n! * N) . Das heißt, Sie können keine Permutation erstellen und mit allen anderen Permutationen vergleichen, um die Unterscheidbarkeit sicherzustellen (das wäre O (n! ^ 2 * n) ).
- Empirische Messungen, die zeigen, dass Zeit- und Speicherbeschränkungen eingehalten werden, werden akzeptiert.
- Sie müssen die Permutationen tatsächlich drucken / ausgeben (da es unmöglich ist, sie zu speichern).
Wenn Sie Ihr Programm lange genug ausführen, sollten (theoretisch) alle Permutationen ausgegeben werden!
Deutliche Permutationen:
Die Liste [1, 1, 2] hat drei Permutationen, nicht sechs: [1, 1, 2] , [1, 2, 1] und [2, 1, 1] . Sie können die Reihenfolge der Ausgabe wählen.
Überschaubare Testfälle:
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]
Größerer Testfall:
Es ist unmöglich, alle Permutationen für diese auszugeben, aber es sollte theoretisch funktionieren, wenn Sie ihm genügend Zeit geben (aber nicht unbegrenzten Speicher).
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]
Sie müssen erklären, woher Sie wissen, dass alle Permutationen unterschiedlich sind und dass schließlich alle Permutationen gedruckt werden.
Dies ist Code-Golf, also gewinnt der kürzeste Code in Bytes.
quelle
Antworten:
JavaScript (ES6),
177169 ByteVerwendet den bekannten Algorithmus zur Erzeugung der nächsten lexikografischen Permutation, der meines Erachtens Speicher O (len (Array)) und Zeit O (len (Array) * len (Ausgabe)) hat. (Beachten Sie, dass die Array - Elemente in Betracht gezogen werden , in umgekehrter Reihenfolge sein, so dass beispielsweise
2, 2, 1, 1
wird aufzuzählen2, 1, 2, 1
;1, 2, 2, 1
usw.quelle
Python 3 mit Sympy , (50?) 81 Bytes
Probieren Sie es online aus!
50 Bytes, wenn eine Generatorfunktion akzeptabel ist:
Die Implementierung ist Open Source und derzeit auf Git Hub verfügbar. Zum Zeitpunkt des Schreibens befindet sich die Funktion in Zeile 983 .
Ich denke, dass dies der Fall ist, aber lassen Sie mich wissen, wenn dies nicht der Fall ist, erfüllen Sie die asymptotischen Grenzen.
Python 2, (411?) 439 Bytes
Eine golfed Version (auch Fälle , ignoriert wir nicht Abdeckung erforderlich) in Python 2 (immer noch den mit dem integrierten in
itertools.permutations function
) kommt bei 439 Bytes oder 411 ohne zusätzlichen Text eher zu drucken als generieren (diefor v in h(input()):print v
):(Hinweis: Hierbei wird der Python 2-Golf mit alternierenden Tabulatoren und Leerzeichen für Einrückungen verwendet.)
quelle
C ++ (gcc) , 203 Bytes
Anscheinend hat C ++ dies als eingebaute Funktion ...
Probieren Sie es online aus!
Ungolfed Code: TIO Link.
Dies verwendet
O(n)
Speicher (garantiert durchstd::vector
) und optimale Laufzeit.Einige Optimierungen im Code:
import
anstelle voninclude
(G ++ veraltete Erweiterung)bits/stdc++.h
(vorkompilierter Header enthält alle anderen Header) anstelle mehrerer erforderlicher Header. Oft verlangsamt dies die Kompilierungszeit.using namespace std
Das ist bekanntermaßen eine schlechte Idee .puts("")
stattcout<<'\n'
zum Schreiben einer neuen Zeile. Dies ist normal für das C-Programm, fühlt sich aber für mich komisch an. Ich denke, das sollte erwähnt werden.main
Rückgabewert (int
) kann weggelassen werden.Ansonsten (abgesehen vom Löschen von Leerzeichen) ist es die gleiche Art und Weise, wie ich oft in C ++ programmiere.
Einige mögliche Optimierungen: (Ich weiß nicht, ob dies standardmäßig zulässig ist):
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
für mögen1 2 1 3
. Dies ermöglicht das Speichern von mehr als 9 Bytes.#import
die Header in C ++ oder einen kürzeren Headernamen zu verwenden.quelle
std::sort
die Zeitkomplexität nicht überläuftusing 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);}
@ ist newlineScala (48 Bytes)
Probieren Sie es online aus
Permutationen gibt einen Iterator über verschiedene Permutationen zurück.
quelle
JavaScript (Node.js) ,
137128123 ByteProbieren Sie es online aus!
quelle
APL (NARS), 156 Zeichen, 312 Bytes
Sie, F und G wären 2 Funktionen, um zusammen zu verwenden ... G ordnen Sie zuerst das Array an, als wenden Sie auf das ordinierte Array die Funktion F an und schreiben Sie Permutationen mit der Beobachtung, dass es besser ist, nicht zur Rekursion zu gehen, wenn das Element bereits gefunden wurde (weil das ganze Ergebnis schon gefunden wäre). Ich weiß nicht, ob dies zu allen Einschränkungen passt ... Test:
quelle