0votos

Bactracking básico continuación en PHP

por josejuan hace 5 años

Misma versión que en Haskell pero en PHP. Ésta es para @ilopez, el backtracking aquí se hace *sin* recursión, versión iterativa usando una pila.

Dado los números n y m obtener de la manera mas eficiente posible un array de todas las combinaciones de un número binario de n dígitos en donde aparezcan m veces repetidas el 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<?php 
 
function combinations($n, $m) { 
  $rs = array(); 
  $stack = array(1); 
  $bs = array(); 
  while(!empty($stack)) { 
    $c = array_pop($stack); 
    if($c > 0) { 
      if(array_push($bs, $c) == $m) { 
        array_push($rs, array_map(NULL, $bs)); 
        array_pop($bs); 
      } else { 
        array_push($stack, -$c); 
      if($c < $n) 
        array_push($stack, $c + 1); 
    } else { 
      array_pop($bs); 
      if(-$c < $n) 
        array_push($stack, 1 - $c); 
  return $rs; 
 
function bin2($n, $m) { 
    $a = array_fill(1, $n, 0); 
    foreach(combinations($n, $m) as $x) { 
        //foreach($x as $b) $a[$b] = 1; 
        //print implode(', ', $a) . "\n"; 
        //foreach($x as $b) $a[$b] = 0; 
        print implode(', ', $x) . "\n"; // <-- usar ésta para sólo anotar los bits 
 
bin2(500, 2); 
 
?> 
 
======================================= 
Por ejemplo: 
 
     
## En un Atom corriendo la versión con "class Combination" 
## (en los comentarios de la solución de @ilopez) 
 
## Generando números completos 
tmp$ time -f "%E, %M" php nmbits.php | wc -l 
0:24.54, 6904 
124750 
 
## Generando lista de bits a 1 
tmp$ time -f "%E, %M" php nmbits.php | wc -l 
0:05.11, 6868 
124750 
 
     
     
## En el mismo Atom corriendo la versión con la función "combinations" 
## pegada en esta solución: 
 
## Generando números completos 
tmp$ time -f "%E, %M" php nmbits2.php | wc -l 
0:23.93, 73160 
124750 
 
## Generando lista de bits a 1 
tmp$ time -f "%E, %M" php nmbits2.php | wc -l 
0:04.39, 73160 
124750 
1 comentario
0votos

Escrito por ilopez hace 5 años

Genial regalo del día del padre... gracias hijo mio xD.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.