Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

### Блог пользователя Betlista

Автор Betlista, 7 лет назад, ,

Coders always argue which programming language is better. Each one of you have some preference. I like Java the most. But there is at least one thing missing in Java for sure — permutations.
C has a function (next_permutation()), that modifies permutation (parameter) to next permutation (lexicographically greater), if such permutation exists is function return value is true, false otherwise.

My version of such function in Java:

	// simply prints all permutation - to see how it works
private static void printPermutations( Comparable[] c ) {
System.out.println( Arrays.toString( c ) );
while ( ( c = nextPermutation( c ) ) != null ) {
System.out.println( Arrays.toString( c ) );
}
}

// modifies c to next permutation or returns null if such permutation does not exist
private static Comparable[] nextPermutation( final Comparable[] c ) {
// 1. finds the largest k, that c[k] < c[k+1]
int first = getFirst( c );
if ( first == -1 ) return null; // no greater permutation
// 2. find last index toSwap, that c[k] < c[toSwap]
int toSwap = c.length - 1;
while ( c[ first ].compareTo( c[ toSwap ] ) >= 0 )
--toSwap;
// 3. swap elements with indexes first and last
swap( c, first++, toSwap );
// 4. reverse sequence from k+1 to n (inclusive)
toSwap = c.length - 1;
while ( first < toSwap )
swap( c, first++, toSwap-- );
return c;
}

// finds the largest k, that c[k] < c[k+1]
// if no such k exists (there is not greater permutation), return -1
private static int getFirst( final Comparable[] c ) {
for ( int i = c.length - 2; i >= 0; --i )
if ( c[ i ].compareTo( c[ i + 1 ] ) < 0 )
return i;
return -1;
}

// swaps two elements (with indexes i and j) in array
private static void swap( final Comparable[] c, final int i, final int j ) {
final Comparable tmp = c[ i ];
c[ i ] = c[ j ];
c[ j ] = tmp;
}


The above code is inspired by wikipedia.

Probably most of you know, that number of permutations is n!, so checking all permutations is ok when n <= 10.

For example, it lasts 0,3s to generate all lucky numbers (containing only digits 4 and 7, where number of 4s and 7s is the same) with length 24 (there are 24!/12!/12! such numbers).

edit: corrected the "definition" of lucky number

•
• +20
•

 » 7 лет назад, # |   +1 What's your definition of a lucky number? If it's "any number that contains only digits 4 and 7", then I don't understand how you get the quantity of such numbers of length 24. Every digit can be either 4 or 7, no other restrictions, so it should be 2^24, shouldn't it?
•  » » 7 лет назад, # ^ |   0 Thanks for correction, of course lucky numbers in problem statements are the numbers that have only 4 and 7 digits and count of 4s and 7s is the same O:-)
 » 7 лет назад, # | ← Rev. 4 →   +13 I think there is a simplier way to work with permutations in Java: void generate(int[] p, int L, int R) { if (L == R) { // all numbers are set // do something with permutation in array p[] } else { // numbers at positions [0, L-1] are set, try to set L-th position for (int i = L; i <= R; i++) { int tmp = p[L]; p[L] = p[i]; p[i] = tmp; generate(p. L+1, R); tmp = p[L]; p[L] = p[i]; p[i] = tmp; } } } > For example, it lasts 0,3s to generate all lucky numbers (containing only digits 4 and 7) with length 24 (there are 24!/12!/12! such numbers).There are 2^24 lucky numbers of length 24; you said about lucky numbers which have equal numbers of '4' and '7'.Update: generating these numbers using bitmasks also takes 0.3 seconds, but is easier to code: 1238640, or with Integer.bitCount() instead of bitcounts array: 1238647
•  » » 7 лет назад, # ^ |   0 Thanks for your reply :-)First, thanks for correction for definition of lucky number.Your code generates permutation correctly if all elements are different, if there are same elements it generates same sequences. Also if there is need to generate only permutations from some permutation, for example: "generate all permutations of 11 elements, lexicographically greater than [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]", but your code was not meant to do it I know, I will rename the blog entry.
•  » » » 7 лет назад, # ^ |   0 I agree. But I've never seen such problems :D
 » 7 лет назад, # |   +17 // C++ next_permutation() analog in Java boolean next_permutation(int[] p) { for (int a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.length - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } 
•  » » 7 лет назад, # ^ |   0 That is the same code as the one above, but I used Comparable intentionally — it can compare other type of objects too, for example Strings, characters (I know that you can do int n = 'a'), BigDecimals and so on without the change.
•  » » » 7 лет назад, # ^ |   +1 But my code can be much faster than yours, if compareTo() method is slow. You can always replace your Comparable[] array with an integer permutation. For example you can replace {"a", "ab", "ab"} with {0, 1, 1}
•  » » 6 лет назад, # ^ |   0 simple and beautiful. I like it. Thanks.
 » 7 лет назад, # |   +3 I did write a class for to handle permutations: http://www.uwe-alex.de/Permutation/Permutation.htmlThe class has several methods to walk or jump through the list of possible permutations. The Method next() creates the next Permutation, the method next(int n) creates the first Permutation wich is greater than this and has a change in index n Example:Permutation: 0 1 2 3 4 5 6 next(3) Permutation: 0 1 2 4 3 5 6
•  » » 6 лет назад, # ^ |   0 This sounds awsome. Could you please post it here, because the site is down?
 » 6 лет назад, # |   0 Thanks. This is good.
 » 4 года назад, # |   +8 Here is an UVa problem if you want to try your algorithms for obtaining the next permutation:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=82
 » 3 года назад, # |   0 If my input is of larger length and the pivot index( where c[k]
 » 21 месяц назад, # |   -17 This is a really good explanation of the derivation of the algorithm: https://www.quora.com/How-would-you-explain-an-algorithm-that-generates-permutations-using-lexicographic-ordering
•  » » 6 месяцев назад, # ^ |   0 Why so many downvotes for this comment ? Infact I found the explanation under that link really useful. Thanks for the link.