Category Archive: Алгоритмы

Удаление числа из строки

Иногда мы пользуемся трюком, сохраняя числа (ID из базы данных) в строке через запятую.
Например: «1024,15,8,0,55».
И теперь, допустим, какое-то число из этого списка не нужно, и его необходимо убрать из исходной строки. Как это реализовать?

Первый вариант:
1) разбить строку по запятой
2) отфильтровать удаляемое число
3) собрать строку заново

Второй вариант (допустим, удаляем число 55):
1) вырезать из строки подстроки вида: ,55,
2) удаляем подстроки вида 55, и ,55

Реализация 1-го варианта (Java):

String val = "55";
String collect = Arrays.stream(
        "55,1024,55,15,8,0,55".split(","))
        .filter(v -> !v.equals(val))
        .collect(Collectors.joining(","));
System.out.println(collect);//1024,15,8,0

Реализация 2-го варианта (Java):

int del = 55;
String result = "55,1024,55,15,8,0,55"
        .replaceAll("," + del + ",", ",")
        .replaceAll(",?" + del + ",?", "");
System.out.println(result);//1024,15,8,0

Как искать ошибку в программе?

Список подсказок, как найти ошибку:

  1. Проверить, там ли вы ищите/смотрите ошибку.
    Например, вы могли подключиться не к тому серверу или базе.

  2. Вспомнить и посмотреть, что недавно менялось.
  3. Попросить коллегу посмотреть на проблему незамыленным взглядом
  4. Отстраниться от проблемы.
    Например, переключиться на другую сферу деятельности, проблему или просто отдохнуть

  5. Внимательно посмотреть сообщение об ошибке, может там уже указана точная причина ошибки или хотя бы указатель на нее
  6. Поискать способ (если возможно) просмотра детализованного лога
  7. Вернуться к первому пункту 🙂

Циклический сдвиг по кругу

Рассмотрим, линейный массив:
line
По нему мы можем передвигаться вперед и назад, но не выходя за левую и правую границы.
Данный массив можно закольцевать. Допустим, у нас есть массив, состоящий из элементов пронумерованных следующим образом: 0 1 2 3 4, мы находимся в позиции с индексом 3 и нам нужно сместиться на три позиции вправо. Наши действия:

  1. Перемещаемся вправо на 4-ю позицию;
  2. Пытаемся переместиться вправо на 5-ю позиции, но ее — нет. Перескакиваем на началом массива в 0-ю позицию;
  3. Перемещаемся вправо на 1-ю позицию. В итоге мы оказались на 1-й позиции.

Теперь рассмотрим обратную ситуацию. Мы в позиции с индекcом 1 и нужно сместиться на три позиции влево:

  1. Перемещаеся влево на 0-ю позицию;
  2. Пытаемся переместиться влево на -1-ю позицию, которой нет, поэтому перемещаемся в конец массива на позицию с индексом 4.
  3. Перемещаемся влево на 3-ю позицию. В итоге оказываемся на 3-й позиции.

circle
Реализация смещения вправо:

int[] arr = new int[]{10, 20, 30, 40, 50};
int index = 3;
System.out.println("index = " + index);//Вывод: 3
System.out.println("value = " + arr[index]);//Вывод: 40
int step = 3;
int newIndex = (index + step) % arr.length;
System.out.println("newIndex = " + newIndex);//Вывод: 1
System.out.println("value = " + arr[newIndex]);//Вывод: 20

Реализация смещения влево:

int[] arr = new int[]{10, 20, 30, 40, 50};
int index = 1;
System.out.println("index = " + index);//Вывод: 1
System.out.println("value = " + arr[index]);//Вывод: 20
int step = 13;
int newIndex = (arr.length + (index - step) % arr.length) % arr.length;
System.out.println("newIndex = " + newIndex);//Вывод: 3
System.out.println("value = " + arr[newIndex]);//Вывод: 40

Зацикливание массива реализовано с помощью операции взятия остатка от деления %, это позволяет исключить полностью завершенные циклы.

