Median of Medians Java implementation, kth element in array

Median of Median algorithm implementation in Java. It also provides Kth element in array after sorting. This algorithm runs in O(n) time.

Please leave comments below for more questions and remarks.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
 public static void main(String[] args) {
  Solution s = new Solution();
  List<Integer> a = Arrays.asList(88, 30, 11, 17, 22, 16, 39, 8, 31, 55,
    29, 63, 77, 69, 99, 90, 81, 2, 20, 53, 62, 5, 88, 33, 44, 6);
  System.out.println(s.findKthElement(a, 18));
  Collections.sort(a);
  System.out.println(a);
  System.out.println(a.get(18));
 }

 public int findKthElement(List<Integer> a, int k) {
  if (a.size() < 10) {
   Collections.sort(a);
   return a.get(k);
  }
  ArrayList<Integer> medians = new ArrayList<Integer>();
  for (int i = 0; i < a.size() - a.size() % 5; i = i + 5)
   medians.add(getMedian(a.subList(i, i + 5)));
  int v = getMedian(medians);

  ArrayList<Integer> left = getPartition(a, v, true);
  ArrayList<Integer> right = getPartition(a, v, false);

  return (left.size() + 1 == k) ? v : (left.size() > k) ? findKthElement(
    left, k) : findKthElement(right, k - left.size());
 }

 public int getMedian(List<Integer> a) {
  Collections.sort(a);
  return a.get(a.size() / 2);
 }

 public ArrayList<Integer> getPartition(List<Integer> a, int v,
   boolean isLessThan) {
  ArrayList<Integer> res = new ArrayList<Integer>();
  for (int val : a)
   if (isLessThan && val < v)
    res.add(val);
   else if (!isLessThan && val >= v)
    res.add(val);
  return res;
 }
}

Output:
62 ( value returned from algorithm)
[2, 5, 6, 8, 11, 16, 17, 20, 22, 29, 30, 31, 33, 39, 44, 53, 55, 62, 63, 69, 77, 81, 88, 88, 90, 99]
62 (kth value after sorting)

Arrangements/Combination of a elements in n positions

This method helps in arranging any type of objects in given number of positions. It is brut-force method of getting all type of combinations.

Please leave comments below for more questions and remarks.

public class Solution {
    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(1, 2);
        System.out.println(getArrangements(a, 4));
    }
    public static <T> List<List<T>> getArrangements
               (List<T> numbers, int n) {
        List<List<T>> result = new ArrayList<List<T>>();
        int itr = (int) Math.pow(n, numbers.size());
        for (int i = 0; i < itr; i++) {
            List<T> comb = new ArrayList<T>();
            for (int j = 0; j < n; j++) {
                int pos = (int) Math.pow(numbers.size(),
      (n - j - 1));
                int element = (i / pos) % (numbers.size());
                comb.add(numbers.get(element));
            }
            result.add(comb);
        }
        return result;
    }
}

Results:

Input1:[ 'A','B','C','D'] & 2 positions
output1: [[A, A], [A, B], [A, C], [A, D], [B, A], [B, B], [B, C], [B, D], [C, A], [C, B], [C, C], [C, D], [D, A], [D, B], [D, C], [D, D]]


Input2: [1,2] & 4 positions

[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 2, 2], [1, 2, 1, 1], [1, 2, 1, 2], [1, 2, 2, 1], [1, 2, 2, 2], [2, 1, 1, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 2, 2], [2, 2, 1, 1], [2, 2, 1, 2], [2, 2, 2, 1], [2, 2, 2, 2]]