Division d'un tableau...

[llopht]

Salut tous,

Je préviens je ne suis pas mathématicien et très loin de là . Je suppose que ce que je cherche à un nom, un algo. Si quelqu'un pouvait m'aider ça va probablement être très très simple pour vous... Imaginons un tableau de 12 colonnes (mais ça pourrait être une autre valeur paire).

Je voudrais utiliser ce tableau soit dans son ensemble (les 12 colonnes), le diviser en deux (6 colonnes + 6 colonnes = 12), en trois (4,4,4 = 12), en quatre (3,3,3,3 = 12) en cinq (2,3,2,3,2 = 12) ou en 6 (2,2,2,2,2,2 = 12) et ainsi de suite pour des tableaux plus large.

Maintenant ce que je veux c'est pour chaque "division" obtenir tous les possibilités. Exemple, si je veux le tableau diviser en deux... j'ai donc 6 colonnes + 6 regroupées comme je l'ai indiqué plus haut. Sauf qu'il existe plusieurs variantes :

122222222222 (1 colonne puis 11 colonnes regroupées = 12 colonnes au total)
112222222222 (2,10)
111222222222 (3,9)
111122222222 (4,8)
111112222222 (5,7)
111111222222 (6,6 l'exemple que j'avais donné)
111111122222 (7,5)
111111112222 (8,4)
111111111222 (9,3)
111111111122 (10,2)
111111111112 (11,1)

Si ça reste "simple" pour la version 2 colonnes en raison du décalage, pour la version 3 ça se complique car le nombre de possibilités augmentent... Par exemple avec 5 division on peut avoir un résultat du genre 112223333445 (2,3,4,2,1 = 12).

Donc en gros ce que je voudrais c'est définir la taille du tableau 6, 8, 10, 12 éléments, etc. Et ensuite pour un nombre de divisions donné exemple 3, obtenir un tableau (array) des variantes possibles en hexa (ce qui limiterait à 14 le nombre d'éléments maxi mais simplifierait le stockage et la lecture du résultat) ou dans des tableaux imbriqués (soit en décimal soit en hexa). Genre (en javascript langage qui me faudrait au final) :

var a = variantes(12, 2);
a vaudrait ['1b', '2a', '39', '48', '57', '66', '75', '84', '93', 'a2', 'b1'] en hexa ou autre possibilité
a vaudrait [[1,11],[2,10],[3,9 et ainsi de suite...

var a = variantes(12, 6);
a vaudrait ['222222'] ou
a vraudrait [[2],[2],[2],[2],[2],[2]]

Des idées ?

Merci

Jérôme
-----

[invite4492c379]

Hello,

quel est le but ? Car tu vas te retrouver face à une explosion exponentielle des possibilités et au final te retrouver avec un algo non utilisable au-delà de petits tableaux (en plus si tu l'implémentes en javascript ça deviendra très vite inutilisable) ...

[Tryss]

Il y a exactement façons de découper un tableau à n colonnes en k morceaux.

J'utiliserai un algorithme classique pour générer toutes les combinaisons à k-1 éléments de l'ensemble des entiers de 1 à n, ce qui donne à chaque fois un tableau :

C = {a(1),...,a(k-1) }

Puis, pour obtenir ce que tu souhaites, il suffit de faire une boucle : b(1) = a(1), b(i) = a(i)-a(i-1) et il faut ajouter un dernier b(k) = n-a(k-1)

Ceci dit, je suis curieux, quel est l'objectif?

[invite4492c379]

Oui, pour un tableau de taille n tu te retrouves avec une complexité spatiale en 2^n-1...
En même temps si le taille reste limitée il serait préférable de précalculer les partitions.

[A voir en vidéo sur Futura]

[llopht]

Dans la réalité je vais avoir seulement 2 largeurs de tableaux 12 et 16 colonnes. Le but est simple, je pouvoir faire un petit éditeur qui permettrait à un utilisateur de créer une mise en page à partir d'un format qui se décompose en 12 ou 16 colonnes. Le but de l'éditeur serait simple, imaginons que l'on créé un modèle de page internet avec 4 lignes. La première utilise les 16 colonnes, la seconde 4x4, la troisième ligne 4 puis 12 colonnes et enfin la dernière 2 x 8 colonnes. L'éditeur permettrait à l'utilisateur d'ajouter chaque ligne, de définir le nombre de divisions et ensuite définir la variante pour l'affichage...

Les variantes seraient accessibles au travers d'un slider qui ferait varier l'affichage de la ligne. Rien n'empêche cependant de créer en plus une des formats types...

Tu comprends ? C'est une application pratique des maths mais je sèche J'ai vu certain utiliser des tableaux du genre :

         '1': ['c'],
        '2': ['2a', '39', '48', '57', '66', '75', '84', '93', 'a2'],
        '3': ['228', '237', '246', '255', '264', '273', '282', '327', '336', '345', '354', '363', '372', '426', '435', '444', '453', '462', '525', '534', '543', '552', '624', '633', '642', '723', '732', '822'],
        '4': ['2226', '2235', '2244', '2253', '2262', '2325', '2334', '2343', '2352', '2424', '2433', '2442', '2523', '2532', '2622', '3225', '3234', '3243', '3252', '3324', '3333', '3342', '3423', '3432', '3522', '4224', '4233', '4242', '4323', '4332', '4422', '5223', '5232', '5322', '6222'],
        '5': ['22224', '22233', '22242', '22323', '22332', '22422', '23223', '23232', '23322', '24222', '32223', '32232', '32322', '33222', '42222'],
        '6': ['222222'] 
  

Je trouve ça ridicule, il manque des possibilités et ça reste uniquement pour le format 12 colonnes... Les maths et un bon algo et on arriverait au même résultat...

Jérôme

[invite4492c379]

Pour 16 colonnes tu auras 2¹⁵=32768 possibilités ... tu veux toutes les afficher dans une liste déroulante ?!?!?

[llopht]

Oulà je suis déjà perdu. Tu as le petit manuel pour le gars qui sait seulement faire 1+1=2 ? C'est loin loin loin pour moi ce genre de choses

[llopht]

Sauf erreur plutôt 256 car pour 16 colonnes et 64 pour 12. Tu as en fait au max n/2 divisions possibles.

Plutôt qu'utiliser une liste déroulante, un petit slider qui à chaque cran fait changer l'affichage... et pourquoi pas une liste des variantes les plus utilisées...

[invite4492c379]

Pour n=4 tu as

colonnes	partitions
1	4
2	13 22 31
3	112 121 211
4	1111

Pour n=16 tu auras 16 sous-listes dont la plus grande va contenir 6435 éléments si je ne me trompe pas ...

[invite4492c379]

Re-,

j'ai généré les listes pour le cas n=12 pour que tu vois à quoi cela peut ressembler.

Partition12.txt

Bon courage (peut-être faut-il repenser l'interface ?)