print all possible permutations of r elements in a given integer array of size n in Java

Question

Given an array of size n, generate and print all possible permutations of r elements in array.

For example, if n is 4, input array is [0, 1, 2, 3], and r is 3, then output should be

[0, 1, 2]
[0, 1, 3]
[0, 2, 1]
[0, 2, 3]
[0, 3, 1]
[0, 3, 2]
[1, 0, 2]
[1, 0, 3]
[1, 2, 0]
[1, 2, 3]
[1, 3, 0]
[1, 3, 2]
[2, 0, 1]
[2, 0, 3]
[2, 1, 0]
[2, 1, 3]
[2, 3, 0]
[2, 3, 1]
[3, 0, 1]
[3, 0, 2]
[3, 1, 0]
[3, 1, 2]
[3, 2, 0]
[3, 2, 1]

All elements in the input array are integers, from 0 to n-1. How can I use Java to print all possible permutations?

Important: the number of all elements in a single permutation is not always the size of original array. It's less or equal to the size of original array. Additionally, the order of elements in each permutation does matter.

I have written some code when n=4 and r=3. If n = 100 and r = 50, my code will be really ugly. Is there any smart way to do this when parameters are only n and r?

public static void main(String[] args) {

    // original array
    ArrayList < Integer > items = new ArrayList < > ();

    // all permutations
    ArrayList < ArrayList < Integer >> allPermutations = new ArrayList < ArrayList < Integer >> ();

    // define the end item of the original array.
    // this is n, suppose it's 4 now.
    int endItem = 4;
    for (int i = 0; i < endItem; i++) {
        items.add(i);
    }


    // r means how many elements in each single permutation
    // suppose it's 3 now, i have to write for-loop three times
    // if r is 100, i have to write for-loop 100 times

    // first of the "r"
    for (int i = 0; i < items.size(); i++) {
        // second of the "r"
        for (int j = 0; j < items.size(); j++) {
            // can't be identical to i
            if (j == i)
                continue;

            // third of the "r"
            for (int k = 0; k < items.size(); k++) {
                // can't be identical to i or j
                if (k == i || k == j)
                    continue;

                // a single permutation
                ArrayList < Integer > singlePermutation = new ArrayList < > ();
                singlePermutation.add(items.get(i));
                singlePermutation.add(items.get(j));
                singlePermutation.add(items.get(k));

                // all permutations
                allPermutations.add(singlePermutation);

            }
        }
    }
    for (ArrayList < Integer > permutation: allPermutations) {
        System.out.println(permutation);
    }
    System.out.println(allPermutations.size());

}

Answer 1

Moved solution from question to answer:

Solution:

Thanks to older coder, I managed to find the solution.

public class PermutationTest10 {
    // a is the original array
    // k is the number of elements in each permutation
    public static ArrayList<ArrayList<Integer>> choose(ArrayList<Integer> a, int k) {
        ArrayList<ArrayList<Integer>> allPermutations = new ArrayList<ArrayList<Integer>>();
        enumerate(a, a.size(), k, allPermutations);
        return allPermutations;
    }

  // a is the original array
    // n is the array size
    // k is the number of elements in each permutation
    // allPermutations is all different permutations
    private static void enumerate(ArrayList<Integer> a, int n, int k, ArrayList<ArrayList<Integer>> allPermutations) {
        if (k == 0) {
            ArrayList<Integer> singlePermutation = new ArrayList<Integer>();
            for (int i = n; i < a.size(); i++){
                singlePermutation.add(a.get(i));
            }
            allPermutations.add(singlePermutation);
            return;
        }

      for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            enumerate(a, n-1, k-1, allPermutations);
            swap(a, i, n-1);
        }
    }  

  // helper function that swaps a.get(i) and a.get(j)
    public static void swap(ArrayList<Integer> a, int i, int j) {
        Integer temp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }


  // sample client
    public static void main(String[] args) {

      // n is the end item of the array.
        // if n = 5, the array is [0, 1, 2, 3, 4, 5]
        // k is the number of elements of each permutation.
        int n =5;
        int k =3;

      // create original array
        ArrayList<Integer> elements = new ArrayList<> ();
        for (int i =0; i < n; i ++){
            elements.add(i);
        }

      ArrayList<Integer> a = new ArrayList<> ();
        for (int i = 0; i < n; i ++){
            a.add(elements.get(i));
        }
        System.out.println(choose(a, k));
    }
}