note 87972 added to function.shuffle

The following function, NKnext(), generates combinations sequentially. NKnext's output is a string of 0s and 1s where a "1" at position k represents the kth item being selected. For example, "1001000" represents the 0th and 3rd items being chosen from among 7. Feed NKnext() such a string to generate the next one in the sequence. Note that the sequence is a Gray Code where all adjacent element pairs (including the first and last) differ by a minimal amount (ie. a 0-1 swap), so that one could easily make it circular (Hamiltonian). <?php $n = 7; $k = 3; enumNK ($n, $k); // show all possibilities function enumNK ($n, $k) { // Iteratively generate all strings of $k "1"s and $n-$k "0"s // so that adjacent strings have exactly one 0-1 swap. // Final string is a BRR of the original (right barrel rotation) print // print the initial string $str = str_repeat("1", $k) . str_repeat("0", $n-$k); while ($str= NKnext($str)) print "<br> $str"; } function swap ($str, $pos1, $pos2) { // Return $str with characters at $pos1 and $pos2 swapped $chr = $str[$pos1]; $str[$pos1] = $str[$pos2]; $str[$pos2] = $chr; return $str; } function mod($num, $base) { // Mathematician's modulus // compare with http://php.net/fmod return ($num - $base*floor($num/$base)); } function NKnext ($str, $pos=0, $dir=1) { // Assumes there were initially $k=substr_count($str, "1") contiguous 1s // starting at ($dir==1=>leftmost; $dir==1=>rightmost) position $pos // to be barrel rotated in the direction $dir (1=>right, -1=>left) // while going through all possibilities of [$n=strlen($str), $k] // Returns the resultant next string in the iteration // by finding the position of the next swap ($pos and $pos2) NKswap ($str, $pos, $dir, substr_count ($str, "1"), strlen($str), $pos2); if ($pos==$pos2) return ""; return swap($str, $pos, $pos2); } function NKswap ($str, &$pos, $dir, $k, $n, &$pos2) { // Under the assumptions for NKnext, returns the two // positions ($pos, $pos2) that are to be swapped. // $pos2 is set to $pos if $str is final (ie. no more swaps) if (!$k || $k==$n) return $pos2 = $pos; // all 0s or all 1s $ch1 = ($str[$pos]!="0"); // Is char of interest (fixed char) a "1"? $sub = substr($str, 0, $pos) . substr($str, $pos + 1); // Rest of string // Position of next char of interest $np = mod($pos - ($dir==1) + $ch1 * $dir * ($k-1), $n-1); NKswap($sub, $np, $ch1 ? -$dir : $dir, $k---$ch1, $n-1, $pos2); if ($np==$pos2) // If substring is done return ($pos2 = mod($pos + $ch1 * $dir * ($k - !$k), $n)); if ($pos2>=$pos) ++$pos2; // Adjustment for 'char of interest' posn $pos = $np + ($np>=$pos); } // Return the "normal" swap position ?> BR = Barrel rotation BRR/BRL = Barrel rotation to the right/left by 1 The basic algorithm is recursive, with a fixed "1" position identified ($pos=0, below), all sub-possibilities are iterated, then it is replaced with a 0, and then all those sub-possibilities are iterated. [5, 3] example with leftmost 1 fixed: 11100 -> 10101 -> 10110 -> 11010 -> 10011 -> 11001 [5, 3] continued with leftmost char swap: 11001 -> 01101 [5, 3] continued with leftmost 0 fixed: 01101 -> 00111 -> 01011 -> 01110 When $dir is 1 in the above functions, it represents a net BRR, and $pos represents the starting position of the leftmost 1. When $dir is -1 in the above functions, it represents a net BRL, and $pos represents the starting position of the rightmost 1. $pos is essentially used to determine when all the swaps are done. For example, in rotating 1110 (with $dir=1 and $pos=0) we go through the following: 1101 (and not 0111!), 1011, 0111 Happy New Year, Csaba Gabor from Vienna ---- Server IP: 192.35.244.50 Probable Submitter: 80.108.23.194 ---- Manual Page -- http://www.php.net/manual/en/function.shuffle.php Edit -- https://master.php.net/note/edit/87972 Del: integrated -- https://master.php.net/note/delete/87972/integrated Del: useless -- https://master.php.net/note/delete/87972/useless Del: bad code -- https://master.php.net/note/delete/87972/bad+code Del: spam -- https://master.php.net/note/delete/87972/spam Del: non-english -- https://master.php.net/note/delete/87972/non-english Del: in docs -- https://master.php.net/note/delete/87972/in+docs Del: other reasons-- https://master.php.net/note/delete/87972 Reject -- https://master.php.net/note/reject/87972 Search -- https://master.php.net/manage/user-notes.php