Question 304021 in PHP Question posted in
Official manual can be found here.

PHP – Generate all possible permutations and do something

I have a set of value, say:

0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z

and I’d like to generate all possible keys of 8-digit:

00000000
00000001
00000002
...
zzzzzzzy
zzzzzzzz

but all solutions found trying to allocate an array and PHP gets out of memory.

So I’d like to do something:

 // LOOPS
 // generate 1 permutation
 // do something
 // END LOOP

Any hints?

Tags:

2

Answers


  1. 0

    If you want to generate each and every possible combination of that list, up to a certain number of digits, then you can do this by using a power relation and a modulo.

    For iteration $i, the index of the last digit is given by $i % $numValues

    For iteration $i, the index of the last-but-one digit is given by intval($i / $numValues) % $numValues

    For iteration $i, the index of the last-but-two digit is given by intval($i / ($numValues * $numValues)) % $numValues

    For iteration $i, the index of the last-but-three digit is given by intval($i / ($numValues * $numValues * $numValues)) % $numValues

    … and so on.

    Generalising, you can then set this up as a loop:

    // list of values to use
$values = [0,1,2,3,4,5,6,7,8,9,'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
$numValues = count($values);

// number of digits in each iteration
$numDigits = 8;

// total number of iterations
$numIterations = $numValues ** $numDigits - 1;

// main loop
for ($i = 0; $i <= $numIterations; $i++) {
    $str = '';
    // build string from the most significant digit (leftmost)
    // to the least significant digit (rightmost)
    for ($d = $numDigits - 1; $d >= 0; $d--) {
        $str .= $values[intval($i / ($numValues ** $d)) % $numValues];
    }
    // iteration is now in $str
    // do something with $str ...
    echo $str . PHP_EOL;
}
    Login or Signup to reply.
  2. 0

    You can use base_convert() to convert from/to decimal and use a regular numeric loop:

    echo base_convert('zzzzzzzz', 36, 10), PHP_EOL;
echo base_convert(2821109907455, 10, 36), PHP_EOL;

    2821109907455
zzzzzzzz

    Here’s a simplified example (more on that below), using printf() to add leading zeroes:

    $to = base_convert('zzz', 36, 10);
for ($i = 0; $i < $to; $i++) {
    printf("%03sn", base_convert($i, 10, 36));
}

    Demo

    The main is problem is that you’re trying to generate a huge amount of data. Your alphabet has 36 characters, what makes a total of 368 possible strings (2,821,109,907,456) if I didn’t mess maths. Your script is going to take really long to finish (high level interpreted languages are not ideal for speed), and you’re going to have problems storing the information. You’ll need to dump numbers on the go (to a file or database) and you’ll need a very large disk.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search