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
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?
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:-)
I think there is a simplier way to work with permutations in Java:
> 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
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.I agree. But I've never seen such problems :D
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.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}
I did write a class for to handle permutations: http://www.uwe-alex.de/Permutation/Permutation.html
The 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
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
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
Why so many downvotes for this comment ? Infact I found the explanation under that link really useful. Thanks for the link.