Geben Sie alle unterschiedlichen Permutationen eines Vektors aus

9

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 also gewinnt der kürzeste Code in Bytes.

Stewie Griffin
quelle
2
Gibt es eine Referenzimplementierung, die diese Komplexitätsanforderungen erfüllt?
Steven H.
1
Es sollte nicht zu schwierig sein, einen Algorithmus zu entwickeln, der die Anforderungen erfüllt (er ist jedoch möglicherweise nicht sehr golfig). Ich bin kein Programmierer oder Mathematiker, ich bin nichts anderes als ein bescheidener Herausforderungsschreiber. Ich werde das knifflige Zeug für euch Jungs / Mädchen hinterlassen :)
Stewie Griffin
6
Ich denke, angesichts der Einschränkungenseigenschaften wäre dies besser als schnellster Code, da Code Golf normalerweise für die clevere Verwendung von integrierten Funktionen und Sprachfunktionen gedacht ist.
Uriel
3
"Es sollte nicht zu schwer sein" ≠ "es ist möglich"
Fatalize
1
Ist eine Erzeugungsfunktion akzeptabel oder müssen wir einer solchen Lösung zum Drucken / Ausgeben eine Boilerplate hinzufügen?
Jonathan Allan

Antworten:

6

JavaScript (ES6), 177 169 Byte

a=>{s=''+a
do{console.log(a)
k=a.findIndex((e,i)=>a[i-1]>e)
if(~k)t=a[k],a[k]=a[l=a.findIndex(e=>e>t)],a[l]=t,a=a.map((e,i)=>i<k?a[k+~i]:e)
else a.reverse()}while(a!=s)}

Verwendet 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, 1wird aufzuzählen 2, 1, 2, 1; 1, 2, 2, 1usw.

Neil
quelle
5

Python 3 mit Sympy , (50?) 81 Bytes

lambda a:[print(v)for v in sympy.iterables.multiset_permutations(a)]
import sympy

Probieren Sie es online aus!

50 Bytes, wenn eine Generatorfunktion akzeptabel ist:

import sympy
sympy.iterables.multiset_permutations

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 (die for v in h(input()):print v):

from itertools import*
def h(a,z=-1,g=1):
 x=[v for v in[g,[[v,a.count(v)]for v in set(a)]][g==1]if 0<v[1]];S=sum([v[1]for v in x])
 if x==x[:1]:k,v=x[0];yield[k for i in range([[0,z][z<=v],v][z<1])]
 elif all(v<2for k,v in x):
    for p in permutations([v[0]for v in x],[z,None][z<0]):yield list(p)
 else:
    z=[S,z][z>-1];i=0
    for k,v in x:
     x[i][1]-=1
     for j in h([],z-1,x):
        if j:yield[k]+j
     x[i][1]+=1;i+=1
for v in h(input()):print v

(Hinweis: Hierbei wird der Python 2-Golf mit alternierenden Tabulatoren und Leerzeichen für Einrückungen verwendet.)

Jonathan Allan
quelle
Es ist nicht erforderlich zu schreiben, "zum Zeitpunkt des Schreibens befindet sich die Funktion in Zeile 983" . Sie können einen Link zum neuesten Commit erstellen : github.com/sympy/sympy/blob/… .
Orlp
@orlp Gibt es da nicht schon einen Permalink?
Erik der Outgolfer
@EriktheOutgolfer Ich habe einen Link zu einem bestimmten Commit erstellt, nicht zu 'der neuesten Version'. Das bedeutet, dass mein Link durch zukünftige Änderungen nicht veraltet ist.
Orlp
2

C ++ (gcc) , 203 Bytes

Anscheinend hat C ++ dies als eingebaute Funktion ...

#import<bits/stdc++.h>
using namespace std;main(){vector<int>v;int x;while(cin>>x)v.push_back(x);sort(v.begin(),v.end());do{for(int y:v)cout<<y<<' ';puts("");}while(next_permutation(v.begin(),v.end()));}

Probieren Sie es online aus!

Ungolfed Code: TIO Link.

Dies verwendet O(n)Speicher (garantiert durch std::vector) und optimale Laufzeit.

Einige Optimierungen im Code:

  • Verwenden Sie importanstelle von include(G ++ veraltete Erweiterung)
  • Verwenden Sie bits/stdc++.h(vorkompilierter Header enthält alle anderen Header) anstelle mehrerer erforderlicher Header. Oft verlangsamt dies die Kompilierungszeit.
  • using namespace stdDas ist bekanntermaßen eine schlechte Idee .
  • Verwenden Sie puts("")statt cout<<'\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.
  • mainRü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):

  • Geben Sie die Arraygröße ein, bevor Sie Elemente eingeben. Dies ermöglicht ein Array mit dynamischer Größe und spart insgesamt 30 Byte .
  • Trennen Sie die Ausgänge nicht mit Trennzeichen. Die Ausgabe wird also 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 1für mögen 1 2 1 3. Dies ermöglicht das Speichern von mehr als 9 Bytes.
  • Während es in C erlaubt ist, Header wegzulassen, weiß ich nicht, ob es eine kürzere Möglichkeit gibt, diese Funktionen ohne #importdie Header in C ++ oder einen kürzeren Headernamen zu verwenden.
user202729
quelle
Vielleicht sollten Sie erwähnen, warum std::sortdie Zeitkomplexität nicht überläuft
l4m2
Auch 2 Bytes gespeichertusing 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()));}
l4m2
#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 newline
l4m2
2

Scala (48 Bytes)

def%(i:Seq[Int])=i.permutations.foreach(println)

Probieren Sie es online aus

Permutationen gibt einen Iterator über verschiedene Permutationen zurück.

jrook
quelle
2

JavaScript (Node.js) , 137 128 123 Byte

s=>f(x=c=[],s.map(g=i=>g[i]=-~g[i]));f=i=>Object.keys(g).map(i=>g(i,--g[i]||delete g[i],f(x[c++]=i),c--))<1&&console.log(x)

Probieren Sie es online aus!

s=>
    f(
        x=c=[],
        s.map(g=i=>g[i]=-~g[i]) // O(n) if all same, <=O(n^2) if different
    )
;
f=i=>
    Object.keys(g).map( // for(i in g) breaks when other items get removed
        i=>g(
            i,
            --g[i]||delete g[i], // O(left possible numbers)<O(child situations)
            f(x[c++]=i),
            c--
        )
    )<1
&&
    console.log(x)
14 m2
quelle
0

APL (NARS), 156 Zeichen, 312 Bytes

r←d F w;i;k;a;m;j;v
r←w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m
   v←m,¨(d,m)∇w[a∼i]
   →H×⍳0=↑⍴v⋄⎕←∊d,v
H: j←m
B: i+←1
C: →A×⍳i≤k

G←{⍬F⍵[⍋⍵]}

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:

  G 1 1 2
1 1 2 
1 2 1 
2 1 1 

  G 1 2 3 2
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 

  G 'abb'
abb
bab
bba
RosLuP
quelle