Enumeration Permutations - Minor Notice

[Guest Anonymous]

Okay, it's not often I have to shout for help... but why oh why does this code generate warning? And more to the point ... how the heck do I get rid of it...?

Notice: Undefined offset: -1 in /usr/home/nyna/www/test-harness.lan/htdocs/test.php on line 8

The code itself is designed to print all possible permutations of a given array.

 

<?php

error_reporting(E_ALL);

function next_permutation( $p, $size )
{
// slide down the array looking for where we're smaller than the next guy
for ($i = $size - 1; $p[$i] >= $p[$i + 1]; --$i) // warning in this line
{ }

// if this doesn't occur, we've finished our permutations
// the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
if ($i == -1)
	return false;

// slide down the array looking for a bigger number than what we found before
for ($j = $size; $p[$j] <= $p[$i]; --$j)
{ }

// swap them
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

// now reverse the elements in between by swapping the ends
for (++$i, $j = $size; $i < $j; ++$i, --$j)
{
	$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
}

return $p;
}

$set  = split(" ", "a b c"); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j    = 0;

do
{ 
foreach ($perm as $i)
{
	$perms[$j][] = $set[$i];
}
}
while ($perm = next_permutation($perm, $size) and ++$j);

foreach ($perms as $p)
{
print join(' ', $p) . "
";
}

>

[Haunted Dawg]

Re: Enumeration Permutations - Minor Notice

Well have you ever tried adding 1 line more to the code?

Say for example:

$size2 -= 1;

then use:

 

<?
for ($i = $size2; $p[$i] >= $p[$i + 1]; --$i) // warning in this line
{ }
?>

 

I dont know what your code is trying to do but i sure dont know what its trying to do itself. Please tell me if that works or not.

[Guest Anonymous]

Re: Enumeration Permutations - Minor Notice

Nope, changing the initial size parameter either causes more notices or reduces the number of possible permutations generated dramatically.

The correct output should be (no notices, warnings or errors):

a b c

a c b

b a c

b c a

c a b

c b a

[Haunted Dawg]

Re: Enumeration Permutations - Minor Notice

Ill work on it on a test file.

[Haunted Dawg]

Re: Enumeration Permutations - Minor Notice

For some reason this code works:

 

<?php
error_reporting(E_ALL);
function next_permutation( $p, $size )
{
// slide down the array looking for where we're smaller than the next guy
for ($i = $size - 1; $p[$i] >= $p[$i + 1]; -$i) // warning in this line
{ }
// if this doesn't occur, we've finished our permutations
// the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
if ($i == -1)
	return false;
// slide down the array looking for a bigger number than what we found before
for ($j = $size; $p[$j] <= $p[$i]; --$j)
{ }
// swap them
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
// now reverse the elements in between by swapping the ends
for (++$i, $j = $size; $i < $j; ++$i, --$j)
{
	$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
}

return $p;
}
$set  = split(" ", "a b c"); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j    = 0;
do
{ 
foreach ($perm as $i)
{
	$perms[$j][] = $set[$i];
}
}
while ($perm = next_permutation($perm, $size) and ++$j);
foreach ($perms as $p)
{
print join(' ', $p) . "
";
}
?>

 

But only thing now says:

Fatal error: Maximum execution time of 30 seconds exceeded in /home/finalkil/public_html/test.php on line 7

So maybe try and set a maximum its supposed to show.

[Guest Anonymous]

Re: Enumeration Permutations - Minor Notice

Using set_time_limit( ... ) is *not* an option here, this code has to run at lightning speed.

I have a working solution with a different algorithm however... Won't post it yet until I've fully optimized it.

[Floydian]

Re: Enumeration Permutations - Minor Notice

I've noticed that a for loop always evaluates the first part of the for loop, one last time before stopping.

Suppose you have a for loop like this:

$array = array (1,2,3,4);

for ($i = 0, $i <= 3; $i++) {

echo $i . '

';

}

echo $i . '

';

It would go through each part of the array. However, the last $i would echo out as 4 not 3 as might be expected.

0

1

2

3

4

That is the output of that script.

So, I would think that your for loop is evaluating that array one more time that it should. I'm not exactly sure how to fix it, but I am 100% sure this behavior of PHP for loops is the cause.

[Guest Anonymous]

Re: Enumeration Permutations - Minor Notice

The result of (in your case) post incrementing - yes...

Well it was a possibly bad idea which did in fact prove to be rather risky. The number of permutations I was playing with was waaaay to large to be a viable option for my original problem.

Basically, using permutations allowed to brute-force attack a particular problem.

Doing a little rethinking and judicious use of Knuth, I succeeded in speeding the process up dramatically, however I'm now using a shed load of memory as bifuricated trees tend to grow rather rapidly.

Still, it works, (on my server anyway - with memory limits set rather high), although it has taught me that in this particular instance PHP is *not* the language to use.

And what ... you may well ask ... is "it"? Simple - a Sudoku generator and solver written totally in PHP. Unlike a lot of JavaScript (and certain Java sources), this one guarantees (mathematically) only one solution.

I hope to produce a little mod from this, however instead of generating the puzzles on the fly, I will be supplying "packs" of puzzles.

Thanks for your help guys...

Demo link (short lifetime) http://nyna.co.uk/sudoku.phtml

[Floydian]

Re: Enumeration Permutations - Minor Notice

