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