Вложенный тернарный поиск с золотым сечением

Определение тернарного поиска можно найти в Википедии. Также описание алгоритма можно найти здесь.
Реализация у тернарного поиска несложная, давайте убедимся в этом на примере следующей задачи:

triangle_find_alpha

Имеется прямоугольный треугольник, у которого гипотенуза равна 100 сантиметрам.
Нужно вычислить при каком угле α площадь треугольника будет максимальна.

Хотя данную задачу можно решать другими способами, но для учебных целей решим ее тернарным поиском.
Для начала нужно убедиться, что эту задачу вообще можно решить тернарным поиском. Убедимся в унимодальности нашей функции, т.е. на заданном интервале у функции должен быть один экстремум (максимальное или минимальное значение функции на заданном интервале).
Мы будем перебирать углы от 0° до 90°, т.е. наш интервал поиска от 0 до 90. При возрастании угла, начиная от 0°, площадь треугольника строго возрастает, затем при приближении к углу 90° площадь треугольнига строго уменьшается, т.е. у нас есть максимальное значение функции на данном интервале, а значит выполняется унимодальность функции, и мы можем применить тернарный поиск.
Как работает тернарный поиск.
Сначала интервал разбивается на три части, отсюда и название «тернарный» (Ternary переводится как тройной или троичный). На следующем шаге отсеивается участок, в котором точно нет решения, затем снова отрезок разбивается на три части, и это повторяется до тех пор, пока не будет достугнута необходимая точность результата.
Классический способ разбиения — это разбиение на три равные части части:
ternary_equal
Фрагмент кода, обеспечивающий равенство отрезков Lm1 = m1m2 = m2R:

double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;

При сравнении значений функций в точках m1 и m2 у нас возможно три варианта:
1) Мы сдвигаем область поиска вправо, т.е. l становится равным m1 (l = m1);
2) Мы сдвигаем область поиска влево, т.е. r становится равным m2 (r = m2);
3) При равенстве значений функции в обеих точках, мы сдвигаем область поиска с обеих сторон, т.е. l становиться равным m1 (l = m1), а r становиться равным m2 (r = m2)

Рассмотрим данные случаи на примере поиска максимального значения.
1) Если f(m1) < f(m2), возможно два случая: когда максимальное значение лежит в центральной части или в правой части, а значит левую часть можно отбросить. Максимальное значение обозначено зеленой точкой.
ternary_max_large
2) Если f(m1) > f(m2), аналогично имеется только два случая, когда максимальное значение лежит в центральной или левой части, а значит правую часть можно отбросить.
ternary_max_less
3) Если f(m1) = f(m2), то возможен только один вариант, при котором максимальное значение находится в центральной части, а значит левую и правую части можно отбросить.
ternary_max_equal
Последний вариант, когда f(m1) = f(m2), в целях облегчения алгоритма можно заменить либо на этот случай f(m1) < f(m2), либо на этот f(m1) > f(m2). В скорости из-за этого, конечно же, мы чуть-чуть проиграем, но выиграем в скорости реализации алгоритма и компактности кода.
После каждого шага алгоритма от исходной области поиска остается 2/3, т.е. не самая большая скорость сходимости. Можно повысить скорость сходимости, если выбирать точки m1 и m2 ближе друг другу, правда при этом теряется точность. Повышение скорости сходимости может потребоваться в случае, когда вычисление функции f(x) занимает много времени и нужно минимизировать кол-во вызовов этой функции.
Очень хорошо при выборе точек m1 и m2 воспользоваться пропорциями золотого сечения. Если тернарный поиск использует пропорции золотого сечения, то это один в один Метод золотого сечения.


Золотое сечение — это такое разбиение целого на две части, при котором отношение большего к меньшему равно отношению целого к большему


Это отношение постоянно и равно примерно 1,618, обозначается как φ и называется золотым числом:
phi
Для вычисления точек m1 и m2, разбивающих область поиска золотым сечением, воспользуемся следующими формулами:
m1_phi

