What is wrong with my recursion to create permutations of a string?

Question

It is printing out a few permutations but the rest are null and I'm not sure why. I need to but all the permutations into String[] and I can't import any other package except for util.Arrays. Please help!

import java.util.Arrays;

public class DIE
{

    public static String[] printPermutations(String s)
    {
        int l = s.length();
        int f = factorial(l);
        int count = 0;
        String[] array = new String[f];
        permute("", s, array, 0);
        Arrays.sort(array);
        return array;
    }

    private static String[] permute(String x, String s, String [] array, int count)
    {
        int l = s.length(); 
        if (l == 0)
        {
            array[count] = (x + s);
        }
        for (int i = 0; i < l; i++)
        {
            permute(x + s.charAt(i), s.substring(0, i) + 
                    s.substring(i +1, s.length()), array, count);
            count++;
        }
        return array;
    }

    public static int factorial(int l)
    {
        if (l == 1)
        {
            return 1;
        }
        else
        {
            int result = l * factorial(l - 1);
            return result;
        }
    }

    /*
    Do not edit anything below this comment.
    */

    public static void main(String[] args)
    {
        String[] permutations = printPermutations(args[0]);
        for(String p : permutations)
        {
            System.out.println(p);
        }
    }
}

What kind of inputs are you giving? Post some examples, because I don't think this code is working properly for inputs like "Fable", "Cradle" etc — Govind Madhu, Sep 08 '16 at 04:51
In the main program, you don't need that for loop to print the array. Just remove the entire for loop and use :System.out.println(permutations); — Govind Madhu, Sep 08 '16 at 07:07
yes that what I thought, but I'm not allowed to change main and we have to return the substrings in a String[], unless i can return it in another form without changing main — Sam Craig, Sep 08 '16 at 07:15
Possible duplicate of [What is a debugger and how can it help me diagnose problems?](http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Raedwald, Sep 08 '16 at 08:31

Thomas Kläger · Answer 1 · 2016-09-08T10:20:33.430

Your count variable is wrong. Within the outermost call to permute("", "abc", ...) it is incremented only by one, even though the call to the next level permute("a", "bc", ...) creates two permutations!

There are two possible solutions:

Instead of a String[] to collect your result use a List<String>. Then you don't need to manually count the number of permutations.
let permute return the new count (instead of the result array, that one is never used anyway)

For permute to return the new count the method would look like this:

private static int permute(String x, String s, String [] array, int count)
{
    int l = s.length(); 
    if (l == 0)
    {
        array[count++] = x;
    }
    for (int i = 0; i < l; i++)
    {
        count = permute(x + s.charAt(i), s.substring(0, i) + 
                s.substring(i +1, s.length()), array, count);
    }
    return count;
}

Using a List<String> would need some more changes, but the permute function would be smaller:

public static List<String> printPermutations(String s)
{
    int l = s.length();
    int f = factorial(l);
    List<String> result = new ArrayList<>(f);
    permute("", s, result);
    Collections.sort(result);
    return result;
}

private static void permute(String x, String s, List<String> result)
{
    int l = s.length(); 
    if (l == 0)
    {
        result.add(x);
    }
    for (int i = 0; i < l; i++)
    {
        permute(x + s.charAt(i), s.substring(0, i) + 
                s.substring(i +1, s.length()), result);
    }
}

And some small changes in the main method due to the changed result of printPermutations (IMHO a very bad named method: it prints out nothing, it creates the permutations together with a helper method)

sorry could you explain more what you mean by let permute return the new count that what i was trying to do by including it in the formal parameters — Sam Craig, Sep 08 '16 at 07:31

What is wrong with my recursion to create permutations of a string?

1 Answers1