[complexe] obtenir toutes les combinaisons

#perl 
use strict; 

my %cache; 
sub f { 
 my ($n,$max) = (shift,shift); 
 $max = $n if (not defined $max); 
 $max = $n if $max>$n; 
 return "1" if ($n == 1); 
 my @res; 
 for my $i (1 .. $max) { 
  if ($i==$n) { 
   push @res, $n; 
  } else { 
   if (not defined $cache{$n-$i,$i}) { 
    $cache{$n-$i,$i} = [ &f($n-$i,$i) ]; 
   } 
   push @res, map { "$_ $i" } @{$cache{$n-$i,$i}}; 
   #push @res, map { "$i $_" } @{$cache{$n-$i,$i}};    #ordre inverse d'affichage 
  } 
 } 
 return @res; 
} 

 #Deux affichages du résultat 
my $nbbilles = 8; my @res = f($nbbilles); 
print join "\n", @res; 
print "\n----\n"; 
print join "\n", 
 map { 
  '0 'x($nbbilles - 1 - tr/ / /) #on ajoute les zéros manquants 
  .$_ 
 }   reverse @res; 

Function dénombre(n, p)
For k = 3 To n
    For i = 1 To Int(p / k)
        dénombre = dénombre + g(k - 1, p - i, i)
    Next
Next
dénombre = dénombre + 1 + Int(p / 2)
End Function

Function g(a, b, c)
If a = 2 Then
    g = Int(b / a) - c + 1
Else
    For i = c To Int(b / a)
        g = g + g(a - 1, b - i, i)
    Next
End If
End Function

debian:/home/lami20j/trash# cat combinaison.pl
#!/usr/bin/perl
use warnings;use strict;

my (%hash);
my ($a,$b,$c,$d,$e,$f,$g,$h);
for my $aa(1..8){
 for my $bb(1..8){
  for my $cc(1..8){
   for my $dd(1..8){
    for my $ee(1..8){
     for my $ff(1..8){
      for my $gg(1..8){
        for my $hh(1..8){
        if (($a,$b,$c,$d,$e,$f,$g,$h) =
         (('o' x 16) =~ /^(o{0,$aa})\1(o{0,$bb})\2
                          (o{0,$bb})\3(o{0,$dd})\4
                          (o{0,$ee})\5(o{0,$ff})\6
                          (o{0,$ee})\7(o{0,$ff})\8$/x)) {
          ($a,$b,$c,$d,$e,$f,$g,$h) = (length($a),length($b),
                                       length($c),length($d),
                                       length($e),length($f),
                                       length($g),length($h));
           my $chaine = join("",sort split //,"$a$b$c$d$e$f$g$h");
           $hash{$chaine}++;
        }
       }
      }
     }
    }
   }
  }
 }
}
$,="\n";
print sort keys %hash,"\n";
debian:/home/lami20j/trash# time perl combinaison.pl


00000008
00000017
00000026
00000035
00000044
00000116
00000125
00000134
00000224
00000233
00001115
00001124
00001133
00001223
00002222
00011114
00011123
00011222
00111113
00111122
01111112
11111111
real    10m33.554s
user    9m43.828s
sys     0m2.876s
debian:/home/lami20j/trash#

debian:/home/lami20j/trash# cat combinaison.pl
#!/usr/bin/perl
use warnings;use strict;

my (%hash);
my ($a,$b,$c,$d,$e,$f,$g,$h);
for my $aa(1..8){
for my $bb(1..7){
 for my $cc(1..6){
  for my $dd(1..5){
   for my $ee(1..4){
    for my $ff(1..3){
     for my $gg(1..2){
       for my $hh(1){
       if (($a,$b,$c,$d,$e,$f,$g,$h) =
        (('o' x 16) =~ /^(o{0,$aa})\1(o{0,$bb})\2
                         (o{0,$bb})\3(o{0,$dd})\4
                         (o{0,$ee})\5(o{0,$ff})\6
                         (o{0,$ee})\7(o{0,$ff})\8$/x)) {
         ($a,$b,$c,$d,$e,$f,$g,$h) = (length($a),length($b),
                                      length($c),length($d),
                                      length($e),length($f),
                                      length($g),length($h));
          my $chaine = join("",sort split //,"$a$b$c$d$e$f$g$h");
          #my $rrr = $chaine;
          #next if $chaine eq $rrr;
          #print $chaine,"\n";
          #$rrr="";
          $hash{$chaine}++;
       }
      }
     }
    }
   }
  }
 }
}
}
$,="\n";
print sort keys %hash,"\n";
debian:/home/lami20j/trash# time perl combinaison.pl


00000008
00000017
00000026
00000035
00000044
00000116
00000125
00000134
00000224
00000233
00001115
00001124
00001133
00001223
00002222
00011114
00011123
00011222
00111113
00111122
01111112
11111111
real    0m2.643s
user    0m2.612s
sys     0m0.012s
debian:/home/lami20j/trash#

size = 256
for(i = 0; i < size; i++)
{
	a[i] = 0
}

nbelem = 256
a[size-1] = nbelem

nbelemused = 2;
checkpoint = 0
countfreqcomb = 0
while(1) {
	countfreqcomb += 1
	if (checkpoint)
	{
		for(i = 0; i < size; i++)
			print a[i], ","			
                print "_\n"
		print "nombre de combinaison : ", countfreqcomb, "\n"
	}
	if (a[size-1] == 1)
	{
		break
	}
	
	checkpoint = 0
	
	for(i = size - 2; i >= 0; i--)	
	{
		if ((a[i]+1) < a[i+1])
		{
			a[i] += 1
			a[i+1] -= 1
			break
		} else
		{			
			if (a[i-1] > 0)
			{
				newval = a[i-1] + 2
			} else
			{
				for(j = size - nbelemused; j < size - 1; j++)
				{	
					a[size-1] += a[j]-1
					a[j] = 1
				}
				a[i-1] = 1
				a[size-1] -= 1
				nbelemused += 1
				checkpoint = 1 
				break
			}
			if ((newval-1) > a[i])
			{
				/* do nothing */
			} else
			{
				a[i+1] += (a[i]-newval)
				a[i] = newval
			}
		}
	}
}	

quit

size = 256
maxcomb = 2 ^ (size * 8)
for(i = 0; i < size; i++)
{
	a[i] = 0
}

nbelem = 256
a[size-1] = nbelem

oldent = 0
totalcomb = 0;

nbelemused = 2;
divisor = nbelem / nbelemused;
checkpoint = 0
countfreqcomb = 0
while(1) {
	countfreqcomb += 1
	if (checkpoint)
	{
		for(i = 0; i < size; i++)
			print a[i], ","	
		print "_\n"
		print "counter : ", countfreqcomb, "\n"
	}
	if (a[size-1] == 1)
	{
		break
	}
	
	checkpoint = 0
	
	for(i = size - 2; i >= 0; i--)	
	{
		if ((a[i]+1) < a[i+1])
		{
			a[i] += 1
			a[i+1] -= 1
			break
		} else
		{			
			newval = a[i-1] + 2
			if ((i == size-1) || (newval-1) > a[i])
			{
				/* do nothing */
			} else
			{
				a[i-1] += 1
				if (a[i-1] == 1)
					checkpoint = 1
				newtot = -1
				for(k = i; k < size; k++)
				{
					if ((k == size-1) || (a[k]+1 < a[k+1]))
					{
						a[k] += newtot
						break
					} else
					{
						newtot += a[k] - (newval - 1)
						a[k] = newval - 1
					}
					
				}
				break
			}
		}
	}
}