Press "Enter" to skip to content

Generate All Permutations of an Array or String in Java

Ajk 1

How to generate all permutations of an array or string? This is quite the popular question in interviews… In fact, I personally got asked to generate all permutations of an array or string in 3 interviews last year. Therefore it is essential that if you are planning to go through interviews, you have a complete understanding of this question ready at your fingertips.

First of all to open up the topic, if you have forgotten those hard earned Calculus A+ when you were a freshman, here are a few helpful resources, Permutation on Wikipedia , Permutation on RegentPrep and Permutation on MathWorld to help you create a comprehensive view of the question at hand.

I personally like the second article much better, as it is smaller and much more concise. The initial line says it all:

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself.

Does not sound too hard, does it? So let us think about how to solve this problem. First of all as we always do, we have to discuss constraints and requirements. The number of outputs will be vastly large. Let’s take a look at an example of an array / string of 4 items:

Permutation of a 4 item array
Permutation of a 4 item array

As you can see the number of outputs is quite big, namely O(n!) time complexity (24 = 4*3*2*1). Do we want to hold all that data in memory? Probably not. We should suggest in our interview that it would be better if we assume that it’s ok to just print out the output. That should lessen the memory load, no? Let us see!

At first sight it seems like it would be easy to implement an answer to generate all permutations of an array or string, using recursion, since you can imagine how solving a subset of the problem (solving a permutation of 3 items in the above example), will greatly help in solving the permutation of 4 items.

How to Generate All Permutations of an Array or String – Basic Algorithm

  • For each item in the array: Get the item, and append to it the permutation of the remaining elements
  • The base case: The permutation of a single item – is itself.

As you can see it sounds pretty easy!! So let us just get our hands to it and try to program a solution that will generate all permutations of an array or string in PHP.

How to Generate All Permutations of an Array or String in PHP

Well it took me a bit longer to write but it worked out at the end. To be noted is that since we are using PHP we can use a wonderful feature of the language which passes objects by value, rather than reference (unless otherwise noted), so in this case we can ignore the fact that our arrays are being changed in inside functions, since to the callee, they will seem unchanged :). So how would we find all permutations of an array or string in a language that passes arguments by reference such as Java or C++? Well the idea is that we would have to deep copy the passed array, so let us see how that would work.

Assumption – There are no negative items in the permutation array.

How to Generate All Permutations of an Array or String in Java

As you can see it seems very similar, with a few tweaks per the language. In fact we did not have to deep copy the array / list / string, because we are always setting it back to the original form.

This was a first post on How to Generate All Permutations of an Array or String in Java and PHP. Most likely if you can write this out and mention the reference and value argument pointers for the language of your choice, you will do just fine in your interview. However there are a few caveats. While we analyzed the time complexity from the beginning, we did not say anything about the space complexity of our solution. As it turns out, we are using about O(N!) space too, since we are keeping haggling arrays in our stack. This might be a bottleneck, but the solution needs a trickier algorithm which is generally not required to do well in this “How to Generate All Permutations of an Array” interview question, but which could make you look like a superstar. Given it’s complexity we will take a look at that solution in a part II of this post.

Hope you guys enjoyed it! And I’ll see you guys next time ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