-
Notifications
You must be signed in to change notification settings - Fork 2
/
28-note-libere-20.lsp
8093 lines (6471 loc) · 260 KB
/
28-note-libere-20.lsp
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
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
================
NOTE LIBERE 20
================
444 222222
4444 222222222
44444 222 222
444444 222 222
444 444 222 222
444 444 2222
444 444 2222
444 444 2222
4444444444444 222
4444444444444 222
444 222 222
444 222222222222
444 222222222222
-------
For Fun
-------
π to √-1: get real
√-1 to π: be rational
π to √-1: π/π
√-1 to π: (√-1)²
------------
Segment Tree
------------
Traduzione parziale da:
https://e-maxx.ru/algo/segment_tree
created by e-maxx aka maxdiver aka Ivanov Maxim
https://cp-algorithms.com/data_structures/segment_tree.html
Segment tree
------------
Un "segment tree" (albero dei segmenti) è una struttura dati che memorizza informazioni sugli intervalli di un array in un albero.
A Segment Tree is a data structure that stores information about array intervals as a tree.
Questo consente di rispondere in modo efficiente alle query sugli intervalli di un array, pur essendo sufficientemente flessibile da consentire una rapida modifica dell'array.
È possibile trovare la somma di elementi consecutivi dell'array a[l..r] o trovare l'elemento minimo in tale intervallo in tempo O(log(n)).
Oltre a rispondere a queste domande, il segment tree consente di modificare l'array sostituendo un elemento o anche modificando gli elementi di un intero sottosegmento (ad esempio assegnando tutti gli elementi a[l..r] a qualsiasi valore o aggiungendo un valore a tutti gli elementi del sottosegmento).
In generale, un segment tree è una struttura dati molto flessibile e con essa è possibile risolvere un grande numero di problemi.
Inoltre, è anche possibile applicare operazioni più complesse e rispondere a domande più complesse.
(vedi Versioni avanzate dei segment tree).
In particolare il segment tree può essere facilmente generalizzato a dimensioni maggiori.
Ad esempio, con un segment tree bidimensionale è possibile rispondere a domande di somma o minimo su un sottorettangolo di una determinata matrice in tempo O(log^2(n))
Una proprietà importante dei segment tree è che richiedono solo una quantità lineare di memoria.
Il Segment Tree standard richiede 4n vertici per lavorare su un array di dimensione n.
Forma più semplice di un Segment Tree
-------------------------------------
Per iniziare in modo semplice, consideriamo la forma più semplice di un segment-tree.
Vogliamo rispondere alle domande di somma di sottointervalli in modo efficiente.
La definizione formale del nostro compito è:
Dato un array a[0..(n-1)] il segment tree deve essere in grado di trovare la somma degli elementi tra gli indici "l" e "r" (ovvero calcolando la somma Sum[i=l..r](a[i])), e anche gestire la modifica dei valori degli elementi nell' array (cioè eseguire assegnamenti nella forma a[i] = x).
Il segment-tree dovrebbe essere in grado di elaborare entrambe le query in tempo O(log n).
Questo è un miglioramento rispetto agli approcci più semplici.
Un'implementazione ingenua dell'array, che utilizza un semplice array, può aggiornare gli elementi in O(1), ma richiede O(n) per calcolare ciascuna query di somma.
E le somme dei prefissi precalcolati possono calcolare le query di somma in O(1), ma l'aggiornamento di un elemento dell'array richiede
O(n) per cambiare le somme dei prefissi.
Struttura del segment tree
--------------------------
Possiamo adottare un approccio divide et impera quando si tratta di segmenti di array.
Calcoliamo e memorizziamo la somma degli elementi dell'intero array, ovvero la somma del segmento a[0..(n-1)].
Quindi dividiamo l'array in due metà a[0..(n/2-1)] e a[n/2..(n-1)], calcoliamo la somma di ciascuna metà e le memorizziamo.
Ognuna di queste due metà viene a sua volta divisa a metà e così via finché tutti i segmenti raggiungono la dimensione 1.
Possiamo vedere questi segmenti come se formassero un albero binario: la radice di questo albero è il segmento a[0..(n-1)], e ogni vertice (eccetto i vertici foglia ha esattamente due vertici figli.
Questo è il motivo per cui la struttura dati è chiamata "Segment Tree", anche se nella maggior parte delle implementazioni l'albero non è costruito esplicitamente (vedi Implementazione).
Ecco una rappresentazione visiva di tale segment-tree sull'array a = [1, 3, -2, 8, -7]:
+---------+
| a[0..4] |
| sum = 3 |
+---------+
/ \
/ \
/ \
+---------+ +---------+
| a[0..2] | | a[3..4] |
| sum = 2 | | sum = 1 |
+---------+ +---------+
/ \ / \
/ \ / \
+---------+ +---------+ +---------+ +---------+
| a[0..1] | | a[2..2] | | a[3..3] | | a[4..4] |
| sum = 4 | | sum =-2 | | sum = 8 | | sum = 7 |
+---------+ +---------+ +---------+ +---------+
/ \
/ \
+---------+ +---------+
| a[0..0] | | a[1..1] |
| sum = 1 | | sum = 3 |
+---------+ +---------+
Da questa breve descrizione della struttura dati, possiamo già concludere che un Segment Tree richiede solo un numero lineare di vertici.
Il primo livello dell'albero contiene un singolo nodo (la radice), il secondo livello conterrà due vertici, nel terzo conterrà quattro vertici, finché il numero di vertici non raggiunge n.
Pertanto il numero di vertici nel caso peggiore può essere stimato dalla somma:
1 + 2 + 4 + ... + 2^(ceil(log2(n)) < 2^(ceil(log2(n))+1) < 4n.
Vale la pena notare che ogni volta che n non è una potenza di due, non tutti i livelli del segment-tree saranno completamente riempiti.
Possiamo vedere quel comportamento nella figura sopra.
Per ora possiamo dimenticare questo fatto, ma diventerà importante più avanti durante il processo di implementazione.
L'altezza del segment-tree è O(log(n)), perché scendendo dalla radice alle foglie la dimensione dei segmenti diminuisce circa della metà.
Costruzione
-----------
Prima di costruire il segment tree, dobbiamo decidere:
1) il valore che viene memorizzato in ciascun nodo del segment tree.
Ad esempio, in un segment-tree di somma, un nodo memorizzerebbe la somma degli elementi nel suo intervallo [l, r].
2) l'operazione di unione che unisce due fratelli (sibling) in un segment-tree.
Ad esempio, in un segment-tree somma, i due nodi che corrispondono agli intervalli a[l1..r1] e a[l2..r2] verrebbe unito in un nodo corrispondente all'intervallo a[l1..r2] sommando i valori dei due nodi.
Si noti che un vertice è un "vertice foglia" (leaf), se il segmento corrispondente copre solo un valore nell'array originale.
È presente al livello più basso di un segment-tree.
Il suo valore sarebbe pari all'elemento (corrispondente) a[i].
Ora, per la costruzione del segment-tree, iniziamo dal livello inferiore (i vertici delle foglie) e assegniamo loro i rispettivi valori.
Sulla base di questi valori possiamo calcolare i valori del livello precedente, utilizzando la funzione di unione (merge).
E sulla base di questi possiamo calcolare i valori del precedente e ripetere la procedura fino a raggiungere il vertice della radice.
È conveniente descrivere questa operazione ricorsivamente nell'altra direzione, cioè dal vertice della radice ai vertici della foglia.
La procedura di costruzione, se chiamata su un vertice non foglia, fa quanto segue:
1. costruisce ricorsivamente i valori dei due vertici figli
2. unisce i valori calcolati di questi figli.
Iniziamo la costruzione dal vertice della radice e quindi siamo in grado di calcolare l'intero segment-tree.
La complessità temporale di questa costruzione è O(n), presupponendo che l'operazione di unione sia a tempo costante (l'operazione di unione viene chiamata n volte, che è uguale al numero di nodi interni nel segment-tree).
Domande (query) di somma
------------------------
Per ora risponderemo alle domande di somma.
Riceviamo in input due numeri interi l e r e dobbiamo calcolare la somma del segmento a[l...r] in tempo O(log(n)).
Per fare ciò, attraverseremo il segment tree e utilizzeremo le somme precalcolate dei segmenti.
Supponiamo di trovarci attualmente nel vertice che copre il segmento a[tl...tr].
Ci sono tre casi possibili.
Il caso più semplice è quando il segmento a[l...r] è uguale al segmento corrispondente del vertice corrente (cioè a[l...r] = a[tl...tr]), allora abbiamo finito e può restituire la somma precalcolata memorizzata nel vertice.
In alternativa, il segmento della query può ricadere completamente nel dominio del figlio sinistro o destro.
Ricordiamo che il figlio di sinistra copre il segmento a[tl...tm] e il vertice di destra copre il segmento a[tm+1...tr] con tm = (tl + tr)/2.
In questo caso possiamo semplicemente andare al vertice figlio, il cui segmento corrispondente copre il segmento della query, ed eseguire l'algoritmo qui descritto con quel vertice.
E poi c'è l'ultimo caso, il segmento di query si interseca con entrambi i figli.
In questo caso non abbiamo altra scelta che effettuare due chiamate ricorsive, una per ogni figlio.
Per prima cosa andiamo al figlio di sinistra, calcoliamo una risposta parziale per questo vertice (cioè la somma dei valori dell'intersezione tra il segmento della query e il segmento del figlio di sinistra), poi andiamo al figlio di destra, calcoliamo la risposta parziale utilizzando quel vertice, quindi combina le risposte sommandole.
In altre parole, poiché il figlio di sinistra rappresenta il segmento a[tl...tm] e il figlio di destra il segmento a[tm+1...tr], calcoliamo la query di somma a[l...tm] utilizzando il figlio sinistro e la query di somma a[tm+1...r] utilizzando il figlio corretto.
Quindi l'elaborazione di una query di somma è una funzione che richiama se stessa ricorsivamente una volta con il figlio sinistro o destro (senza modificare i limiti della query), o due volte, una volta per il figlio sinistro e una volta per quello destro (dividendo la query in due sottoquery ).
E la ricorsione termina ogni volta che i confini del segmento di query corrente coincidono con i confini del segmento del vertice corrente. In tal caso la risposta sarà il valore precalcolato della somma di questo segmento, che viene memorizzato nell'albero.
In altre parole, il calcolo della query è un attraversamento dell'albero, che si estende attraverso tutti i rami necessari dell'albero e utilizza i valori di somma precalcolati dei segmenti nell'albero.
Ovviamente inizieremo l'attraversamento dal vertice radice del Segment Tree.
La procedura è illustrata nell'immagine seguente.
Anche in questo caso viene utilizzato l'array a = [1, 3, -2, 8, -7] e qui vogliamo calcolare la somma sum{i=2..4}a[i].
Verranno visitati i vertici viola e utilizzeremo i valori precalcolati dei vertici verdi.
Questo ci dà il risultato -2 + 1 = -1.
Viola
+---------+
| a[0..4] |
| sum = 3 |
+---------+
/ \
/ \
Viola / \ Verde
+---------+ +---------+
| a[0..2] | | a[3..4] |
| sum = 2 | | sum = 1 |
+---------+ +---------+
/ \ / \
/ \Verde / \
+---------+ +---------+ +---------+ +---------+
| a[0..1] | | a[2..2] | | a[3..3] | | a[4..4] |
| sum = 4 | | sum =-2 | | sum = 8 | | sum = 7 |
+---------+ +---------+ +---------+ +---------+
/ \
/ \
+---------+ +---------+
| a[0..0] | | a[1..1] |
| sum = 1 | | sum = 3 |
+---------+ +---------+
Perché la complessità di questo algoritmo è O(log(n))?
Per mostrare questa complessità guardiamo ogni livello dell'albero.
Si scopre che per ogni livello visitiamo solo non più di quattro vertici.
E poiché l'altezza dell'albero è O(log(n)), otteniamo il tempo di esecuzione desiderato.
Possiamo dimostrare che questa proposizione (al massimo quattro vertici per livello) è vera per induzione.
Al primo livello visitiamo solo un vertice, il vertice radice, quindi qui visitiamo meno di quattro vertici.
Consideriamo ora un livello arbitrario.
Per ipotesi di induzione visitiamo al massimo quattro vertici.
Se visitiamo solo al massimo due vertici, il livello successivo avrà al massimo quattro vertici.
Questo è banale, perché ogni vertice può causare al massimo due chiamate ricorsive.
Supponiamo quindi di visitare tre o quattro vertici nel livello attuale.
Da questi vertici, analizzeremo più attentamente i vertici al centro.
Poiché la query di somma richiede la somma di un sotto-array continuo, sappiamo che i segmenti corrispondenti ai vertici visitati al centro saranno completamente coperti dal segmento della query di somma.
Pertanto questi vertici non effettueranno alcuna chiamata ricorsiva.
Quindi solo il vertice più a sinistra e quello più a destra avranno il potenziale per effettuare chiamate ricorsive.
E queste creeranno solo al massimo quattro chiamate ricorsive, quindi anche il livello successivo soddisferà l'asserzione.
Possiamo dire che un ramo si avvicina al limite sinistro della query e il secondo ramo si avvicina a quello destro.
Pertanto visitiamo al massimo 4*log(n) vertici in totale, e ciò equivale a un tempo di esecuzione di O(log(n)).
In conclusione la query funziona dividendo il segmento di input in più sottosegmenti per i quali tutte le somme sono già precalcolate e memorizzate nell'albero. E se interrompiamo il partizionamento ogni volta che il segmento della query coincide con il segmento del vertice, allora abbiamo bisogno solo di O(log(n)) tali segmenti, il che produce l'efficacia del segment tree.
Domande (query) di aggiornamento
--------------------------------
Ora vogliamo modificare un elemento specifico nell'array, diciamo che vogliamo eseguire l'assegnazione a[i] = x.
E dobbiamo ricostruire il segment tree, in modo che corrisponda al nuovo array modificato.
Questa query è più semplice della query di somma.
Ogni livello di un albero di segmenti costituisce una partizione dell'array.
Pertanto un elemento a[i] contribuisce solo ad un segmento per ciascun livello.
Pertanto solo i vertici O(log(n)) devono essere aggiornati.
È facile vedere che la richiesta di aggiornamento può essere implementata utilizzando una funzione ricorsiva.
Alla funzione viene passato il vertice corrente dell'albero e si richiama ricorsivamente con uno dei due vertici figli (quello che contiene a[i] nel suo segmento), quindi ricalcola il suo valore di somma, in modo simile a come viene fatto nel metodo build (ovvero come somma dei suoi due figli).
Anche in questo caso ecco una visualizzazione che utilizza lo stesso array.
Qui eseguiamo l'aggiornamento a[2] = 3.
I vertici verdi sono i vertici che visitiamo e aggiorniamo.
Verde
+---------+
| a[0..4] |
| sum = 8 |
+---------+
/ \
/ \
Verde / \
+---------+ +---------+
| a[0..2] | | a[3..4] |
| sum = 7 | | sum = 1 |
+---------+ +---------+
/ \ / \
/ \Verde / \
+---------+ +---------+ +---------+ +---------+
| a[0..1] | | a[2..2] | | a[3..3] | | a[4..4] |
| sum = 4 | | sum = 3 | | sum = 8 | | sum = 7 |
+---------+ +---------+ +---------+ +---------+
/ \
/ \
+---------+ +---------+
| a[0..0] | | a[1..1] |
| sum = 1 | | sum = 3 |
+---------+ +---------+
Implementazione
---------------
La considerazione principale è come memorizzare il segment tree.
Naturalmente possiamo definire una struttura 'Vertex' e creare oggetti che memorizzano i confini del segmento, la sua somma e inoltre anche i puntatori ai suoi vertici figli.
Tuttavia, ciò richiede la memorizzazione di molte informazioni ridondanti sotto forma di puntatori.
Utilizzeremo un semplice trucco per renderlo molto più efficiente utilizzando una struttura dati implicita: memorizzare solo le somme in un array. (Un metodo simile viene utilizzato per gli heap binari).
La somma del vertice radice all'indice 1, la somma dei suoi due vertici figli agli indici 2 e 3, la somma dei figli di questi due vertici agli indici da 4 a 7 e così via.
Con l'indicizzazione 1, convenientemente il figlio sinistro di un vertice all'indice i viene memorizzato nell'indice 2i e quello destro nell'indice 2i + 1.
In modo equivalente, il genitore di un vertice all'indice i viene memorizzato in i/2 (divisione intera ).
Questo semplifica molto l'implementazione.
Non abbiamo bisogno di memorizzare la struttura dell'albero in memoria. È definito implicitamente.
Abbiamo bisogno solo di un array che contenga la somma di tutti i segmenti.
Come notato prima, dobbiamo memorizzare al massimo 4n vertici. Potrebbe essere inferiore, ma per comodità assegniamo sempre un array di dimensione 4n. Ci saranno alcuni elementi nell'array sum che non corrisponderanno ad alcun vertice nell'albero reale, ma ciò non complica l'implementazione.
Quindi, memorizziamo il segment tree semplicemente come un array t[] con una dimensione pari a quattro volte la dimensione dell'input n:
int n, t[4*MAXN];
La procedura per costruire il segment tree da un dato array a[] è simile alla seguente: è una funzione ricorsiva con i parametri a[] (l'array di input), v (l'indice del vertice corrente) e i confini tl e tr del segmento corrente.
Nel programma principale questa funzione verrà chiamata con i parametri del vertice radice: v = 1, tl = 0 e tr = n - 1.
void build(int a[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = t[v*2] + t[v*2+1];
}
}
Inoltre la funzione per rispondere alle domande di somma è anche una funzione ricorsiva, che riceve come parametri informazioni sul vertice/segmento corrente (cioè l'indice v e i confini tl e tr) e anche le informazioni sui confini della query, l e r.
Per semplificare il codice, questa funzione esegue sempre due chiamate ricorsive, anche se ne è necessaria una sola: in tal caso la chiamata ricorsiva superflua avrà l > r, e questo può essere facilmente colto utilizzando un controllo aggiuntivo all'inizio della funzione.
int sum(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return sum(v*2, tl, tm, l, min(r, tm))
+ sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
Infine la query di aggiornamento.
La funzione riceverà anche informazioni sul vertice/segmento corrente e inoltre anche il parametro della query di aggiornamento (ovvero la posizione dell'elemento e il suo nuovo valore).
void update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
t[v] = t[v*2] + t[v*2+1];
}
}
Implementazione Memory efficient
--------------------------------
La maggior parte delle persone utilizza l'implementazione della sezione precedente.
Se guardi l'array t puoi vedere che segue la numerazione dei nodi dell'albero nell'ordine di un attraversamento BFS (attraversamento dell'ordine dei livelli).
Utilizzando questo attraversamento i figli del vertice v sono rispettivamente 2v e 2v+1.
Tuttavia, se n non è una potenza di due, questo metodo salterà alcuni indici e lascerà alcune parti dell'array t inutilizzate.
Il consumo di memoria è limitato a 4n, anche se un segment tree di un array di n elementi richiede solo 2n - 1 vertici.
Tuttavia può essere ridotto.
Rinumeriamo i vertici dell'albero nell'ordine di un attraversamento del tour di Eulero (attraversamento in preordine) e scriviamo tutti questi vertici uno accanto all'altro.
Consideriamo un vertice con indice v, e sia responsabile del segmento [l, r], e poniamo mid = (l + r)/2.
È ovvio che il figlio di sinistra avrà indice v+1.
Il figlio di sinistra è responsabile del segmento [l, mid], ad es. in totale ci saranno 2 * (mid - l + 1) - 1 vertici nel sottoalbero del figlio di sinistra.
Possiamo quindi calcolare l'indice del figlio destro di v.
L'indice sarà v + 2 * (mid - l + 1). Con questa numerazione otteniamo una riduzione della memoria necessaria a 2n.
L'articolo continua con versioni avanzate della struttura segment tree "Advanced versions of Segment Trees" e analizza i seguenti argomenti:
- Finding the maximum
- Finding the maximum and the number of times it appears
- Compute the greatest common divisor / least common multiple
- Counting the number of zeros, searching for the k-th zero
- Searching for an array prefix with a given amount
- Searching for the first element greater than a given amount
- Finding subsegments with the maximal sum
- Find the smallest number greater or equal to a specified number. No modification queries.
- Find the smallest number greater or equal to a specified number. With modification queries.
- Find the smallest number greater or equal to a specified number. Acceleration with "fractional cascading".
- Range updates - Addition on segments - Assignment on segments - Adding on segments, querying for maximum
- Generalization to higher dimensions
- Compression of 2D Segment Tree
- Preserving the history of its values (Persistent Segment Tree)
- Finding the k-th smallest number in a range
- Dynamic segment tree (implicit segment tree or sparse segment tree)
----------------------------------------------------------------
Soluzione del ponte di Wheatstone sbilanciato con il metodo mesh
----------------------------------------------------------------
R2 R5
+-----*****-----+-----*****-----+
| | |
| * |
Va ----+ R3 * +---- Vb
| * |
| R1 | R4 |
+-----*****-----+-----*****-----+
Vab = 24 Volt
R1 = 150 Ohm
R2 = 50 Ohm
R3 = 100 Ohm
R4 = 300 Ohm
R5 = 250 Ohm
Loop 1:
I1 = R1-R3-R2 (antiorario)
Loop 2:
I2 = R4-R3-R5 (orario)
Loop 3:
I3 = R4-R1 (antiorario)
Kirchhoff's Voltage Law (Loop 1):
R2I1 + R3(I1+I2) + R1(I1−I3) = 0 Volt
50I1 + 100(I1+I2) + 150(I1−I3) = 0 Volt
1) 300I1 + 100I2 − 150I3 = 0 Volt
Kirchhoff's Voltage Law (Loop 2):
R5I2 + R3(I2+I1) + R4(I2+I3) = 0 Volt
250I2 + 100(I2+I1) + 300(I2+I3) = 0 Volt
2) 100I1 + 650I2 + 300I3 = 0 Volt
Kirchhoff's Voltage Law (Loop 3):
24 + R1(I3−I1) + R4(I3+I2) = 0 Volt
24 + 150(I3−I1) + 300(I3+I2) = 0 Volt
3) −150I1 + 300I2 + 450I3 = -24 Volt
Solve the 3x3 system:
300I1 + 100I2 − 150I3 = 0
100I1 + 650I2 + 300I3 = 0
−150I1 + 300I2 + 450I3 = -24
(setq a '((300 100 -150)
(100 650 300)
(-150 300 450)))
(setq b '(0 0 -24))
Function "sislin-g" is "yo.lsp" library:
(sislin-g a b)
;-> (-0.09379310344827588 0.07724137931034483 -0.1360919540229885)
Calculate branch resistor current values:
IR1 = I3 − I1 = 136.092 − 93.793 = 42.299 mA
IR2 = I1 = 93.793 mA
IR3 = I1 − I2 = 93.793 − 77.241 = 16.552 mA
IR4 = I3 − I2 = 136.092 − 77.241 = 58.851 mA
IR5 = I2 = 77.241 mA
Calculate voltage drops:
VR1 = IR1*R1 = (0.042299)*(150) = 6.3448 Volt
VR2 = IR2*R5 = (0.093793)*(50) = 4.6897 Volt
VR3 = IR3*R5 = (0.016552)*(100) = 1.6552 Volt
VR4 = IR4*R5 = (0.058851)*(300) = 17.6553 Volt
VR5 = IR5*R5 = (0.077241)*(250) = 19.3103 Volt
----------------------------------------
Somma quadrata dei quadrati dei divisori
----------------------------------------
Determinare la sequenza dei numeri la cui somma dei quadrati dei divisori è anch'essa un numero quadrato.
Sequenza OEIS A046655:
Numbers whose sum of the squares of divisors is also a square number
1, 42, 246, 287, 728, 1434, 1673, 1880, 4264, 6237, 9799, 9855, 18330,
21352, 21385, 24856, 36531, 39990, 46655, 57270, 66815, 92664, 125255,
156570, 182665, 208182, 212949, 242879, 273265, 380511, 391345, 411558,
539560, 627215, 693160, 730145, 741096, ...
Esempio:
Numero = 42
Divisori: 1 2 3 6 7 14 21 42
Quadrati dei divisori: 1, 4, 9, 36, 49, 196, 441, 1764
Somma dei Quadrati dei divisori = 2500
Poichè 50x50 = 2500 si tratta di un quadrato perfetto, quindi il numero 42 fa parte della sequenza.
(define (divisors num)
"Generate all the divisors of an integer number"
(local (f out)
(cond ((= num 1) '(1))
(true
(setq f (factor-group num))
(setq out '())
(divisors-aux 0 1)
(sort out)))))
; auxiliary function
(define (divisors-aux cur-index cur-divisor)
(cond ((= cur-index (length f))
(push cur-divisor out -1)
)
(true
(for (i 0 (f cur-index 1))
(divisors-aux (+ cur-index 1) cur-divisor)
(setq cur-divisor (* cur-divisor (f cur-index 0)))
))))
Funzione che fattorizza un numero intero:
(define (factor-group num)
(if (= num 1) '((1 1))
(letn (fattori (factor num)
unici (unique fattori))
(transpose (list unici (count unici fattori))))))
Funzione che verifica se un numero intero è un quadrato perfetto:
(define (square? n) (let (v (+ (sqrt n 0.5))) (= n (* v v))))
Funzione che verifica se un numero appartiene alla sequenza:
(define (seq? num)
(square? (apply + (map (fn(x) (* x x)) (divisors num)))))
(time (println (filter seq? (sequence 1 1e6))))
;-> (1 42 246 287 728 1434 1673 1880 4264 6237 9799 9855 18330
;-> 21352 21385 24856 36531 39990 46655 57270 66815 92664 125255
;-> 156570 182665 208182 212949 242879 273265 380511 391345 411558
;-> 539560 627215 693160 730145 741096 773224 814463 931722 992680)
;-> 19144.706
----------------------------------
I tre numeri interi sono distinti?
----------------------------------
Dati tre numeri a, b e c determinare quanti sono quelli distinti.
Esempi:
numeri: 1 2 3 (3 numeri distinti: 1, 2 e 3)
numeri: 1 2 2 (2 numeri distinti: 1 e 2)
numeri: 2 2 2 (1 numero distinto: 2)
(define (check a b c)
(cond ((!= a b c) 3) ; numeri tutti diversi
((= a b c) 1) ; numeri tutti uguali
(true 2))) ; numeri in cui uno di loro è duplicato
(check 1 2 3)
;-> 3
(check 1 2 2)
;-> 2
(check 2 2 2)
;-> 1
Se i numeri vengono dati come elementi di una lista possiamo usare "apply":
(apply check '(1 2 3))
;-> 3
(apply check '(1 2 2))
;-> 2
(apply check '(2 2 2))
;-> 1
--------------------
Un problema del 1953
--------------------
Il 20 giugno 1953 George Gamow inviò il seguente telegramma a Stanislaw Ulam:
"Caro Stan, un problema per te: usando 20 lettere diverse scrivi una lunga parola contenente qualche migliaio di lettere.
Quanto dovrebbe essere lunga questa parola per avere buone probabilità di trovarci dentro tutte le parole di 10 lettere?
Pregoti telegrafarmi risposta."
Stan rispose immediatamente da Los Alamos:
"Pregoti telegrafarmi se consentito saltare lettere in parola lunga per formare parole 10 lettere. Se si, risposta abbastanza breve.
Se solo lettere contigue consentite risposta molto maggiore dieci alla ventesima potenza e Carson spedirà questa parola a carico destinatario.
Con affetto, Stan."
Quante parole di 10 lettere posso generare con un alfabeto di 20 simboli?
Se ogni simbolo può essere utilizzato più volte in una parola e l'ordine dei simboli è significativo, allora abbiamo 20^10 possibilità.
Questo è perché abbiamo 20 opzioni per il primo simbolo, 20 per il secondo, e così via, fino al decimo simbolo.
Quindi, il numero totale di parole possibili sarà 10^20.
Se, invece, l'ordine dei simboli non è significativo e possiamo utilizzare ciascun simbolo solo una volta, allora stiamo parlando di una combinazione.
In questo caso, il numero di combinazioni è data da:
(n−r)!r!
--------
n!
dove, n è il numero totale di simboli (20).
r è la lunghezza della parola (10)
Quindi abbiamo:
(20-10)!10!
-----------
20!
Questo rappresenta il numero di parole uniche di 10 simboli che possiamo generare usando 20 simboli diversi senza ripetizione e con l'ordine non significativo.
La probabilità di trovare una specifica parola di 10 lettere in una sequenza di k lettere, dove ogni lettera può essere una delle 20 diverse lettere con probabilità uniforme, è data da:
P = 1 - (1 - 1/20^10)^k
Nell'equazione, la probabilità P rappresenta la probabilità di trovare almeno una volta la parola di 10 lettere in una sequenza di k lettere.
Possiamo fissare un valore desiderato per P (ad esempio, 0.95 per una probabilità del 95%) e risolvere l'equazione per k:
0.95 = 1 - (1 - 1/20^10)^k
0.95 + (10239999999999/10240000000000)^k = 1
(10239999999999/10240000000000)^k = 0.05
k ≈ 3.12305×10^13
Quindi con una parola lunga 3.12305×10^13 abbiamo il 95% di probabilità di trovare tutte le parole di 10 lettere che si possono creare con 20 simboli.
-----------------------
Software version number
-----------------------
Quando viene pubblicato un software, gli viene assegnato un numero di versione.
Per aggiornare il software all'ultima versione, gli utenti devono capire quale versione dovrebbe essere più recente.
Consideriamo solo i numeri di versione che sono alcune cifre intervallate da punti.
In particolare:
- Un numero di versione è una stringa non vuota che può contenere solo cifre (0..9) e punti (.).
- I punti non sarebbero il primo/ultimo carattere di un numero di versione.
- Ci devono essere alcune cifre tra i punti. Non possono apparire due punti consecutivi.
Esempi:
2 1 18.04 18.4
1.0.0 1 7.010 7.8
1.0 1.0.0 1.0.0.1.0 1.00.00.2
1.2.42 1.2.41 00.00.01 0.0.0.1
1.1.56789 1.2.0 0.0.1 0.1
1.10 1.2 42.0 4.2.0
1.20 1.150 999.999 999.999.1
2018.08.1 2018.08
Questo problema può essere risolto usando il natural-sort.
(define (natural-sort l)
(let (natural-key (lambda (s) (filter true?
(flat (transpose (list
(parse s "[0-9]+" 0)
(map int (find-all "[0-9]+" s))))))))
(sort l (fn (x y) (< (natural-key x)
(natural-key y))))
))
(setq lst '("2" "1" "1.0.0" "1" "1.0" "1.0.0" "1.2.42" "1.2.41" "1.1.56789"
"1.2.0" "1.10" "1.2" "1.20" "1.150" "18.04" "18.4" "7.010" "7.8"
"1.0.0.1.0" "1.00.00.2" "00.00.01" "0.0.0.1" "0.0.1" "0.1" "42.0"
"4.2.0" "999.999" "999.999.1" "2018.08.1" "2018.08"))
(natural-sort lst)
;-> ("0.0.0.1" "0.0.1" "00.00.01" "0.1" "1" "1" "1.0" "1.0.0" "1.0.0"
;-> "1.0.0.1.0" "1.00.00.2" "1.1.56789" "1.2" "1.2.0" "1.2.41" "1.2.42"
;-> "1.10" "1.20" "1.150" "2" "4.2.0" "7.8" "7.010" "18.4" "18.04" "42.0"
;-> "999.999" "999.999.1" "2018.08" "2018.08.1")
------------------
Primi in un numero
------------------
Dato un numero trovare al suo interno i "sottonumeri" primi.
Un "sottonumero" primo è una sequenza consecutiva di cifre (prese dal numero dato), che rappresenta un numero primo.
(define (prime? num)
"Check if a number is prime"
(if (< num 2) nil
(= 1 (length (factor num)))))
(define (find-primi num)
(local (out len str val)
(setq out '())
(setq len (length num))
(setq str (string num))
(for (i 0 (- len 1))
(for (j 1 (- len i))
;(println i { } j)
(setq val (int (slice str i j) 0 10))
;(print val { })
(if (prime? val) (push val out -1))
)
)
out))
Proviamo:
(find-primi 1234567890)
;-> (2 23 23456789 3 4567 5 67 7 89)
(find-primi 1234567891011121314)
;-> (1234567891 12345678910111 2 23 23456789 3 4567 4567891 45678910111
;-> 45678910111213 5 56789101 67 67891 678910111213 7 789101 78910111213
;-> 89 89101 9101112131 101 10111 11 1112131 11 1112131 11 11213 1213 2
;-> 2131 13 131 3 31)
-----------------------------------------------------------
Selezionare/rimuovere/inserire elementi da una lista ogni k
-----------------------------------------------------------
Vediamo tre funzioni per selezionare, rimuovere e inserire elementi di una lista ogni k elementi.
Funzione che rimuove gli elementi ogni k:
(define (remove-k lst k)
(let (out '())
(dolist (el lst) (if (!= (% (+ $idx 1) k) 0) (push el out -1)))
out))
Proviamo:
(setq a (sequence 1 50))
(remove-k a 3)
;-> (1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28
;-> 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50)
(remove-k a 1)
;-> ()
Funzione che seleziona gli elementi ogni k:
(define (select-k lst k)
(let (out '())
(dolist (el lst) (if (= (% (+ $idx 1) k) 0) (push el out -1)))
out))
Proviamo:
(select-k a 3)
;-> (3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48)
(select-k a 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)
Verifichiamo la correttezza delle due funzioni:
(= (sort (extend (select-k a 3) (remove-k a 3))) (sort a))
;-> true
(setq b '(46 45 94 74 10 59 38 73 60 57 36 15 22
42 80 51 98 75 34 16 65 49 6 69 50))
(= (sort (extend (select-k b 7) (remove-k b 7))) (sort b))
;-> true
Per finire la funzione che inserisce un elemento in una lista ogni k:
(define (insert-k val lst k)
"Inserts element into a list every k"
(let (out '())
(dolist (el lst)
(if (zero? (% (+ $idx 1) k))
(extend out (list el val))
(push el out -1)))
out))
Proviamo:
(insert-k ', '(1 2 3 4 5 6 7 8 9) 1)
;-> (1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ,)
(insert-k ', '(1 2 3 4 5 6 7 8 9) 2)
;-> (1 2 , 3 4 , 5 6 , 7 8 , 9)
(insert-k ', '(1 2 3 4 5 6 7 8 9) 3)
;-> (1 2 3 , 4 5 6 , 7 8 9 ,)
(insert-k ', '(1 2 3 4 5 6 7 8 9) 4)
;-> (1 2 3 4 , 5 6 7 8 , 9)
---------------------
La regola di Naismith
---------------------
La regola di Naismith aiuta nella pianificazione di una spedizione a piedi o di una escursione calcolando quanto tempo ci vorrà per percorrere il percorso previsto, compreso l'eventuale tempo extra impiegato quando si cammina in salita.
Questa regola pratica fu ideata da William W. Naismith, un alpinista scozzese, nel 1892.
Una versione moderna può essere formulata come segue:
"Calcolare un'ora ogni 5 km in piano, più un'ora aggiuntiva per ogni 600 m di salita"
Questa regola di base presuppone che gli escursionisti abbiano una forma fisica ragionevole, su un terreno tipico e in condizioni normali.
Non tiene conto dei ritardi, come le pause prolungate per riposarsi o visitare la città, o degli ostacoli alla navigazione.
velocità-piana = 5000 / 60 = 83.333333 metri/min
velocità-salità = 600 / 60 = 10 metri/min
(define (naismith dist-piana dist-salita)
(local (v1 v2 t1 t2)
(setq v1 (div 5000 60))
(setq v2 (div 600 60))
(setq t1 (div dist-piana v1))
(setq t2 (div dist-salita v2))
(add t1 t2))
Proviamo:
(naismith 2000 1000)
;-> 124 ;minuti
(naismith 1000 2000)
;-> 212 ;minuti
-------------------
Prodotto più comune
-------------------
Dato un elenco di numeri interi positivi con più di un elemento, restituisce il prodotto più comune di due elementi nell'array.
Ad esempio, l'MCM della lista (2 3 4 5 6) è 12, poiché una tabella di prodotti è:
2 3 4 5 6
+---------------
2 | - 6 8 10 12
3 | - - 12 15 18
4 | - - - 20 24
5 | - - - - 30
6 | - - - - -
Poiché 12 appare più volte (due volte come 2*6 e 3*4).
Non vengono considerati i prodotti di un elemento per se stesso.
Tuttavia, gli elementi identici vengono comunque moltiplicati, quindi la tabella per (2 3 3) avrà il seguente aspetto:
2 3 3
+--------
2 | - 6 6
3 | - - 9
3 | - - -
Con l'MCM pari a 6.
(setq lst '(2 3 4 5 6))
(define (mcm lst)
(local (out freq uniq)
(setq out '())
(setq freq '())
(for (i 0 (- (length lst) 2))
(for (j (+ i 1) (- (length lst) 1))
;(println (lst i) { } (lst j))
(push (* (lst i) (lst j)) freq -1)
)
)
(setq uniq (unique freq))
(setq freq (sort (map (fn(x y) (list x y)) (count uniq freq) uniq) >))
;(println freq)
(setq massimo (freq 0 0))
;(println massimo)
(dolist (el freq)
;(println el)
(if (= (el 0) massimo) (push el out -1))
)
out))
Facciamo alcune prove:
(mcm (sequence 1 10))
;-> ((2 40) (2 30) (2 24) (2 20) (2 18) (2 12) (2 10) (2 8) (2 6))
(mcm '(2 3 4 5 6))
;-> ((2 12))
(mcm '(7 2))
;-> ((1 14))
(mcm '(2 3 3))
;-> ((2 6))
(mcm '(3 3 3))
;-> ((3 9))
(mcm '(1 1 1 1 2 2))
;-> ((8 2))
(mcm '(6 200 10 120))
;-> ((2 1200))
(mcm '(2 3 4 5 6 7 8 8))
;-> ((3 24))
(mcm '(5 2 9 10 3 4 4 4 7))
;-> ((4 20))
(mcm '(9 7 10 9 7 8 5 10 1))
;-> ((4 90) (4 70) (4 63))
----------------------------------------------------
A Million Random Digits with 100,000 Normal Deviates
----------------------------------------------------
"A Million Random Digits with 100,000 Normal Deviates" è un libro di numeri casuali pubblicato dalla RAND Corporation nel 1955.
Il libro, composto da un elenco di numeri casuali, è stato un importante strumento nel settore della statistica.
È stato creato a partire dal 1947 usando la simulazione elettronica di una roulette connessa ad un computer i cui risultati, adeguatamente filtrati, sono stati inseriti nel libro. Questo fu molto importante in quanto non esisteva un elenco di numeri casuali di tali dimensioni.
Oggi siamo abituati ad utilizzare il generatore di numeri pseudo-casuali codificato in una routine, ma all'epoca questo non era possibile.
Nel 1949, durante la progettazione del computer Manchester Mark I, Alan Turing progettò un generatore di numeri casuali che sfruttava una sorgente di rumore elettronico veramente casuale.
John Von Neumann disse che "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin."
In italiano, "chiunque prenda in considerazione i metodi aritmetici per generare numeri casuali commette, ovviamente, peccato."
"Random numbers should not be generated with a method chosen at random."
"I numeri casuali non dovrebbero essere generati con un metodo scelto a caso."
Donald E. Knuth
Esistono due categorie principali di generatori di numeri casuali:
A) Generatori di numeri Pseudo Random (Generatori lineari congruenti, Mersenne Twister, altri)
B) Generatori di numeri random veri (Generatori fisici di rumore, caos, altri)
I numeri, che sono di pubblico dominio, sono riportati nel file "rand-million.txt" nella cartella "data".
Ogni riga contiene una cifra da 0 a 9.
Vediamo per curiosità la frequenza delle cifre contenute nel file:
(silent (setq nums (parse (read-file "rand-million.txt"))))
(setq digit (map string (sequence 0 9)))
;-> ("0" "1" "2" "3" "4" "5" "6" "7" "8" "9")
(count digit nums)
;-> (99803 100050 100640 100311 100094 100214 99942 99559 100107 99280)
Vedi anche "Generatore di numeri casuali" su "Note libere 1".
-----------------------------
Partizioni prime di un numero
-----------------------------
La partizione prima si riferisce al processo di divisione di un dato numero in un insieme di numeri primi.
Ad esempio, se il numero è 6, può essere partizionato come 2 + 2 + 2 o 3 + 3 (nota che 1 non viene considerato primo).
L'obiettivo di generare tutte le partizioni prime di un dato numero è elencare tutti i modi possibili per dividere il numero in numeri primi .
Per generare tutte le partizioni prime di un numero, possiamo utilizzare un approccio ricorsivo.
Per prima cosa identifichiamo i numeri primi che possono essere utilizzati per la partizione.
Quindi prendiamo ciascun numero primo e partizioniamo ricorsivamente il numero rimanente finché non raggiungiamo una partizione in cui tutti i numeri sono primi.
Sequenza OEIS A000607: Number of partitions of n into prime parts
1, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 30,
35, 40, 46, 52, 60, 67, 77, 87, 98, 111, 124, 140, 157, 175, 197, 219,
244, 272, 302, 336, 372, 413, 456, 504, 557, 614, 677, 744, 819, 899, 987,
1083, 1186, 1298, 1420, 1552, 1695, 1850, 2018, 2198, 2394, 2605, 2833,
3079, 3344, ...
(define (prime? num)
"Check if a number is prime"
(if (< num 2) nil
(= 1 (length (factor num)))))
Funzione che genera una lista con valori true negli indici primi:
(define (primes num) (map prime? (sequence 0 num)))
Funzione che genera le partizioni in modo ricorsivo:
(define (partition value idx sum num)
(cond ((= sum num)
(push (slice result 0 idx) out -1)
(if show (println (slice result 0 idx))))
((or (>= idx (/ num 2)) (> sum num)) nil) ; condizione di stop
(true
(for (i value num)
(if (prime i)
(begin
(setf (result idx) i)
; trova il prossimo elemento
(partition i (+ idx 1) (+ sum i) num)
))))))
Funzione che genera tutte le partizioni di un numero con tutti numeri primi:
(define (prime-part num show)
(local (out result prime)
(setq out '())
(setq result (array (/ num 2) '(0)))
(setq prime (primes num))
(partition 2 0 0 num)
out))
Facciamo alcune prove:
(prime-part 7)
;-> ((2 2 3) (2 5) (7))
(prime-part 9)
;-> ((2 2 2 3) (2 2 5) (2 7) (3 3 3))
(prime-part 17)
;-> ((2 2 2 2 2 2 2 3) (2 2 2 2 2 2 5) (2 2 2 2 2 7) (2 2 2 2 3 3 3)
;-> (2 2 2 3 3 5) (2 2 2 11) (2 2 3 3 7) (2 2 3 5 5) (2 2 13) (2 3 3 3 3 3)
;-> (2 3 5 7) (2 5 5 5) (3 3 3 3 5) (3 3 11) (3 7 7) (5 5 7) (17))
(prime-part 21 true)
;-> (2 2 2 2 2 2 2 2 2 3)
;-> (2 2 2 2 2 2 2 2 5)
;-> (2 2 2 2 2 2 2 7)
;-> (2 2 2 2 2 2 3 3 3)
;-> (2 2 2 2 2 3 3 5)