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

This link might help you. No code from me. Good luck.

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

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 4

using Dollar it is simple:

@Test
public void generatePermutations() {
    // digits is the string "0123456789"
    String digits = $('0', '9').join();

    // then generate 10 permutations
    for (int i : $(10)) {
        // shuffle, the cut (0, 4) in order to get a 4-char permutation
        System.out.println($(digits).shuffle().slice(4));
    }
}