generating Variations without repetitions / Permutations in java

Question

I have to generate all variations without repetitions made of digits 0 - 9.

Length of them could be from 1 to 10. I really don't know how to solve it, especially how to avoid repetitions.

Example: length of variations: 4 random variations: 9856, 8753, 1243, 1234 etc. (but not 9985 - contains repetition)

I would be really grateful if somebody can help me with that issue, especially giving some code and clues.

Answer 1

Here is my Java code. Feel free to ask if you don't understand. The main point here is:

1. sort again character array. for example: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
2. generate permutation and always keep condition: index of a1 < index of a2 < index of a3 ...

import java.util.Arrays;

public class PermutationDup {

    public void permutation(String s) {
        char[] original = s.toCharArray();
        Arrays.sort(original);
        char[] clone = new char[s.length()];
        boolean[] mark = new boolean[s.length()];
        Arrays.fill(mark, false);
        permute(original, clone, mark, 0, s.length());
    }

    private void permute(char[] original, char[] clone, boolean[] mark, int length, int n) {
        if (length == n) {
            System.out.println(clone);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (mark[i] == true) continue;
            // dont use this state. to keep order of duplicate character
            if (i > 0 && original[i] == original[i-1] && mark[i-1] == false) continue;
            mark[i] = true;
            clone[length] = original[i];
            permute(original, clone, mark, length+1, n);
            mark[i] = false;
        }

    }

    public static void main(String[] args) {
        PermutationDup p = new PermutationDup();
        p.permutation("abcab");
    }
}

Answer 2

The keyword to look for is permutation. There is an abundance of source code freely available that performs them.

As for keeping it repetition free I suggest a simple recursive approach: for each digit you have a choice of taking it into your variation or not, so your recursion counts through the digits and forks into two recursive calls, one in which the digit is included, one in which it is excluded. Then, after you reached the last digit each recursion essentially gives you a (unique, sorted) list of repetition-free digits. You can then create all possible permutations of this list and combine all of those permutations to achieve your final result.

(Same as duffymo said: I won't supply code for that)

Advanced note: the recursion is based on 0/1 (exclusion, inclusion) which can directly be translated to bits, hence, integer numbers. Therefore, in order to get all possible digit combinations without actually performing the recursion itself you could simply use all 10-bit integer numbers and iterate through them. Then interpret the numbers such that a set bit corresponds to including the digit in the list that needs to be permuted.

Answer 3

I have created the following code for generating permutations where ordering is important and with no repetition. It makes use of generics for permuting any type of object:

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations {

    public static <T> Collection<List<T>> generatePermutationsNoRepetition(Set<T> availableNumbers) {
        Collection<List<T>> permutations = new HashSet<>();

        for (T number : availableNumbers) {
            Set<T> numbers = new HashSet<>(availableNumbers);
            numbers.remove(number);

            if (!numbers.isEmpty()) {
                Collection<List<T>> childPermutations = generatePermutationsNoRepetition(numbers);
                for (List<T> childPermutation : childPermutations) {
                    List<T> permutation = new ArrayList<>();
                    permutation.add(number);
                    permutation.addAll(childPermutation);
                    permutations.add(permutation);
                }
            } else {
                List<T> permutation = new ArrayList<>();
                permutation.add(number);
                permutations.add(permutation);
            }
        }

        return permutations;
    }
}