<html> <head> <title>A frivolous cycle decomposer</title> <link rel="shortcut icon" href="../favicon.ico" > </head> <body bgcolor="#ffffff" link="#a02222" vlink="#888888" alink="#cc3333"> <?php # ================================================================ # John Kerl # kerl.john.r@gmail.com # 2007-05-16 # ================================================================ # ---------------------------------------------------------------- function index_of($char, $string) { $n = strlen($string); for ($i = 0; $i < $n; $i++) if ($string[$i] == $char) return $i; return -1; } # ---------------------------------------------------------------- function make_cycle_decomposition($old_string, $new_string) { $n = strlen($old_string); $cycdec = array(); $marks = array_fill(0, $n, 0); for ($i = 0; $i < $n; $i++) { if ($marks[$i]) continue; $cycle = array(); $nexti = $i; $marks[$nexti] = 1; $num_passes = 0; while (1) { $num_passes++; if ($num_passes > $n) { echo "string_cycle_decomposition: \"" . $old_string . "\" is not a permutation of \"" . $new_string . "\"."; return array(); } array_push($cycle, $old_string[$nexti]); $nextval = $new_string[$nexti]; $nexti = index_of($nextval, $old_string); if ($nexti == -1) { echo "string_cycle_decomposition: \"" . $old_string . "\" is not a permutation of \"" . $new_string . "\"."; return array(); } if ($nexti == $i) break; $marks[$nexti] = 1; } array_push($cycdec, $cycle); } return $cycdec; } # ---------------------------------------------------------------- function print_cycle_decomposition($old_string, $new_string) { $cycdec = make_cycle_decomposition($old_string, $new_string); $n = count($cycdec); $num_cycles_printed = 0; for ($i = 0; $i < $n; $i++) { $m = count($cycdec[$i]); if ($m > 1) { $num_cycles_printed++; print "("; for ($j = 0; $j < $m; $j++) print $cycdec[$i][$j]; print ")"; } } if ($num_cycles_printed == 0) print "()"; echo "<br>"; } # ---------------------------------------------------------------- $old_string = 'SPHINX'; $usro = $_GET['o']; $usrn = $_GET['n']; $usrs = $_GET['s']; $usrd = $_GET['d']; $o = isset($usro) ? $usro : $old_string; $n = isset($usrn) ? $usrn : $old_string; $s = isset($usrs) ? $usrs : -1; $d = isset($usrd) ? $usrd : -1; $l = strlen($n); #echo "<br>o = $o\n"; #echo "<br>n = $n\n"; #echo "<br>s = $s\n"; #echo "<br>d = $d\n"; #echo "<br>"; if (($s >= 0) && ($s < $l) && ($d >= 0) && ($d < $l)) { $temp = $n[$d]; $n[$d] = $n[$s]; $n[$s] = $temp; $s = -1; $d = -1; } if ($s == -1) { echo "Click a letter in the second row."; } else { echo "Click another letter in the second row."; } echo "<br>"; echo "<b>"; for ($i = 0; $i < $l; $i++) { echo " $o[$i]"; } echo "</b>"; echo "<br>"; echo "<b>\n"; if ($s == -1) { for ($i = 0; $i < $l; $i++) { echo " <a href=\"cycdec.php?o=$o&n=$n&s=$i&d=$d\">" . $n[$i] . "</a>\n"; } } else { for ($i = 0; $i < $l; $i++) { if ($i == $s) { $color1 = " <font color=#808080>"; $color2 = " </font>"; } else { $color1 = ""; $color2 = ""; } echo " <a href=\"cycdec.php?o=$o&n=$n&s=$s&d=$i\">$color1" . $n[$i] . "$color2</a>\n"; } } echo "</b>\n"; echo "<br>"; echo "Cycle decomposition:"; print_cycle_decomposition($o, $n); #echo "<br>"; #echo "<br>o = $o\n"; #echo "<br>n = $n\n"; #echo "<br>s = $s\n"; #echo "<br>d = $d\n"; #echo "<br>"; echo "<p>\n"; echo "<a href=\"cycdec.php\">Reset</a>\n"; ?> </body> </html>