Partner – Moderne – NPI EA (cat=Spring Boot)
announcement - icon

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Course – Black Friday 2026 – NPI EA – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

1. Introduction

In this article, we’ll look at how to create permutations of an array.

First, we’ll define what a permutation is. Second, we’ll look at some constraints. And third, we’ll look at three ways to calculate them: recursively, iteratively, and randomly.

We’ll focus on the implementation in Java and, therefore, won’t go into a lot of mathematical detail.

2. What Is a Permutation?

A permutation of a set is a rearrangement of its elements. A set which consists of n elements has n! permutations. Here n! is the factorial, which is the product of all positive integers smaller or equal to n.

2.1. Example

The array of integers [3,4,7] has three elements and six permutations:

n! = 3! = 1 x 2 x 3 = 6

Permutations: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Constraints

The number of permutation increases fast with n. While it takes only a few seconds to generate all permutations of ten elements, it will take two weeks to generate all permutations of 15 elements:

permutations

3. Algorithms

3.1. Recursive Algorithm

The first algorithm we look at is Heap’s algorithm. It’s a recursive algorithm which produces all permutations by swapping one element per iteration.

The input array will be modified. If we don’t want that, we need to create a copy of the array before calling the method:

public static <T> void printAllRecursive(
  int n, T[] elements, char delimiter) {

    if(n == 1) {
        printArray(elements, delimiter);
    } else {
        for(int i = 0; i < n-1; i++) {
            printAllRecursive(n - 1, elements, delimiter);
            if(n % 2 == 0) {
                swap(elements, i, n-1);
            } else {
                swap(elements, 0, n-1);
            }
        }
        printAllRecursive(n - 1, elements, delimiter);
    }
}

The method uses two helper methods:

private static void swap(T[] elements, int a, int b) {
    T tmp = elements[a];
    elements[a] = elements[b];
    elements[b] = tmp;
}
private static void printArray(T[] elements, char delimiter) {
    String delimiterSpace = delimiter + " ";
    for(int i = 0; i < elements.length; i++) {
        System.out.print(elements[i] + delimiterSpace);
    }
    System.out.print('\n');
}

Here, we write the result to System.out, however, we can easily store the result in an array or in a list instead.

3.2. Iterative Algorithm

Heap’s algorithm can also be implemented using iterations:

int[] indexes = new int[n];
for (int i = 0; i < n; i++) {
    indexes[i] = 0;
}

printArray(elements, delimiter);

int i = 0;
while (i < n) {
    if (indexes[i] < i) {
        swap(elements, i % 2 == 0 ?  0: indexes[i], i);
        printArray(elements, delimiter);
        indexes[i]++;
        i = 0;
    }
    else {
        indexes[i] = 0;
        i++;
    }
}

3.3. Permutations in Lexicographical Order

If the elements are comparable, we can generate permutations sorted by the natural order of the elements:

public static <T extends Comparable<T>> void printAllOrdered(
  T[] elements, char delimiter) {

    Arrays.sort(elements);
    boolean hasNext = true;

    while(hasNext) {
        printArray(elements, delimiter);
        int k = 0, l = 0;
        hasNext = false;
        for (int i = elements.length - 1; i > 0; i--) {
            if (elements[i].compareTo(elements[i - 1]) > 0) {
                k = i - 1;
                hasNext = true;
                break;
            }
        }

        for (int i = elements.length - 1; i > k; i--) {
            if (elements[i].compareTo(elements[k]) > 0) {
                l = i;
                break;
            }
        }

        swap(elements, k, l);
        Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length));
    }
}

This algorithm has a reverse operation in every iteration; therefore, it is less efficient on arrays than Heap’s algorithm.

3.4. Randomized Algorithm

If n is big, we can generate a random permutation by shuffling the array:

Collections.shuffle(Arrays.asList(elements));

We can do this several times to generate a sample of permutations.

We might create the same permutations more than once, however, for big values of n, the chances to generate the same permutation twice are low.

4. Conclusion

There are many ways to generate all permutations of an array. In this article, we saw the recursive and iterative Heap’s algorithm and how to generate a sorted list of permutations.

It’s not feasible to generate all permutations for large arrays, therefore, we can generate random permutations instead.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.
Partner – Moderne – NPI EA (tag=Refactoring)
announcement - icon

Modern Java teams move fast — but codebases don’t always keep up. Frameworks change, dependencies drift, and tech debt builds until it starts to drag on delivery. OpenRewrite was built to fix that: an open-source refactoring engine that automates repetitive code changes while keeping developer intent intact.

The monthly training series, led by the creators and maintainers of OpenRewrite at Moderne, walks through real-world migrations and modernization patterns. Whether you’re new to recipes or ready to write your own, you’ll learn practical ways to refactor safely and at scale.

If you’ve ever wished refactoring felt as natural — and as fast — as writing code, this is a good place to start.

Course – Black Friday 2026 – NPI EA – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW