How does this recursive code to find all permutations of a string work?

Question

I am doing Project Euler problems. I am currently working on the circular primes problem

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Although checking if something is primes was easy for me, I could not figure out how to get all the permutations of the numbers. After a good bit of searching for tips on an algorithm to do that, I came across a website which gave code for that in Java, which I adapted to PHP below. However, before proceeding with the problem, I would really like to understand what exactly the different bits of the code are doing, especially in the for loop. What I understand of it so far is that in the for loop, it is starting with an empty prefix and then looping through the string and adding a single element from the string to the prefix, until there is only one element left in the original string, at which point, it echoes it out. Am I understanding this correctly? If not, what am I missing?

<?php
    getallcombos("","1234");
    function getallcombos($prefix,$string){
        if(strlen($string)==1){
            echo $prefix.$string."<br>";
        }
        $array=str_split($string);
        for($i=0;$i<strlen($string);$i++){
            $newstr=substr($string,0,$i).substr($string,$i+1);
            getallcombos($prefix.$array[$i],$newstr);
        }                       
    }       
?>

Check my answer for this [here](http://stackoverflow.com/questions/19226649/how-does-the-algorithm-for-recursively-printing-permutations-of-an-array-work-ex) — Alma Do, Oct 15 '13 at 14:19
Or mine, here: http://stackoverflow.com/questions/19226649/how-does-the-algorithm-for-recursively-printing-permutations-of-an-array-work-ex/19227988#19227988 :) (It has a jsFiddle.) — jgroenen, Oct 15 '13 at 14:19
Do you want *rotations* of the digits? Or *permutations* of the digits? That is, 197 has three rotations: 197, 719, 971. But there are 6 permutations: 179, 197, 719, 791, 917, 971. — Jim Mischel, Oct 15 '13 at 17:04

jgroenen · Accepted Answer · 2013-10-15T14:36:30.083

The problem does not ask for permutations, but rotations. This is different. For all rotations, you can do a loop:

var number = "2031";
var rotations = [];
for (i = 0; i < number.length; ++i) {
    number = number.substring(1)
           + number[0];
    rotations.push(number);
}
console.log(rotations);

http://jsfiddle.net/T6Mur/

UPDATE

Specially for you:

function allRotArePrime(number) {
    var int;
    for (i = 0; i < number.length; ++i) {
        int = parseInt(
            number.substring(i) +
            number.substring(0, i)
        );
        // if (!isPrime(int)) return false;
        console.log(int);
    }
    //return true;
}

var num = 1927;
allRotArePrime(num.toString());

http://jsfiddle.net/T6Mur/3/

Oh, don't forget to do 'var i' :) – jgroenen Oct 15 '13 at 14:40 — jgroenen, Oct 15 '13 at 14:40

Halcyon · Answer 2 · 2013-10-15T14:29:24.483

The if is your stopping condition. If string is only length 1 you only have one permutation.

the for loop is complex but it does something like this:

"" "1234" -> loop 4 times, giving:

"1", "234"
"2", "134"
"3", "124"
"4", "123"

Basically it moves one character from string to prefix, and it does all combinations to get all permutations.

Then it runs then next loop, which gives:

"12" "34"
"13" "24"
"14" "23"
"21" "34"
.. etc

Eventually you will get:

"123" "4" -> "1234"
"124" "3" -> "1243"
.. etc

As for you problem: note that it will be inefficient for numbers like 777 it will just give you 777 6 times. Also, you need rotations, not permutations. 197 should give 197,971,719 but not 179,791,917

How does this recursive code to find all permutations of a string work?

2 Answers2