Yeah, I noticed you are decrementing the count on that for loop. I think my theory still stands that the for loop expression valuates one time past the length of the array thus causing the notice, even though the code inside the for loop wouldn't execute, hence the offset of -1 ;)

 

Edit:

Oh, and sudoku sounds like fun. I almost added one to me project but alas it was coded by a german guy and the text was all in german. Add to that the fact that I know nothing of sudoku and I wouldn't know if that thing was working right or not lol. And the last problem was that since it was javascript based, it really wouldn't do for building it into the game.

[Haunted Dawg]

Re: Enumeration Permutations - Minor Notice

Nyna i know im not the best at coding but i came up with a little function that randomly selects a b c and displays them. Yes every single one is different but you might some times get the same all 3 letters its basicly like gambling lol. Anyways:

 

<?
error_reporting(E_ALL);
$array = array("a","b","c");
function rand_one($max)
{
  global $array;
  $rand = rand(0,$max);
  $val = $array[$rand];
  return $val;
}
function rand_two($max)
{
  global $array;
  $rand = rand(0,$max);
  $val = $array[$rand];
  return $val;
}
function rand_three($max)
{
  global $array;
  $rand = rand(0,$max);
  $val = $array[$rand];
  return $val;
}
function loop_through()
{
  global $array;
  $count = rand(0,count($array)-1);
  $p = 0;
  while($p < 100)
   {
     $p++;
     echo rand_one($count).'  '.rand_two($count).'  '.rand_three($count).'
';
   }
}
loop_through();
?>

 

That gave me:

 

a a b
b a a
b b a
b a a
a b b
a b b
a a a
a a b
b b a
b b a
a a a
b b b
b a b
a a b
b a b
a b a
b b b
b a b
a b b
b b a
b b b
a b b
b b a
a b a
a a b
b a a
a a a
b a b
b a a
a a a
b b a
b a b
a b b
b a b
b a b
b a a
b a b
a a b
b b a
a a a
a a a
b a a
a a a
b b a
a b b
a a a
b a a
a b b
b a a
b b b
a a a
b b a
b a b
a a b
a b b
a b b
a b a
b a b
a a a
b a b
b a a
b b a
a b a
b b a
a a b
b a b
b b b
b a b
b a b
b a b
b b a
b a a
b b a
a a b
a b a
a b b
a b a
b b b
b a a
b b a
a b b
b b a
b b b
a b a
a a b
a b b
a b a
a b b
a a b
a b b
b a b
b a a
b a b
b a b
a a a
a a b
b a b
b b a
b a b
a a b

 

Hope that helps in a way.

[Guest Anonymous]

Re: Enumeration Permutations - Minor Notice

Three problems there ... (That's why this is in the Pro section)

1. Duplicates

Brute-Forcing by random generation is classically viable, but technically useless. With 3 entities (a, b, c) we have 3! solutions or 6, 4 entities is 24, 5 is 120 ... by the time you hit 10, that's 3,628,800 which is starting to get to the stage of being prohibitive to store the "seen that one" in memory.

2. Speed

Redoing an operation - one which has already been tested would just be a waste of time. In this instance, I needed to mathematically prove that there was only 1 solution to the problems I generate (unlike javascript generators and some java ones). Careless thinking led me to initially assume that testing permutations would be feasible.

3. Flexibility

Iterating through permutations is by is very nature an "Iterative" process. having to construct separate functions for each element is madness. (Think of an odometer - emulating that - where there are no duplicates is fairly simple).

Nice try... but better luck next time.

[Haunted Dawg]

Re: Enumeration Permutations - Minor Notice

Well it was worth a try i never quite understood what this is for so anyway's it was worth a try xD

[Will]

Re: Enumeration Permutations - Minor Notice

The problem is in the second part of the for loop:

$p[$i] >= $p[$i + 1];

It is due to the array key ($i) not existing on the first run.

It does work even with the error; so is there a problem.

To fix; you can check to see if it exists:

<?php

error_reporting(E_ALL);

function chk($p,$ii)
{
if (array_key_exists($ii,$p)) {
return $p[$ii];
} else {
return 0;
}
}


function next_permutation( $p, $size )
{
// slide down the array looking for where we're smaller than the next guy
for ($i = $size - 1;
chk($p,$i) >= chk($p,$i+1);// warning in this line
 --$i)
{ }

// if this doesn't occur, we've finished our permutations
// the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
if ($i == -1)
	return false;

// slide down the array looking for a bigger number than what we found before
for ($j = $size; $p[$j] <= $p[$i]; --$j)
{ }

// swap them
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

// now reverse the elements in between by swapping the ends
for (++$i, $j = $size; $i < $j; ++$i, --$j)
{
	$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
}

return $p;
}

$set  = split(" ", "a b c"); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j    = 0;

do
{ 
foreach ($perm as $i)
{
	$perms[$j][] = $set[$i];
}
}
while ($perm = next_permutation($perm, $size) and ++$j);

foreach ($perms as $p)
{
print join(' ', $p) . "
";
}

?>

http://www.thecrimelife.net/cenu.php

[Haunted Dawg]

Re: Enumeration Permutations - Minor Notice

Will are you sure your script is right? It is just giving me the same letters the hole time.

[Will]

Re: Enumeration Permutations - Minor Notice

It's meant to; it's following a logical order to work out the permutation.

Anyway the problem was with the error message; which I fixed.

[Will]

Re: Enumeration Permutations - Minor Notice

Was it right?