Problema combinatorio

[paolossp-votailprof]

Supponendo di avere k oggetti differenti m1, m2, ..., mk è possibile elencarli nel modo (esempio fatto con k = 6)

1. m1
2. m2
3. m3
4. m4
5. m5
6. m6
7. m1 m2
8. m1 m3
9. m1 m4
10. m1 m5
11. m1 m6
12. m2 m1
13. m2 m3
14. m2 m4
15. m2 m5
16. m2 m6
17. m3 m1
18. m3 m2
19. m3 m4
20. m3 m5
21. m3 m6

e sperare che esista un algoritmo veloce (che non richieda di calcolare sempre da 1) per avere una trasformazione da numero naturale a sequenza di oggetti e/o viceversa?

Quello che mi interessa è sapere se c'è un algoritmo immediato che dato il 16, per esempio, fornisca i coefficienti 2 e 6 e/o viceversa.

Se si giungesse alla conclusione che un tale algoritmo non è possibile, è invece possibile ottenerlo per la sequenza:

1. m1
2. m2
3. m3
4. m4
5. m5
6. m6
7. m1 m1
8. m1 m2
9. m1 m3
10. m1 m4
11. m1 m5
12. m1 m6
13. m2 m1
14. m2 m2
15. m2 m3
16. m2 m4
17. m2 m5
18. m2 m6
19. m3 m1
20. m3 m2

Ovviamente non conta tanto l'ordine delle sequenze quanto il fatto che le sequenze con un numero più piccolo di mosse vengano sempre prima di quelle con un numero più grande.

Notare che nel primo caso la particolarità sta nel fatto che non ripeto mai due volte di seguito lo stesso oggetto, a differenza del secondo esempio.

[paolossp-votailprof]

Salve a tutti,

torno su questo forum circa dopo un mese dal giorno in cui ho posto il quesito. Purtroppo subito dopo il primo messaggio, poiché mi fu risposto che l'argomento era stato trattato ma non si trattava dell'argomento che richiedevo, non sono più tornato sul forum e mi sono messo a studiare da solo un metodo.
La mia paura iniziale, che mi porto dietro da un paio d'anni, era che una soluzione semplice al problema non esistesse e che fosse un problema indecidibile. In realtà mentre leggevo il libro 'L'ultimo teorema di Fermat' un ragionamento che ho fatto mi ha rassicurato sulla quasi certa esistenza di una soluzione e un'impegno assiduo ha fatto emergere la soluzione, in una sola notte . NdP. Da quel giorno ho interrotto la lettura del libro a metà..
In questi giorni sto pubblicando un articolo sul mio sito che tratta del Cubo di Rubik, sono arrivato a spiegare in un modo spero più comprensibile il problema che ho posto qui e una parziale soluzione. Nei prossimi giorni inserirò nell'articolo l'algoritmo completo, sia in forma ricorsiva che in forma iterativa. Purtoppo una rappresentazione matematica come quelle che sono state date in molte risposte (che leggerò appena ho un po' di tempo) non sono in grado di darla: il mio 'mestiere' è l'informatico più che il matematico.

Vi ringrazio comunque per le risposte che avete dato. Vi lascio il link del mio articolo, sperando che a qualcuno di voi leggendolo vengano in mente anche altre idee, oppure critiche al mio lavoro.

http://www.rubiksillusions.com/ita/solu ... parziale/1

A presto..