generating Variations without repetitions / Permut

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

Imagine you had a magical function - given an array of digits, it will return you the correct permutations.

How can you use that function to produce a new list of permutations with just one extra digit?

e.g.,

if i gave you a function called permute_three(char[3] digits), and i tell you that it only works for digits 0, 1, 2, how can you write a function that can permute 0, 1, 2, 3, using the given permute_three function?

...

once you solved that, what do you notice? can you generalize it?

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

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");
    }
}