Generating variations without repetitions / Rearrangements in java

Question

I need to generate all the options without repeating from the numbers 0-9.

Their length can be from 1 to 10. I really do not know how to solve it, especially how to avoid repetition.

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

I would be very grateful if someone could help me in this matter, especially with code and tips.

Answer 1

The search keyword is permutation. There is a lot of free source code that executes them.

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

(Same as duffymo said: I will not provide the code for this)

Extended note: recursion is based on 0/1 (exception, inclusion), which can be directly translated to bits, therefore, integers. Therefore, to get all possible combinations of numbers without actually doing recursion, you can simply use all 10-bit integers and scroll through them. Then interpret the numbers so that the dial bit matches the inclusion of the digit in the list that you want to move.

Answer 2

Here is my java code. Feel free to ask if you understand. The main thing here:

• sort an array of characters. for example: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
• generate a permutation and always keep the condition: index a1 <index a2 <index 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 3

Imagine that you have a magic function - a given array of numbers, it will return you the correct permutations.

How can you use this function to create a new permutation list with just one extra digit?

eg,

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

...

as soon as you decide, what did you notice? can you generalize it?

Answer 4

using Dollar , it's 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)); } } 

Answer 5

The code for this is similar to code without duplicates, with the addition of an if-else statement. Mark this code

In the above code, change the for loop as follows

 for (j = i; j <= n; j++) { if(a[i]!=a[j] && !is_duplicate(a,i,j)) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); } else if(i!=j) {} // if no duplicate is present , do nothing else permute(a,i+1,n); // skip the ith character } bool is_duplicate(int *a,int i,int j) { if a[i] is present between a[j]...a[i] return 1; otherwise return 0; } 

worked for me

Answer 6

Permutation without repetition is based on the theorem that the number of results is a factorial of the number of elements (in this case, numbers). In your case 10! 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. The proof that this is accurate is the right solution for the generation. Well, since. In the first position, i.e. On the left, you can have 10 numbers, and in the second position you can only have 9 numbers, because one number is in the position on the left, and we cannot repeat the same number, etc. (The proof is carried out using mathematical induction). So how to generate the first ten results? According to my knowledge, the easiest way is to use a cyclic shift. This means that the order of shifting the number to the left is one position (or to the right, if you want), and a number that overflows to put in an empty place. This means that for the first ten results:

10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 1 10 9 8 7
5 4 3 2 1 10 9 8 7 6
...

The first line is the base sample, so it is recommended to add it to the set before generation. The advantage is that in the next step you have to solve the same problem to avoid unwanted duplicity.

In the next step, recursively rotate only 10-1 numbers 10-1 times, etc. This means that the first 9 results in the second step:

10 9 8 7 6 5 4 3 2 1
10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 2 1 9 8 7 6
...

etc., note that the first line is present from the previous step, therefore it cannot be added to the generated set again.

The algorithm recursively does just that, as explained above. You can create all combinations of 3628800 for 10 !, because the number of attachments is the same as the number of elements in the array (this means that in your case for 10 numbers it lingers for about 5 minutes on my computer), and you need to have enough memory if you want to save all combinations in an array.