m2_phi

В процентном соотношении длины отрезков lm1 и lm2 приблизительно равны 38,2% и 61,8% от длины отрезка lr.
Благодаря свойствам золотого сечения точка m1 делит отрезок lm2 в пропорциях золотого сечения, а точка m2 делит отрезок m1r также в пропорциях золотого сечения.
golden_section_search
И так мы видим, что сходимость золотого сечения будет 0,618, что лучше сходимости в случае разбиения области поиска на равные части, где сходимость у нас была 2/3 (0,66).
А теперь вернемся к решению задачи… Исходный код решения задачи на Java:

import static java.lang.Math.*;
 
public class angle {
 
	public static void main(String[] args) {
		double l = 0;
		double r = 90;
		double EPS = 1e-6;//точность 0.000001
		double hypo = 100;//гипотенуза
		while(r - l >= EPS){//повторяем цикл пока не достигнем требуемой точности
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(hypo,m1) < f(hypo,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		System.out.println((l + r) / 2);//результат 44.99999993498489
	}
 
	//функция расчета площади треугольника по гипотенузе и углу
	static double f(double hypo,double alpha){
		alpha = toRadians(alpha);
		return 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
	}
 
}

Т.е. при угле в 44.999999° (45°) достигается максимальная площадь треугольника. В качестве ответа можно было взять значение из переменной l или r, это возможно благодаря достижению заданной точности результата, также можно взять их середину (l + r) / 2, как в рассмотренном выше коде.

Задача на вложенный тернарный поиск
В качестве примера применения вложенного тернарного поиска возьмем задачу «Футбольные ворота». С условием задачи можно ознакомиться здесь или здесь.
Найти максимальную площадь ворот можно, подобрав углы для палок α и β:
football_gate
Сперва мы находим углы α1 и α2, которые разбивают область поиска на три равные части (в данной задачи можно не использовать золотое сечение). Далее для угла α1 с помощью вложенного тернарного поиска ищем угол β1, при котором площадь фигуры максимальна, аналогично, для угла α2 находим подходящий угол β2.
alpha_beta
Найдя пары углов α1 и β1; α2 и β2, вычисляем площадь S1 и S2 соответственно. Можно использовать следующую формулу вычисления площади, где a и b — длины палок:

S = 0.5 * a * a * cos(alpha) * sin(alpha) +
0.5 * b * b * cos(beta) * sin(beta) +
a * b * sin(alpha) * cos(beta)

Сравнив полученные площади, мы можем отсеять треть диапазона углов, которые дают маленькую площадь. И повторяем эти шаги до тех пор, пока не достигнем требуемой точности.
Код решения задачи на Java:

import java.io.*;
 
import static java.lang.Math.*;
 
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.*;
public class FooballGate {
 
	static int a;//длина 1-ой палки
	static int b;//длина 2-ой палки
	static double EPS = 1e-6;//точность результата
 
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new File("input.txt"));
		s.useLocale(Locale.US);		
		a = s.nextInt();
		b = s.nextInt();
		s.close();
 
		double l = 0;
		double r = 90;
 
		while(r - l >= EPS){
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(m1) < f(m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
 
		double ans = f((l + r) / 2);//результат		
		DecimalFormat df = new DecimalFormat("0.00000000",
				DecimalFormatSymbols.getInstance(Locale.US));
		System.out.println(df.format(ans));//вывод с восемью знаками после запятой
 
	}
 
 
	//функция расчета площади с фиксированным углом alpha,
	//в которой тернарным поиском идет поиск угла beta,
	//при котором площадь максимальна
	static double f(double alpha){
		double l = 0;
		double r = 90;
		while(r - l >= EPS){
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(alpha,l) < f(alpha,r)){
				l = m1;
			}else{
				r = m2;
			}
		}	
		return f(alpha,(l + r) / 2);
	}
 
	//функция расчета площади в зависимости от углов: alpha и beta 
	static double f(double alpha, double beta){
		alpha = toRadians(alpha);
		beta = toRadians(beta);
		return 0.5 * a * a * cos(alpha) * sin(alpha) +
				0.5 * b * b * cos(beta) * sin(beta) +
				a * b * sin(alpha) * cos(beta);
	}
}

Задача на тройную вложенность тернарного поиска с необходимостью применения золотого сечения
Задача называется «Космические спасатели». Ознакомиться с условием задачи можно здесь или здесь.
planets
По условию задачи нам нужно вычислить координаты x,y,z строительства новой спасательной станции, причем расстояние от станции до самой дальней планеты должно быть минимально.
Сперва пробуем подобрать координату x тернарным поиском, но координаты y и z — неизвестны, поэтому зафиксировав некоторые точки x, полученные золотым сечением, мы запускаем вложенные тернарный поиск с фиксированной координатой x для поиска координаты y. Далее внутри поиска y запускаем вложенный тернарный поиск координаты z. Когда мы имеем все три зафиксированные координаты мы можем посчитать расстояния до всех планет и из них определить максимальное расстояние, это расстояние и будет значением функции f(x,y,z).
Т.к. в условии сказано, что количество планет может быть 100, то вычисление функции f(x,y,z) очень затратно по времени. Чтобы программа уложилась во временные рамки, нужно при тернарном поиске разбивать область поиска золотым сечением, а не на равные части. Тем самым у нас повыситься сходимость, т.е. вызовов функции f(x,y,z) станет меньше. Но при золотом сечении теряется точность, поэтому мы увеличим точность с 10-6 до 10-7.
Реализация на Java:

import java.io.*;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.*;
public class SpaceRescuers {
	static int MAX = (int) 1e4;//максимальная граница поиска
	static int MIN = -MAX;//минимальная граница поиска
	static class Point{
		int x;
		int y;
		int z;
		public Point(int x, int y, int z) {
			super();
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
 
	static class PointD{
		double x;
		double y;
		double z;
		public PointD(double x, double y, double z) {
			super();
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
	}
 
	static Point[] points;
	static double EPS = 1e-7;
	static PointD bestPoint;//лучшая точка
	static double best = Double.MAX_VALUE;//лучшее расстояние (минимальное)
	static double fi = 1 / ((Math.sqrt(5) + 1) / 2);
 
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new File("input.txt"));
		s.useLocale(Locale.US);
		int N = s.nextInt();
		points = new Point[N];
		for(int i = 0; i < N; i++){
			points[i] = new Point(s.nextInt(),s.nextInt(),s.nextInt());
		}
		s.close();
 
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(m1) > f(m2)){
				l = m1;
			}else{
				r = m2;
			}
		}		
		double x = bestPoint.x;
		double y = bestPoint.y;
		double z = bestPoint.z;
		DecimalFormat df = new DecimalFormat("0.000000", 
			DecimalFormatSymbols.getInstance(Locale.US));
		System.out.println(df.format(x) + " " + df.format(y) + " " + 
			df.format(z));
	}
 
