Swap with repetition in Java (lines look like this: 00001112222)

Question

I have lines of the form 000011122222 . That is, consecutive numbers are repeated randomly. time. Some other examples may be as follows:

 0011122223333 01222 00011234444 001122222 

etc. I know, for example, for line 01222 , which can be a complete rearrangement of 5!/3! . I need to generate all these permutations for each such line.

I tried to generate permutations in various ways. One of them is the generation of all possible permutations (as for non-repeating strings), but since the strings I will be using can be very large, it can waste time generating too many redundant permutations.

Secondly, I tried to put numbers in random indexes of an array of characters equal to the size of the string, and loop completion when the number of digits will be the same as in the input string. However, I spend a lot of memory and also take a lot of time.

I need an efficient way to create permutations for such strings. Just an algorithm or code, or welcome. I am using Java.

Thanks!

Answer 1

One of the standard algorithms for generating permutations is an algorithm for listing them in lexicographically increasing order . This algorithm, which is used by most implementations of the C ++ std::next_permutation , generates permutations no more than O (n) time for each permutation and skips all permutations that are duplicates of each other. It is also very easy to code.

Hope this helps!

Answer 2

Instead of rearranging the original string of numbers, rearrange the groups of numbers. I don't know how to best describe it, so I will try a few psuedocode.

For the string "001222" a group of digits - two 0, 1 and 3 seconds.

 permute(groups, permutation): if there are no non-empty groups print permutation else for each non-empty group permutation += group.digit --group.count permute(groups, permutation) 

By looping groups, not all numbers, he avoids generating duplicates, because each digit can only be selected once for the next position, and not several times. Looking through a random permutation, you get

 Permutation Digit Groups 0: 2, 1: 1, 2: 3 // start 0 0: 1, 1: 1, 2: 3 02 0: 1, 1: 1, 2: 2 // * 021 0: 1, 1: 0, 2: 2 // the 1 group is removed from the set 0212 0: 1, 1: 0, 2: 1 02120 0: 0, 1: 0, 2: 1 // the 0 group is removed from the set 021202 0: 0, 1: 0, 2: 0 // the 2 group is removed from the set 

Now go to the * page.

 02 0: 1, 1: 0, 2: 1 

Since you are looping over groups of numbers, and not all (repeating) numbers from the original string, you cannot select 2 again. This means that all permutations starting with “02” will be unique because the prefix “02” is generated only once. The same goes for the algorithm.

Update

Here is a quick PHP implementation that produces 60 permutations for entering "001222":

 function permute(&$groups, &$count, $permutation) { $done = true; foreach ($groups as &$group) { if ($group[1] > 0) { --$group[1]; permute($groups, $count, $permutation . $group[0]); ++$group[1]; $done = false; } } if ($done) { echo $permutation . PHP_EOL; ++$count; } } $groups = array( array(0, 2), array(1, 1), array(2, 3), ); $count = 0; permute($groups, $count, ''); echo "\nTotal: $count\n"; 

Answer 3

You can create lines by randomly selecting the number of digits. Like this:

 length : int - Total string length digits : int - maximum digit to include in the string string : String - the return value for(i : int from 0 to digits) { remainingChars : int = length - length(string) //remaining chars in string remainingDigits : int = digits - i + 1 count : int = Random from 1 to (remainingChars - remainingDigits + 1) Append count times i to the string } 

Answer 4

I don’t know exactly what you are trying to say, but I once needed a permutation version, where I had a set of numbers like 012, and all permutations were:

012 021 102 120 201 210

to achieve this, I looked at wikipedia http://en.wikipedia.org/wiki/Permutation to find the algorithm, then I just created a way for it:

  public static boolean Permute(int[] a) { int k, l, n = a.length -1; for (k = n -1; ; k--) { if (k == -1) return false; if (a[k] < a[k + 1]) break; } for (l = n; l >= 0; l--) { if (a[k] < a[l]) { int opt = a[l]; a[l] = a[k]; a[k] = opt; break; } } for (int i = k + 1, j = n; i < j; i++, j--) { int opt = a[i]; a[i] = a[j]; a[j] = opt; } return true; } 

I can help you if you are more specific