There is a solution.

 package permutation; /** Class for generation amount of combinations (factorial) * !!! this is generate proper permutations without repeating and proper amount (počet) of rows !!! * * @author hariprasad */ public class TestForPermutationII { private static final String BUMPER = "*"; private static int counter = 0; private static int sumsum = 0; // definitoin of array for generation //int[] testsimple = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int[] testsimple = {1, 2, 3, 4, 5}; private int ELEMNUM = testsimple.length; int[][] shuff; private String gaps(int len) { String addGap = ""; for(int i=0; i <len; i++) addGap += " "; return addGap; } /** Factorial computing */ private int fact(int num) { if (num > 1) { return num * fact(num - 1); } else { return 1; } } /** Cyclic shift position to the left */ private int[] lShiftPos(int[] arr, int pos) { int[] work = new int[ELEMNUM]; int offset = -1; for (int jj = 0; jj < arr.length; jj++) { if (jj < pos) { work[jj] = arr[jj]; } else if (jj <= arr.length - 1) { if (jj == pos) { offset = arr[pos]; // last element } if (jj != (arr.length - 1)) { work[jj] = arr[jj + 1]; } else { work[jj] = offset; } } } return work; } private String printBuff(int[] buffer) { String res = ""; for (int i= 0; i < buffer.length; i++) { if (i == 0) res += buffer[i]; else res += ", " + buffer[i]; } return res; }; /** Recursive generator for arbitrary length of array */ private String permutationGenerator(int pos, int level) { String ret = BUMPER; int templen = counter; int[] work = new int[ELEMNUM]; int locsumread = 0; int locsumnew = 0; //System.out.println("\nCalled level: " + level); for (int i = 0; i <= templen; i++) { work = shuff[i]; sumsum++; locsumread++; for (int ii = 0; ii < pos; ii++) { counter++; sumsum++; locsumnew++; work = lShiftPos(work, level); // deep copy shuff[counter] = work; } } System.out.println("locsumread, locsumnew: " + locsumread + ", " + locsumnew); // if level == ELEMNUM-2, it means no another shift if (level < ELEMNUM-2) { ret = permutationGenerator(pos-1, level+1); ret = "Level " + level + " end."; //System.out.println(ret); } return ret; } public static void main(String[] argv) { TestForPermutationII test = new TestForPermutationII(); counter = 0; int len = test.testsimple.length; int[] work = new int[len]; test.shuff = new int[test.fact(len)][]; //initial test.shuff[counter] = test.testsimple; work = test.testsimple; // shalow copy test.shuff = new int[test.fact(len)][]; counter = 0; test.shuff[counter] = test.testsimple; test.permutationGenerator(len-1, 0); for (int i = 0; i <= counter; i++) { System.out.println(test.printBuff(test.shuff[i])); } System.out.println("Counter, cycles: " + counter + ", " + sumsum); } } 

The intensity (number of cycles) of the algorithm is the sum of the incomplete factorials of the number of members. Thus, there is an overhang when a partial set is read again to generate the next subset, so the intensity:

P! + n! / 2! + n! / 3! + ... + n! / (n-2)! + n! (n-1)!

Answer 7

There is one solution that is not from me, but it is very beautiful and complex.

  package permutations; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Set; /** * @author Vladimir Hajek * */ public class PermutationSimple { private static final int MAX_NUMBER = 3; Set<String> results = new HashSet<>(0); /** * */ public PermutationSimple() { // TODO Auto-generated constructor stub } /** * @param availableNumbers * @return */ public static List<String> generatePermutations(Set<Integer> availableNumbers) { List<String> permutations = new LinkedList<>(); for (Integer number : availableNumbers) { Set<Integer> numbers = new HashSet<>(availableNumbers); numbers.remove(number); if (!numbers.isEmpty()) { List<String> childPermutations = generatePermutations(numbers); for (String childPermutation : childPermutations) { String permutation = number + childPermutation; permutations.add(permutation); } } else { permutations.add(number.toString()); } } return permutations; } /** * @param args */ public static void main(String[] args) { Set<Integer> availableNumbers = new HashSet<>(0); for (int i = 1; i <= MAX_NUMBER; i++) { availableNumbers.add(i); } List<String> permutations = generatePermutations(availableNumbers); for (String permutation : permutations) { System.out.println(permutation); } } } 

I think this is a great solution.

Answer 8

I created the following code to generate permutations, where ordering is important without repetition. It uses generics to swap 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; } } 

Answer 9

Brief Useful Permutation Indexing Knowledge

Create a method that generates the correct permutation, given the index value between {0 and N! -1} for "zero indexing" or {1 and N!} For "one indexed".

Create a second method containing a "for loop" where the lower bound is 1 and the upper bound is N !. eg. "for (i; i <= N!; i ++)" for each instance of the loop call the first method, passing me as an argument.