	//опредение минимального расстояния при фиксированной координате x
	static double f(double x){
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(x,m1) > f(x,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		return f(x,(l + r) / 2);
	}
 
	//определение минимального расстояния при фиксированных координатах x и y
	static double f(double x,double y){
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(x,y,m1) > f(x,y,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		return f(x,y,(l + r) / 2);
	}
 
	//определение минимального расстояния при фиксированных координатах x,y и z
	static double f(double x,double y,double z){
		double max = 0;
		for(int i = 0; i < points.length; i++){
			Point p = points[i];			
			double s = 
					(p.x - x) * (p.x - x) + 
					(p.y - y) * (p.y - y) + 
					(p.z - z) * (p.z - z);
			max = Math.max(max, s);
		}
		if(max < best){
			best = max;
			bestPoint = new PointD(x,y,z);
		}
		return max;
	}
 
}

Обратите внимание на некоторые места в коде:

  1. Мы рассчитываем не φ, а 1/φ, чтобы дальше в вычислениях использовать умножение, а не деление, т.к. умножение работает быстрее;
    static double fi = 1 / ((Math.sqrt(5) + 1) / 2);
    double delta = (r - l) * fi;
    double m1 = r - delta;
    double m2 = l + delta;
  2. В первых двух задачах мы рассматривали поиск максимального значения, а данной задаче нас интересует минимально значение, поэтому в условном операторе меняется условие:
    if(f(m1) > f(m2)){
    	l = m1;
    }else{
    	r = m2;
    }
  3. Обратите внимание, что при расчете расстояния извлечение квадратного корня опущено.
    double s = 
    	(p.x - x) * (p.x - x) + 
    	(p.y - y) * (p.y - y) + 
    	(p.z - z) * (p.z - z);

    Извлечение квадратног корня — очень затратная операция. Сравнивать расстояния можно и без извлечения корня, а если бы потребовалось узнать самое минимальное расстояние, то корень можно было бы извлечь в самом конце.

Сортировка кучей (GCC 4.9.1)

Реализация на GCC 4.9.1 сортировки кучей (пирамидальная сортировка).
У сортировки кучей два больших достоинства:

  1. В худшем случае работает за O(n * log n)
  2. Не требует дополнительной памяти

Реализация:

#include<stdio.h>
//получить индекс левого потомка
int left(int i){
	return i * 2 + 1;
}
 
//получить индекс правого потомка
int right(int i){
	return i * 2 + 2;
}
 
//поменять местами два элемента массива
int swap(int *a,int i,int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}
 
//вывести на экран массив
void print(int *a,int size){
	int i;
	for(i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
}
 
//переупорядочивание поддерева
void heapify(int *a,int size,int i){
	int l = left(i);
	int r = right(i);
	int largest = i;
	if(l < size && a[i] < a[l]){
		largest = l;
	}
	if(r < size && a[largest] < a[r]){
		largest = r;
	}
	if(i != largest){
		swap(a,i,largest);
		heapify(a,size,largest);
	}
}
 
//постройка кучи
void buildHeap(int *a,int size){
	int i;
	for(i=size/2 - 1;i>=0;i--){
		heapify(a,size,i);
	}
}
 
//сортировка кучей
void heapSort(int *a,int size){
	buildHeap(a,size);
//	printf("build\n");
//	print(a,size);
	while(--size > 0){
		swap(a,0,size);
		heapify(a,size,0);		
	}
}
 
int main(){	
	const int N = 9;
	int arr[9] = {1,6,3,5,9,4,2,8,7};
	print(arr,N);//вывести на экран исходный массив
	heapSort(arr,N);//сортировка кучей
	printf("=============\n");
	print(arr,N);//вывод отсортированного массива	
	return 0;
}

В результате исходный массив (1 6 3 5 9 4 2 8 7) будет отсортирован (1 2 3 4 5 6 7 8 9).

Перебор всех возможных вариантов

В данной статье будет рассмотрено два алгоритма перебора всех возможных вариантов.

Для начала придумаем задачу, на примере которой будем рассматривать алгоритмы.
Пусть у нас имеется множество S, состоящее из 4-х элементов: * + /, и наша задача — перебрать все возможные комбинации из 3-х элементов, используя элементы множества S. Причем, выбираемые элементы могут повторяться. Например: «+*+».

Первый алгоритм

Сопоставим каждому элементу число, начиная с 0.
* — 0
— 1
+ — 2
/ — 3

Можно догадаться, что нужно перебрать элементы от 0 0 0 до 3 3 3:
0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 0 1


3 2 3
3 3 0
3 3 1
3 3 2
3 3 3

Всего получится 64 варианта (4 * 4 * 4 = 64)

Далее нужно провести обратную операцию, сопоставив числу элемент множества S.
Например, набору 2 0 2 соответствует +*+

В алгоритме мы будем имитировать сложение в столбик, каждый раз прибавляя единицу, чтобы получить новый вариант.

Реализация:

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов
int size = 3;//кол-во элементов
int arr[] = new int[size];//массив для хранения текущего варианта множества
outer: while(true){//вечный цикл
 
	//вывод варианта множества на экран
	for(int ndx : arr){
		System.out.print(abc[ndx]);
	}
	System.out.println();
 
	int i = size - 1;//ставим курсов в самую правую ячейку
	while(arr[i] == abc.length - 1){//движемся влево, если ячейка переполнена
		arr[i] = 0;//записываем в ячейку 0, т.к. идет перенос разряда
		i--;//сдвиг влево
		//если перенос влево невозможен, значит перебор закончен
		if(i < 0)break outer;
	}
	arr[i]++;//увеличиваем значение ячейки на единицу
}

В результате программа выведет все 64 варианта:

***
**-
**+
**/
*-*
*--
...
...
/++
/+/
//*
//-
//+
///

Второй алгоритм
Для начала посчитаем сколько всего возможных комбинаций, это число равно n ^ k, где n — это размер алфавита (кол-во допустимых символов), а k — кол-во элементов в комбинации.
Для нашего множества S, состоящего из *,,+ и /, n равно 4. И т.к. нужно перебрать все комбинации из трех элементов, то k равно 3.
Получаем: n ^ k = 4 ^ 3 = 64.
В итоге мы должны получить 64 комбинации.
Вот если бы существовал способ преобразования номера комбинации в элементы комбинации.
И такой способ существует: для этого нужно номер комбинации преобразовать в k-значное число в системе счисления по основанию n.
Первой комбинации будет соответствовать число 0, а последней 63.
Перебирая числа от 0 до 63, нам нужно каждое число преобразовать в число в систему счисления по основанию 4. Для получения разрядов числа нужно целочисленно разделить число на 1, 4, 16 (т.е. n^0, n^1, n^2) и результат взять по модулю n.
Пример: для числа 57 при k = 3 и n = 4
(57 / 1) % 4 = 57 % 4 = 1 (-)
(57 / 4) % 4 = 14 % 4 = 2 (+)
(57 / 16) % 4 = 3 % 4 = 3 (/)
Т.е. комбинации под номером 57 соответствует комбинация -+/

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов (алфавит)
int N = abc.length;//N - размер алфавита
int K = 3;//кол-во элементов в комбинации
 
int pow[] = new int[K + 1];//массив для степеней числа N: N^0, N^1, .., N^K   
pow[0] = 1;
for (int i = 1; i <= K; i++) {//вычисляем степени числа N
	pow[i] = pow[i - 1] * N
}
 
//перебираем все номера комбинаций
for (int i = 0; i < pow[K]; i++) {
	char arr[] = new char[K];
	//вычисляем элементы комбинации
	for (int j = 0; j < K; j++) {
		//каждый элемент получаем из массива abc по индексу,
		//индекс - это число в системе счисления по основанию N (0..N-1)
		//в соответствующем разряде j (от 0 до K-1 включительно)
		arr[j] = abc[(i / pow[j]) % N];
	}
	//вывод в консоль
	for(char ch : arr){
		System.out.print(ch);
	}
	System.out.println();
}

Вывод программы:

0 ***
1 -**
2 +**
3 /**
4 *-*
.....
57 -+/
58 ++/
59 /+/
60 *//
61 -//
62 +//
63 ///

В данном алгоритме перебор идет как бы слева направо, но это не важно, т.к. мы перебираем все комбинации.

Перебор всех подмножеств заданного множества (Java)

Пусть дано множество, состоящее из четырех элементов: {a,b,c,d}.
Необходимо перебрать все возможные подмножества данного множества:
1) {} — пустое множество
2) {a}
3) {b}
4) {a,b}
5) {c}
6) {a,c}
7) {b,c}
8) {a,b,c}
9) {d}
10) {a,d}
11) {b,d}
12) {a,b,d}
13) {c,d}
14) {a,c,d}
15) {b,c,d}
16) {a,b,c,d}

