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...

En gros c'est simple. 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).

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 coupes on peut avoir un résultats 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 :

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

[nodjim]

Comme les 12 colonnes, pour prendre ton exemple, peuvent être découpées en 11 endroits différents (frontières entre 2 colonnes), et selon que tu vas utiliser ou non ces 11 séparations, alors le nombre de configurations possibles est de 2^11.
Pour n colonnes, 2^(n-1) configurations possibles.

[fatal_error]

salut,

on peut s'en sortir ainsi :
avec un exemple 10 à décomposer en quatre colonnes
on commence avec [10,x,x,x], les x à déterminer.
Première condition, les x sont supérieurs à 0.
donc le premier nombre doit etre au plus 7 (le plus petit x valant 1)

donc on va tester pour le premier nombre tous ceux entre 1 et 7
mettons 6.
[6,x,x,x]
on doit donc déterminer [x,x,x] qui vaut 10-6 = 4
On crèe donc une récursive :

Code: Tout sélectionner


function decomp(numToDecompose,nbCuts){
  //no more columns to decompose
  if(nbCuts==0){
    return [numToDecompose];
  }
 
  var sols = [];
  for(var i=numToDecompose - (nbCuts-1); i>0 && i*nbCuts>=numToDecompose; i--){
    var subSols = decomp(numToDecompose-i, nbCuts-1);
    //add all sub sols to current elem
    subSols.forEach(function(subSol){
      sols.push([i].concat(subSol));
    });
  }
  //return all sols
  return sols;
}


la condition i*nbCuts>=numToDecompose, signifie que on ordonne la liste, c'est à dire que si j'ai
[5,x,x,x], alors x vaut au plus 5 idem
[5,4,x,x], alors x vaut au plus 4
Ca permet d'ordonner les solutions.

Une fois qu'on a récupéré les solutions, par exemple pour 10 à décomposer en 4 colonnes :
7 1 1 1 0
6 2 1 1 0
5 3 1 1 0
5 2 2 1 0
4 4 1 1 0
4 3 2 1 0
4 2 3 1 0
4 2 2 2 0
3 5 1 1 0
3 4 2 1 0
3 3 3 1 0
3 3 2 2 0
Il faut permuter chacune de ces solutions (par exemple 1 1 1 7, 1 1 7 1, etc)
Pour ca, il faut simplement faire gaffe que si on permute le digit 1 avec le digit 2, 1 1 1 7, 1 1 1 7, alors les combi sont identiques donc c'est pas bon.
On peut générer toutes les perm d'une solution donnée, et filtrer les doublons :

Code: Tout sélectionner

function getId(perm){
  var s = 0;
  for(i = 0; i





function displayResults(arr, node){
  var s='Résultats : ';//gedit is shit for js coloring
  arr.forEach(function(el){
    for(var i=0; i';
  });
  node.html(s);
}
$(document).ready(function(){
  $('form').submit(function(e){
    e.preventDefault();
    var numToDecompose = $('#numToDecompose').val();
    var nbCuts = $('#nbCuts').val();
    try{
      var results = mainDecomp(numToDecompose, nbCuts);
      displayResults(results, $('#decomp'));
    }catch(e){
      console.log(e);
    }
  });
});



 
    Nombre à decomposer
   
    Nombre de coupes
   
   
 
 




decomp.js comprenant :

Code: Tout sélectionner

function getId(perm){
  var s = 0;
  for(i = 0; i0 && i*nbCuts>=numToDecompose; i--){
    var subSols = decomp(numToDecompose-i, nbCuts-1);
    //add all sub sols to current elem
    subSols.forEach(function(subSol){
      sols.push([i].concat(subSol));
    });
  }
  //return all sols
  return sols;
}

avec donc allPermute à implémenter