Kth Order Statistics/Partial ordering – Using Tournament Algorithm (optimized)

 on Jan 13, 2011

This blog entry is in continuation to my previous entries about finding 2nd Minimum and more generic K^th Order statistic in linear time (asymptotic) using dynamic programming principles and tournament algorithm in particular. Here I talk about slight variation to the tournament algorithm implementation that results in better runtime performance. Using modification to our earlier logic we can find K^th min without any need for back-tracking. We still need to build the tournament tree, but the new mechanism results in better runtime efficiency and is also simpler to implement (compared to what we did earlier).

The Idea

The idea is that if keep track of nodes a given node is compared at each level as the node progress in tournament method, we have sufficient information to deduct K^th minimum without ever back tracking the tournament tree. To find second minimum, we inspect the root node’s defeated-node-list for the minimum value. Once we have second minimum; for finding third min we combine second min node’s defeated-node-list to minimum (root) node's defeated node-list and find the third minimum from the resulting set. This method may need some additional processing while constructing tournament tree (and perhaps little more memory), but it is worth the effort as it saves us from backtracking tournament tree to find K^th min.

Details

Referring to the same sample list used previously. If we were to keep track of defeated nodes, we can obtain something like the following:

We wrap the input data into a node structure which can encapsulate the key and also the value (in typical scenario there will be some data value that these keys would be pointing to). In addition to key and value, each node contains a list (defeated-nodes linked-list) of nodes. As a node progress to next level, it appends the defeated node to its defeated-node-list.

After constructing the tournament tree and generating node-list of defeated nodes, for each node, can easily find the K^th minimum by traversing the graph from root-node.

For example, here's how we can find 2^nd, 3^rd and 4^th min for the example above:

2^nd Minimum: Looking at the node-list for root node, we can find the second minimum without any back-tracking. Since the root node must have defeated second min node on its way to last level, second min must be the minimum node in the defeated-node-list for the root node. For the case above from the node-list we can find the second minimum value as 2.

3rd Minimum: To find third minimum, we need to go to second minimum node, get its node-list and then find the third minimum from among the combined list for the minimum and second minimum. Since we already have node with value 2 in node-list of root node, we obtain its node list and find the third least from the resulting set. For the above case it will be 3 (the node with key 2 returns 14 and 5 which is larger than 3 which root node holds).

4th Minimum: Continuing the same idea, we obtain node-list for node with key 3 (found in node-list of root); combine it with node-list of min and second min, to find the 4th min from the resulting set.

In general, the root node has node-list which is log(n) size which contains the second min. From second min we can obtain its node-list and combined with node-list of min, we can obtain third min and so on. This mechanism does not require any backtracking, once we build node-list for each progressing node. 

  
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Copyright (c) 2010-2020 Malkit S. Bhasin. All rights reserved.
 * 
 * All source code and material on this Blog site is the copyright of Malkit S.
 * Bhasin, 2010 and is protected under copyright laws of the United States. This
 * source code may not be hosted on any other site without my express, prior,
 * written permission. Application to host any of the material elsewhere can be
 * made by contacting me at mbhasin at gmail dot com
 * 
 * I have made every effort and taken great care in making sure that the source
 * code and other content included on my web site is technically accurate, but I
 * disclaim any and all responsibility for any loss, damage or destruction of
 * data or any other property which may arise from relying on it. I will in no
 * case be liable for any monetary damages arising from such loss, damage or
 * destruction.
 * 
 * I further grant you ("Licensee") a non-exclusive, royalty free, license to
 * use, modify and redistribute this software in source and binary code form,
 * provided that i) this copyright notice and license appear on all copies of
 * the software;
 * 
 * As with any code, ensure to test this code in a development environment
 * before attempting to run it in production.
 * 
 * @author Malkit S. Bhasin
 * 
 */

public class KThMinimum2 {

	/**
	 * @param inputList
	 *            unordered linked list of Node
	 * @param k
	 *            order of minimum value desired
	 * @return kth minimum Node
	 * @throws Exception
	 */
	public static Node getKthMinimum(
			List> inputList, int k) throws Exception {
		return findKthMinimum(inputList, k).get(k - 1);
	}

	/**
	 * @param inputList
	 *            unordered linked list of non-negative integers
	 * @param k
	 *            ordered number of minimum values
	 * @return k ordered minimum values
	 * @throws Exception
	 */
	public static List> getMinimumKSortedElements(
			List> inputList, int k) throws Exception {
		return findKthMinimum(inputList, k);
	}

	/**
	 * First output tree will be obtained using tournament method. During each
	 * round, adjacent nodes are compared against, the lower of two moves to
	 * next round. The defeated node is added to list of defeated nodes
	 * maintained at each node.
	 * 
	 * Kth minimum is obtained by going through list of defeated nodes, starting
	 * from the root node (minimum node).
	 * 
	 * @param inputArray
	 * @param k
	 * @return ordered array of k minimum elements
	 * @throws Exception
	 */
	private static List> findKthMinimum(
			List> inputList, int k) throws Exception {
		List>> outputTree = getOutputTree(inputList);
		// printList(outputTree);
		return getKthMin(outputTree, k);
	}

