Oui je pense que Jester a usé de l'emphase avec le mot carnage. Je sais qu'il n'aime pas la diffusion d'erreur, on avait discuté ensemble à l'époque de Skyrim. Il préfère les choses bien "ordered" si j'ose dire
5mins/image c'est genre brute force à essayer toutes les combinaisons de palettes de 16 parmi 64 ou 128 couls.. Tu vois le genre. D'ailleurs je me suis fait un algo marrant pour énumérer de façon non récursive tous les ensembles de n entiers dans un liste de m entiers (non consécutifs): si je te donne {1, 3, 4, 5, 7, 15, 16, 17, 21, 23, 25, 31} lister toutes les partitions en 4 sous-ensembles. Mon implémentation est toute petite, utilise les bitfields et pleins de propriétés de l’arithmétique binaire. Elle pourrait presque figurer dans le Hacker's Delight.
Je l'ajouterais dans ce message quand je repasserai chez moi. (wait & see)
[Edit: je suis rentré] ah non l'algo est recursif. Mais il est petit quand même. Le code représente les ensembles d'entiers sous forme de bitfields (dont limité aux entier de 0 à 31 sur 32bits. Au delà il faut travailler sur une arithmétique multiprécision que je ne développerai pas).
La routine suivante prend un ensemble ($set), et un sous ensemble ($x) de ($set) (donc ($x & $set) == $x) et calcule le sous ensemble suivant ($y) de $set. Le prochain sous-ensemble ($y) est le plus petit sous ensemble de ($set) tel ($x<$y):
Code : Tout sélectionner
sub next_in_set {
my($x, $set) = @_;
return ($x-$set) & $set;
}
C'est très compact et très rapide. En gros avec $set = %0011001, la routine produit %0000001 %0001000 %0001001 %0010000 %00100001 %0011000 %0011001. En fait elle compte en binaire les 8 valeurs possibles pour les 3 bits à 1 dans le set initial, mais elle saute par dessus les zones de 0 consécutifs dans le bitmask.
Ensuite la routine suivante énumère toutes les partitions de ($set) en ($k) sous-ensembles
Code : Tout sélectionner
sub all_k_partition {
my($k, $set, $i) = @_;
return () if $set==0 || $k==0 || $set<=$i;
return ($set) if $k==1;
my(@r);
while($i = &next_in_set($i, $set)) {
my($m) = $i;
for (my $j = 1;$m>>$j;$j<<=1) {$m|=$m>>$j;}
for my $j (&all_k_partition($k-1, $set^$i, $m)) {
push(@r, "$i,$j");
}
}
return @r;
}
elle prend en paramètres ($k), le nombre de partitions de l'ensemble ($set) à considérer et une graine ($i) représentant le plus grand sous-ensemble contigu non contenu dans $set (donc initialement cela vaut 0). Elle se base sur le fait que toutes les ($k) partitions de ($set) est constitué par la concaténation chaque sous-ensemble ($i) non vide de ($set) concaténé à toutes les ($k-1) partitions de ($set) privé de ($i) (d'où le ($set ^ $i)).
La boucle sur une ligne
est une façon rapide de prendre un nombre $m = %00100101011, et d'obtenir %00111111111 (i.e. tous les bits du lsb au msb sont à 1) en au plus log2(position(msb))<=5 tours.
Voilà.. fin de la parenthèse chia.te. Mais chose promise, chose due
Au fait l'ensemble des partitions de {1, 3, 4, 5, 7, 15, 16, 17, 21, 23, 25, 31} en 4 sous-ensembles contient 611501 éléments. Pour les voir tous il vous suffit d'exécuter le code ici:
http://pastebin.com/y1Cdi1vB. Les premières et dernières partitions énumérées sont:
Code : Tout sélectionner
1 {1} {3} {4} {5,7,15,16,17,21,23,25,31}
2 {1} {3} {5} {4,7,15,16,17,21,23,25,31}
3 {1} {3} {4,5} {7,15,16,17,21,23,25,31}
4 {1} {3} {7} {4,5,15,16,17,21,23,25,31}
5 {1} {3} {4,7} {5,15,16,17,21,23,25,31}
6 {1} {3} {5,7} {4,15,16,17,21,23,25,31}
7 {1} {3} {4,5,7} {15,16,17,21,23,25,31}
8 {1} {3} {15} {4,5,7,16,17,21,23,25,31}
9 {1} {3} {4,15} {5,7,16,17,21,23,25,31}
...
611496 {1,4,5,7,15,16,17,21} {23} {3,25} {31}
611497 {1,4,5,7,15,16,17,21} {3,23} {25} {31}
611498 {3,4,5,7,15,16,17,21} {23} {25} {1,31}
611499 {3,4,5,7,15,16,17,21} {23} {1,25} {31}
611500 {3,4,5,7,15,16,17,21} {1,23} {25} {31}
611501 {1,3,4,5,7,15,16,17,21} {23} {25} {31}