Afficher toutes les permutations distinctes d'un vecteur

9

Défi:

Afficher toutes les permutations distinctes d'une liste, potentiellement longue, d'entiers positifs. Vous pouvez supposer que le vecteur a moins de 1 000 nombres lors des tests, mais le processus devrait en théorie fonctionner pour tout vecteur avec plus d'un nombre, quelle que soit sa taille.

Restrictions:

  • Vous devez limiter l'utilisation de la mémoire à O (n ^ 2) , où n est le nombre d'éléments dans le vecteur d'entrée. Vous ne pouvez pas avoir O (n!) . Cela signifie que vous ne pouvez pas stocker toutes les permutations en mémoire.
  • Vous devez limiter la complexité temporelle à O (taille du résultat * n) . Si tous les nombres sont égaux, alors ce sera O (n) , et si tous sont distincts, alors ce sera O (n! * N) . Cela signifie que vous ne pouvez pas créer une permutation et la comparer à toutes les autres permutations pour garantir la distinction (ce serait O (n! ^ 2 * n) ).
  • Les mesures empiriques pour montrer que les restrictions de temps et de mémoire sont respectées sont acceptées.
  • Vous devez réellement imprimer / sortir les permutations (car il est impossible de les stocker).

Si vous exécutez votre programme assez longtemps, toutes les permutations devraient être générées (en théorie)!

Permutations distinctes:

La liste [1, 1, 2] comporte trois permutations, pas six: [1, 1, 2] , [1, 2, 1] et [2, 1, 1] . Vous pouvez choisir l'ordre de sortie.


Cas de test gérables:

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]

Cas de test plus grand:

Il est impossible de produire toutes les permutations pour celui-ci, mais cela devrait fonctionner en théorie si vous lui avez donné suffisamment de temps (mais pas de mémoire illimitée).

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]

Vous devez expliquer comment vous savez que toutes les permutations sont distinctes et que toutes les permutations seront éventuellement imprimées.

C'est le donc le code le plus court en octets gagne.

Stewie Griffin
la source
2
Existe-t-il une implémentation de référence qui répond à ces exigences de complexité?
Steven H.
1
Il ne devrait pas être trop difficile de trouver un algorithme qui réponde aux exigences (il pourrait ne pas être très golfique cependant). Je ne suis ni programmeur ni mathématicien, je ne suis qu'un humble écrivain de challenge. Je vais laisser les choses délicates pour vous les gars / filles :)
Stewie Griffin
6
Je pense qu'étant donné les caractéristiques des restrictions, ce serait mieux comme code le plus rapide, car le code golf est généralement destiné à une utilisation intelligente des fonctionnalités intégrées et du langage.
Uriel
3
"Ça ne devrait pas être trop dur" ≠ "c'est possible"
Fatalize
1
Une fonction de génération est-elle acceptable ou devons-nous ajouter un passe-partout à une telle solution pour imprimer / imprimer?
Jonathan Allan

Réponses:

6

JavaScript (ES6), 177 169 octets

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)}

Utilise le prochain algorithme de génération de permutation lexicographique bien connu, qui, je crois, a la mémoire O (len (tableau)) et le temps O (len (tableau) * len (sortie)). (Notez que les éléments du tableau sont considérés comme étant dans l'ordre inverse, de sorte que p. Ex. 2, 2, 1, 1Énumérera jusqu'à 2, 1, 2, 1; 1, 2, 2, 1etc.

Neil
la source
5

Python 3 avec sympy , (50?) 81 octets

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

Essayez-le en ligne!

50 octets si une fonction de générateur est acceptable:

import sympy
sympy.iterables.multiset_permutations

L'implémentation est open source et actuellement disponible sur git hub , au moment de l'écriture, la fonction est à la ligne 983 .

Je pense que oui, mais faites-moi savoir si ce n'est pas le cas, remplissez les limites asymptotiques.


Python 2, (411?) 439 octets

Une version golfée (en ignorant également les cas que nous ne sommes pas tenus de couvrir) en Python 2 (toujours en utilisant le intégré itertools.permutations function) arrive à 439 octets , ou 411 sans aucun passe-partout supplémentaire à imprimer plutôt que de générer (le 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

(note: ceci utilise le golf Python 2 de tabulation et d'espaces alternés pour les retraits)

Jonathan Allan
la source
Il n'est pas nécessaire d'écrire "au moment de l'écriture, la fonction est à la ligne 983" , vous pouvez créer un lien permanent vers le dernier commit: github.com/sympy/sympy/blob/… .
orlp
@orlp N'y a-t-il pas déjà un permalien?
Erik the Outgolfer
@EriktheOutgolfer J'ai lié à un commit spécifique, pas à «la dernière version», ce qui signifie que mon lien ne sera plus obsolète en cas de modifications futures.
orlp
2

C ++ (gcc) , 203 octets

Apparemment, C ++ a cela comme une fonction intégrée ...

#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()));}

Essayez-le en ligne!

Code non golfé: lien TIO.

Cela utilise de la O(n)mémoire (garantie par std::vector) et une durée d'exécution optimale.

Quelques optimisations dans le code:

  • Utiliser à la importplace de include(extension obsolète G ++)
  • Utilisez bits/stdc++.h(l'en-tête précompilé contient tous les autres en-têtes) au lieu de plusieurs en-têtes nécessaires. Cela ralentit souvent le temps de compilation.
  • using namespace stdqui est connu pour être une mauvaise idée .
  • Utilisez puts("")au lieu de cout<<'\n'pour écrire une nouvelle ligne. C'est normal pour le programme C, mais c'est bizarre pour moi. Je pense donc que cela devrait être mentionné.
  • mainla valeur de retour ( int) peut être omise.

Sinon (à part la suppression des espaces blancs), c'est de la même manière que je programme souvent en C ++.

Quelques optimisations possibles: (je ne sais pas si cela est autorisé par défaut):

  • Entrez la taille du tableau avant de saisir les éléments. Cela permettra un tableau de taille dynamique, économisant globalement 30 octets .
  • Pas séparer les sorties avec des séparateurs. Ainsi , la sortie sera comme 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 1pour 1 2 1 3. Cela permet d'économiser plus de 9 octets.
  • Alors qu'en C, il est permis d'omettre les en-têtes, je ne sais pas s'il existe un moyen plus court d'utiliser ces fonctions sans #importles en-têtes en C ++, ou un nom d'en-tête plus court.
user202729
la source
Vous devriez peut-être mentionner pourquoi std::sortne fait pas déborder la complexité du temps
l4m2
Également 2 octets enregistrésusing 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);}@ is
newline
2

Scala (48 octets)

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

Essayez-le en ligne

permutations renvoie un itérateur sur des permutations distinctes.

jrook
la source
2

JavaScript (Node.js) , 137 128 123 octets

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)

Essayez-le en ligne!

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)
l4m2
la source
0

APL (NARS), 156 caractères, 312 octets

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⍵[⍋⍵]}

Eux, F et G seraient 2 fonctions à utiliser ensemble ... G ordonner d'abord le tableau qu'appliquer au tableau ordonné la fonction F et écrire les permutations en observant que si l'élément est déjà trouvé, mieux vaut ne pas aller en récursivité (car tout le résultat serait déjà trouvé). Je ne sais pas si cela convient à toutes les restaurations ... 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
la source