Keluarkan semua permutasi yang berbeda dari suatu vektor

9

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 sehingga kode terpendek dalam byte menang.

Stewie Griffin
sumber
2
Apakah ada implementasi referensi yang memenuhi persyaratan kompleksitas ini?
Steven H.
1
Seharusnya tidak terlalu sulit untuk menghasilkan algoritma yang memenuhi persyaratan (mungkin tidak terlalu golf). Saya bukan seorang programmer atau ahli matematika, saya hanyalah seorang penulis tantangan yang sederhana. Saya akan meninggalkan barang-barang yang sulit untuk kalian :)
Stewie Griffin
6
Saya pikir mengingat karakteristik pembatasan ini akan menjadi lebih baik sebagai kode tercepat, karena golf kode biasanya untuk penggunaan yang cerdas dari fitur bawaan dan bahasa.
Uriel
3
"Seharusnya tidak terlalu sulit" ≠ "itu mungkin"
Fatalize
1
Apakah fungsi pembangkit dapat diterima atau haruskah kita menambahkan boilerplate ke solusi seperti itu untuk mencetak / menghasilkan?
Jonathan Allan

Jawaban:

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

Menggunakan 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, 1Akan disebutkan 2, 1, 2, 1; 1, 2, 2, 1dll.

Neil
sumber
5

Python 3 dengan sympy , (50?) 81 byte

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

Cobalah online!

50 byte jika fungsi generator dapat diterima:

import sympy
sympy.iterables.multiset_permutations

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:

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

(catatan: ini menggunakan golf Python 2 tab dan spasi bolak-balik untuk indentasi)

Jonathan Allan
sumber
Tidak perlu menulis "pada saat penulisan fungsi ini di baris 983" , Anda dapat permalink ke komit terbaru: github.com/sympy/sympy/blob/… .
orlp
@ Atau apakah sudah ada permalink di sana?
Erik the Outgolfer
@EriktheOutgolfer Saya menautkan ke komit tertentu, bukan 'versi terbaru', sehingga itu berarti tautan saya tidak akan kedaluwarsa oleh perubahan di masa mendatang.
orlp
2

C ++ (gcc) , 203 byte

Rupanya C ++ memiliki ini sebagai fungsi bawaan ...

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

Cobalah online!

Kode tidak dikunci: TIO link.

Ini menggunakan O(n)memori (dijamin oleh std::vector) dan runtime optimal.

Beberapa optimasi dalam kode:

  • Gunakan importsebagai ganti include(ekstensi G ++ tidak digunakan)
  • Gunakan 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 stdyang dikenal sebagai ide yang buruk .
  • Gunakan puts("")sebagai ganti cout<<'\n'untuk menulis baris baru. Ini normal untuk program C, tetapi terasa aneh bagi saya. Jadi saya pikir ini harus disebutkan.
  • mainnilai 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):

  • Masukkan ukuran array sebelum memasukkan elemen. Ini akan memungkinkan array ukuran dinamis, secara keseluruhan menghemat 30 byte .
  • Tidak memisahkan output dengan pemisah. Jadi hasilnya akan seperti 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 1untuk 1 2 1 3. Ini memungkinkan menghemat lebih banyak 9 byte.
  • Sementara di C diizinkan untuk menghilangkan header, saya tidak tahu apakah ada cara yang lebih pendek untuk menggunakan fungsi-fungsi tanpa #importheader di C ++, atau nama header yang lebih pendek.
pengguna202729
sumber
Mungkin Anda harus menyebutkan mengapa std::sortkompleksitas waktu tidak meluap
l4m2
Juga 2 byte disimpanusing 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);} @ adalah baris baru
@adalah
2

Scala (48 byte)

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

Cobalah online

permutasi mengembalikan iterator melalui permutasi yang berbeda.

jrook
sumber
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)

Cobalah online!

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
sumber
0

APL (NARS), 156 karakter, 312 byte

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

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:

  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
sumber