Checking Bitwise Outcome From Nested Loops Of Element Count Factorial

[help_me_with_php]

hi all,

 

here's some code for combinations of array values:

 

$words = array(1,2,3,4);
$num = count($words);
//The total number of possible combinations
$total = pow(2, $num);
//Loop through each possible combination
for ($i = 0; $i < $total; $i++) {
 //For each combination check if each bit is set
for ($j = 0; $j < $total; $j++) {
 //Is bit $j set in $i?
 if (pow(2, $j) & $i) echo $words[$j] . ' ';	
}
echo '<br />';
}

 

I understand everything about this except the fact that the array indicies can only be 0-3 for an array with 4 elements like this one. What I'm not understanding is the nested loop for $J. Isn't it obvious that the bitwise outcome will never be = 1 everytime $J rises above 3 (which is the element count) and finishes it's loop? If the outcome was ever = 1 in that scenario, $words[$j] would be undefined and couldn't echo out, right?

 

So the question is, why is this code written the way it is which renders most of the nested loop iterations for $J useless?

 

If this is supposed to be in the math section, please let me know. thanks.

Edited December 20, 2012 by help_me_with_php

[requinix]

I believe the answer is "because the code is buggy": $j actually should be counting to $num, not $total.

[help_me_with_php]

I believe the answer is "because the code is buggy": $j actually should be counting to $num, not $total.

 

yeah that's what it seems like to me. But it does make sense, from a comprehensive mathematical point of view, doesn't it? Factually, the code is actually running through all possibilities based on binary. So in essence, this person is doing what's right even though some of it's redundant and not really needed.

 

yes? that's what it looks like from here.

Edited December 20, 2012 by help_me_with_php

[requinix]

With the fix I mentioned, yes it does make sense. If $words contained more than just the numbers 1-4, like words or names, then this is basically the easiest way to enumerate all the possible combinations.

 

Actually, considering the output

1 2 1 2 3 1 3 2 3 1 2 3...

if you were to, say, hit all of those numbers on the numeric keypad lock on a particular set of cars, you would be able to get in. Except this output is horribly inefficient: there's a significantly shorter list out there.

[help_me_with_php]

I may follow you. I may not. But let me just ask you the question about what I need here, in the end.

 

I need to use that code for enumeration purposes, but outside every 'J' loop I need to store in memory the indicies of the values that were captured during the 'J' iteration and evaluate the sum of them. I'm having trouble doing this because PHP is so smart. I came from another development area (like VB legacy) where the language is much stricter because the authors *suck* (for lack of a better term here). So I'm not used to a development environment doing anything for me, really.

 

I think I have to store the associated keys in a new array during the 'J' loop, then use internals to sum the temporary array of index values. Can you help write that? Probably 2 lines of code. as said, not used to intelligent IDE's. PHP also has so many alternative methods for doing the same thing, that kind of ticks me off sometimes. in the end, the only thing that makes a difference in those cases is the memory (down to the bit) that's actually used for a method.

 

thanks!

Edited December 20, 2012 by help_me_with_php

[requinix]

I'm thinking either you actually need to store the indices

$indices = array(0, 0, 0, 0);
// then $indices[$j]++

or you just need the sum of everything

$sum = 0;
// then $sum += $j to sum the index, $sum++ to count

[help_me_with_php]

I'm thinking either you actually need to store the indices

$indices = array(0, 0, 0, 0);
// then $indices[$j]++

or you just need the sum of everything

$sum = 0;
// then $sum += $j to sum the index, $sum++ to count

 

not following. I can figure it out, but would take much longer. can you dumb it down anymore than that?

[requinix]

Whichever is the one you need, the first line is the initialization (happens before the loops) and the second line is the action you do inside that if block. Like

$words = array(1,2,3,4);
$num = count($words);
//The total number of possible combinations
$total = pow(2, $num);
/* initialization */
//Loop through each possible combination
for ($i = 0; $i < $total; $i++) {
         //For each combination check if each bit is set
for ($j = 0; $j < $total; $j++) {
         //Is bit $j set in $i?
         if (pow(2, $j) & $i) {
                  echo $words[$j] . ' ';
                  /* action */
         }
}
echo '<br />';
}