Причем подмножества {a,b} и {b,a} считаются одним и тем же подмножеством.

Данную задачу будем решать с использованием битовых масок и битовых операций.
Сразу приведу реализацию:

char arr[] = new char[]{'a','b','c','d'};
int N = arr.length;
for (int mask = 0; mask < (1 << N); mask++) {//перебор масок			
	for (int j = 0; j < N; j++) {//перебор индексов массива
		if((mask & (1 << j)) != 0){//поиск индекса в маске
			System.out.print(arr[j] + " ");//вывод элемента
		}
	}
	System.out.println();//перевод строки для вывод следующего подмножества
}

А теперь пояснения.
1 << N — побитовый сдвиг единицы на N позиций влево.
В двоичном виде единица выглядит так 00000001. В нашем случае N = 4.
После сдвига на 4 позиции влево появится новое число, двоичный вид которого 00010000. Теперь, если вычесть из этого числа единицу получим: 00001111. Если опустить ведущие нули, то получим 1111. Четыре единицы — это состояние, когда в подмножество попадают все элементы, 0000 — пустое множество, 1010 — подмножество состоит из первого и третьего элемента множества (нумерация с нуля, отсчет ведется справа) и т.д.
Т.е. мы перебираем числа, двоичное представление которых от 0000 до 1111.

