Betlista's blog

By Betlista, 13 years ago, In English

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

  • Vote: I like it
  • +20
  • Vote: I do not like it

| Write comment?
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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:-)

»
13 years ago, # |
Rev. 4   Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree. But I've never seen such problems :D

»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
// 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;
}
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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}

»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why so many downvotes for this comment ? Infact I found the explanation under that link really useful. Thanks for the link.