	private static List> getKthMin(
			List>> outputTree, int k)
			throws Exception {
		int size = outputTree.size();
		if (k <= 0) {
			throw new IllegalArgumentException(
					"Please provide valid integer argument k [0," + size + ")");
		}

		List> orderedList = new LinkedList>();
		Node rootNode = outputTree.get(size - 1).get(0);
		orderedList.add(rootNode);
		if (k == 1) {
			return orderedList;
		}

		List> defeatedNodes = new LinkedList>();
		defeatedNodes.addAll(rootNode.getDefeatedNodesList());
		Node ithMinNode = rootNode;

		for (int i = 1; i < k; i++) {
			ithMinNode = getIthMinNode(defeatedNodes, ithMinNode);
			defeatedNodes.addAll(ithMinNode.getDefeatedNodesList());
		}

		Node kthMinNode = rootNode;
		for (int i = 1; i < k; i++) {
			kthMinNode = getIthMinNode(defeatedNodes, kthMinNode);
			orderedList.add(kthMinNode);
		}
		return orderedList;
	}

	private static Node getIthMinNode(
			List> defeatedNodes,
			Node iMinusOneTh) {
		Node ithMin = new KThMinimum2().new Node(
				Integer.MAX_VALUE, Integer.MAX_VALUE);
		for (Node n : defeatedNodes) {
			if (n.compareTo(iMinusOneTh) < 0) {
				continue;
			}
			if ((n.compareTo(iMinusOneTh) > 0) && (n.compareTo(ithMin) < 0)) {
				ithMin = n;
			}
		}
		return ithMin;
	}

	/**
	 * Takes an input array and generated a two-dimensional array whose rows are
	 * generated by comparing adjacent elements and selecting minimum of two
	 * elements. Thus the output is inverse triangle (root at bottom)
	 * 
	 * @param values
	 * @return
	 */
	public static List>> getOutputTree(
			List> inputList) {
		Integer size = new Integer(inputList.size());
		double treeDepth = Math.log(size.doubleValue()) / Math.log(2);
		int intTreeDepth = (int) (Math.ceil(treeDepth)) + 1;
		List>> outputTreeList = new ArrayList>>();

		// first row is the input
		outputTreeList.add(inputList);
		// printRow(inputList);

		List> currentRow = inputList;
		List> nextRow = null;
		for (int i = 1; i < intTreeDepth; i++) {
			nextRow = getNextRow(currentRow);
			// printRow(nextRow);
			outputTreeList.add(nextRow);
			currentRow = nextRow;
		}
		return outputTreeList;
	}

	/**
	 * Compares adjacent elements (starting from index 0), and construct a new
	 * array with elements that are smaller of the adjacent elements.
	 * 
	 * For even sized input, the resulting array is half the size, for odd size
	 * array, it is half + 1.
	 * 
	 * @param values
	 * @return
	 */
	private static List> getNextRow(
			List> values) {
		int rowSize = getNextRowSize(values);
		List> row = new ArrayList>(
				rowSize);
		int i = 0;
		for (int j = 0; j < values.size(); j++) {
			if (j == (values.size() - 1)) {
				// this is the case where there are odd number of elements
				// in the array. Hence the last loop will have only one element.
				// row[i++] = values.get(j);
				row.add(values.get(j));
			} else {
				row.add(getMin(values.get(j), values.get(++j)));
			}
		}
		return row;
	}

	/**
	 * Returns minimum of two passed in values.
	 * 
	 * @param num1
	 * @param num2
	 * @return
	 */
	private static Node getMin(Node node1,
			Node node2) {
		if (node1.compareTo(node2) < 0) {
			node1.addDefeatedNode(node2);
			return node1;
		} else {
			node2.addDefeatedNode(node1);
			return node2;
		}
	}

	/**
	 * following uses Math.ceil(double) to round to upper integer value..since
	 * this function takes double value, diving an int by double results in
	 * double.
	 * 
	 * Another way of achieving this is for number x divided by n would be -
	 * (x+n-1)/n
	 * 
	 * @param values
	 * @return
	 */
	private static int getNextRowSize(List> values) {
		return (int) Math.ceil(values.size() / 2.0);
	}

	private static void printRow(List> inputList) {
		for (Node n : inputList) {
			System.out.print(n.getKey() + " ");
		}
		System.out.println(" ");
	}

	private static void printList(List>> outputTree) {
		for (List> list : outputTree) {
			for (Node n : list) {
				System.out.print(n.getKey() + ": ");
				for (Node defeatedNode : n
						.getDefeatedNodesList()) {
					System.out.print(defeatedNode.getKey() + " ");
				}
				System.out.println("");
			}
		}
	}

	private static List> getNodeList(int[] input) {
		List> list = new ArrayList>();
		Node node = null;
		for (int i : input) {
			node = new KThMinimum2().new Node(i, i);
			list.add(node);
		}
		return list;
	}

	class Node, X> implements Comparable {
		private T key;
		private X value;
		private List> list = new LinkedList>();

		public Node(T key, X value) {
			super();
			this.key = key;
			this.value = value;
		}

		public void addDefeatedNode(Node node) {
			list.add(node);
		}

		public List> getDefeatedNodesList() {
			return list;
		}

		@Override
		public int compareTo(Object o) {
			Node other = (Node) o;
			return key.compareTo(other.getKey());
		}

		public T getKey() {
			return key;
		}

		public X getValue() {
			return value;
		}

		@Override
		public String toString() {
			return String.valueOf(key);
		}
	}
	
	public static void main(String args[]) throws Exception {
		int[] input = { 2, 14, 5, 13, 1, 8, 17, 10, 6, 12, 9, 4, 11, 15, 3, 16 };
		List> inputList = getNodeList(input);
		System.out.println("Fifth Minimum: " + getKthMinimum(inputList, 5));
		int minimumSortedElementSize = 10;
		List> tenMinimum = getMinimumKSortedElements(
				inputList, minimumSortedElementSize);
		System.out.print("Minimum " + minimumSortedElementSize + " Sorted: ");
		for (int i = 0; i < minimumSortedElementSize; i++) {
			System.out.print(tenMinimum.get(i) + " ");
		}
	}
}