После того как мы получили маску (mask), необходимо узнать в каких позициях стоят единицы. Проверять будем следующим образом.
Например, на каком-то шаге цикла программы маска равна 1100, мы перебираем все позиции путем сдвига единицы: 0001, 0010, 0100 и 1000. Для проверки воспользуемся операцией побитового И (если в одинаковых позициях стоят единицы, то результат единица, иначе ноль). В Java обозначается как &
В нашем случае:
1100 & 0001 = 0000
1100 & 0010 = 0000
1100 & 0100 = 0100
1100 & 1000 = 1000
Т.е. если в итоге получилось число отличное от нуля, то включаем элемент в множество.
0100 — включаем в множество элемент с индексом 2
1000 — включаем в множество элемент с индексом 3
Нумерация с нуля и справа.
Результат работы программы (первая строка пустая — это пустое множество):


a 
b 
a b 
c 
a c 
b c 
a b c 
d 
a d 
b d 
a b d 
c d 
a c d 
b c d 
a b c d 

В данной реализации мы хранили маски в типе int.
(1 << 30) равно 1 073 741 824 Безопасное значение N для типа int: 30. Свыше 30 будет переполнение переменных типа int, поэтому нужно использовать long.
При N > 30 перебор будет ощутимо все медленнее и медленнее.

