permutations.java

a molecular graph kernel based on iterative graph similarity and optimal assignments

/**
 * ISOAK - Iterative similarity optimal assignment kernel.
 * 
 * Written by Matthias Rupp 2006-2007.
 * Copyright (c) 2006-2007, Matthias Rupp, Ewgenij Proschak, Gisbert Schneider.
 * 
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * 
 *  * The above copyright notice, this permission notice and the following disclaimers
 *    shall be included in all copies or substantial portions of this software.
 *  * The names of the authors may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 * 
 * Please cite
 * 
 * Matthias Rupp, Ewgenij Proschak, Gisbert Schneider:
 * A Kernel Approach to Molecular Similarity Based on Iterative Graph Similarity,
 * Journal of Chemical Information and Molecular Modeling, 47(6): 2280-2286, 2007, 
 * DOI http://dx.doi.org/10.1021/ci700274r.
 *
 * if you use this software.
 */

package info.mrupp.isoak1;

import static info.mrupp.isoak1.Factorial.factorial;

/**
 * Permutation related functions.
 * 
 * Provides static methods for the computation of all permutations of a given size,
 * all prefixes of given length of permutations of a given size, etc.
 */

public class Permutations {
	/**
	 * All permutations of {0,1,...,n-1}.
	 *
	 * Uses Heaps method.
	 * 
	 * @param n  permutation size. 
	 * @return   all permutations of {0,1,..,n-1} as an array of arrays.
	 */
	public static int[][] permutations(int n) {
		// Special cases.
		if (n < 0) throw new IllegalArgumentException("Permutation size must be non-negative."); 
		if (n == 0) { return new int[0][0]; }
		if (n == 1) { int[][] result = new int[1][1]; result[0][0] = 0; return result; }
		
		// Create result matrix, first row is identity permutation.
		int[][] result = new int[factorial(n)][n];
		for (int i=0; i < n; ++i) result[0][i] = i;
		
		// Initialize indices, buffers etc.
		int pidx = 1;  // Denotes currently created permutation.
		int[] c = new int[n]; for (int i=0; i < n; ++i) c[i] = 1;
		int ii = 1, k;
		
		// Create permutations.
		while (true) {
			if (c[ii] <= ii) {
				if (ii % 2 == 0) { k = 0; } else { k = c[ii]-1; }
				
				System.arraycopy(result[pidx-1], 0, result[pidx], 0, n);  // Copy previous line.
				int t = result[pidx][ii]; result[pidx][ii] = result[pidx][k]; result[pidx][k] = t;  // Swap ii-th and k-th entry.
				++pidx;
				
				c[ii] += 1;
				ii = 1;
			} else {
				c[ii] = 1;
				++ii;
			}
			
			if (ii >= n) break;
		}
		
		return result;
	}
	
	/**
	 * All prefixes of given length of all permutations of given length.
	 *
	 * Generates all length k prefixes of all permutations of {0,1,...,n-1} in lexicographic order.
	 * 
	 * - If k == 0, an empty matrix is returned.
	 * - Once calculated, permutation prefixes are kept across function calls.
	 * - There are (n over k)k! = n!/(n-k)! prefixes of length k of permutations of n elements.
     * 
     * @param k  prefix length.
     * @param n  permutation size.
     * @return   all permutations of {0,1,..,n-1} as an array of arrays.
	 */
	public static int[][] prefixes(int k, int n) {	
		// Special cases.
		if (k < 0 || k > n) throw new IllegalArgumentException("Prefix length must be in range [0,n].");
		if (k == 0) { return new int[0][0]; }
		if (k == n) { return Permutations.permutations(n); }
		
		// Compute prefixes.		
		int[][] result = new int[factorial(n)/factorial(n-k)][k];	// Result matrix.
		for (int i = 0; i < k; ++i) result[0][i] = i;				// Initialize first prefix.
		System.arraycopy(result[0], 0, result[1], 0, k);			// Take over into currently computed result row.
		int residx = 1;												// Current row.
		int idx = k-1;												// Index into current result row, starting at end.
		int[] a = new int[n];										// Symbols not currently in prefix, sorted ascendingly. During computation, additional indices may be temporarily stored.
		for (int i = 0; i < n-k; ++i) a[i] = k+i;					// Initialize remaining symbols.
		int alength = n-k;											// Current size of a (number of occupied entries).
		int j = 0;													// Index into a, starting at beginning.
				
		while (true) {
			// Find first incrementable index from the right.
			while (result[residx][idx] > a[j]) {
				a[alength] = result[residx][idx]; ++alength; 		// Remove large symbol from current prefix and store it in a.