Если будете делать реализацию с long, то при сдвиге единицы нужно писать так:

1L << j

Т.е. нужно к единице приписать L, и тогда результат операции будет long, в противном случае будет int с переполнением.

НОК и НОД (lcm и gcd) на Java

НОД (Наибольший общий делитель) или gcd (Greatest Common Divisor)
НОД — наибольшее число, которое является делителем одновременно для чисел a и b.
Реализация (Алгоритм Евклида):

long gcd(long a,long b){
	return b == 0 ? a : gcd(b,a % b);		
}

Применение:

System.out.println(gcd(10,24));//результат: 2
System.out.println(gcd(12,24));//результат: 12
System.out.println(gcd(11,24));//результат: 1

НОК (Наименьшее общее кратное) или lcm (Least Common Multiple)
НОК — наименьшее число, которое делится на a и b без остатка.
НОК можно найти через НОД по следующей формуле:
нок
Реализация:

long lcm(long a,long b){
	return a / gcd(a,b) * b;
}

Примечание: a / gcd(a,b) * b более предпочтительно, чем a * b / gcd(a,b), т.к. во втором случае при больших числах переполнение случиться намного раньше.
Применение:

System.out.println(lcm(3, 4));//результат: 12
System.out.println(lcm(3, 9));//результат: 9
System.out.println(lcm(5,12));//результат: 60