Перебор с отсечением

живой пример

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Combinations {
    public static void main(String[] args) {
        int[] nominals = {5, 2, 3};
        Arrays.sort(nominals);
        List<List<Integer>> result = new ArrayList<>();
        walk(nominals, 0, 8, new ArrayDeque<>(), result);
        System.out.println(result);
    }

    static void walk(int[] nominals, int from, int rest, Deque<Integer> current, List<List<Integer>> result) {
        if (rest == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = from; i < nominals.length; i++) {
            if (nominals[i] > rest) break;
            current.addLast(nominals[i]);
            walk(nominals, i, rest - nominals[i], current, result);
            current.removeLast();
        }
    }
}

живой пример

package main

import (
	"fmt"
	"slices"
)

func walk(nominals []int, from, rest int, current []int, result *[][]int) {
	if rest == 0 {
		*result = append(*result, slices.Clone(current))
		return
	}
	for i := from; i < len(nominals); i++ {
		if nominals[i] > rest {
			break
		}
		current = append(current, nominals[i])
		walk(nominals, i, rest-nominals[i], current, result)
		current = current[:len(current)-1]
	}
}

func main() {
	nominals := []int{5, 2, 3}
	slices.Sort(nominals)
	var result [][]int
	walk(nominals, 0, 8, nil, &result)
	fmt.Println(result)
}

живой пример

function walk(nominals, from, rest, current, result) {
  if (rest === 0) {
    result.push([...current]);
    return;
  }
  for (let i = from; i < nominals.length; i++) {
    if (nominals[i] > rest) break;
    current.push(nominals[i]);
    walk(nominals, i, rest - nominals[i], current, result);
    current.pop();
  }
}

const nominals = [5, 2, 3].sort((a, b) => a - b);
const result = [];
walk(nominals, 0, 8, [], result);
console.log(JSON.stringify(result));

живой пример

def walk(nominals: list[int], start: int, rest: int, current: list[int], result: list[list[int]]) -> None:
    if rest == 0:
        result.append(current[:])
        return
    for i in range(start, len(nominals)):
        if nominals[i] > rest:
            break
        current.append(nominals[i])
        walk(nominals, i, rest - nominals[i], current, result)
        current.pop()


nominals = sorted([5, 2, 3])
result: list[list[int]] = []
walk(nominals, 0, 8, [], result)
print(result)

живой пример

import java.util.*;

public class Permutations {
    public static void main(String[] args) {
        String[] stops = {"склад", "офис", "клиент"};
        List<List<String>> routes = new ArrayList<>();
        walk(stops, new boolean[stops.length], new ArrayDeque<>(), routes);
        System.out.println(routes.size() + " маршрутов: " + routes);
    }

    static void walk(String[] stops, boolean[] used, Deque<String> current, List<List<String>> out) {
        if (current.size() == stops.length) {
            out.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < stops.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.addLast(stops[i]);
            walk(stops, used, current, out);
            current.removeLast();
            used[i] = false;
        }
    }
}

живой пример

package main

import (
	"fmt"
	"slices"
)

func walk(stops []string, used []bool, current []string, out *[][]string) {
	if len(current) == len(stops) {
		*out = append(*out, slices.Clone(current))
		return
	}
	for i := range stops {
		if used[i] {
			continue
		}
		used[i] = true
		current = append(current, stops[i])
		walk(stops, used, current, out)
		current = current[:len(current)-1]
		used[i] = false
	}
}

func main() {
	stops := []string{"склад", "офис", "клиент"}
	var routes [][]string
	walk(stops, make([]bool, len(stops)), nil, &routes)
	fmt.Println(len(routes), "маршрутов:", routes)
}

живой пример

function walk(stops, used, current, out) {
  if (current.length === stops.length) {
    out.push([...current]);
    return;
  }
  for (let i = 0; i < stops.length; i++) {
    if (used[i]) continue;
    used[i] = true;
    current.push(stops[i]);
    walk(stops, used, current, out);
    current.pop();
    used[i] = false;
  }
}

const stops = ["склад", "офис", "клиент"];
const routes = [];
walk(stops, new Array(stops.length).fill(false), [], routes);
console.log(`${routes.length} маршрутов: ${JSON.stringify(routes)}`);

В Python все перестановки без отсечений отдаёт готовый itertools.permutations(stops), а подмножества — itertools.combinations; перебор пишут руками, когда нужны отсечения. Руками он выглядит так:

живой пример

def walk(stops: list[str], used: list[bool], current: list[str], out: list[list[str]]) -> None:
    if len(current) == len(stops):
        out.append(current[:])
        return
    for i, stop in enumerate(stops):
        if used[i]:
            continue
        used[i] = True
        current.append(stop)
        walk(stops, used, current, out)
        current.pop()
        used[i] = False


stops = ["склад", "офис", "клиент"]
routes: list[list[str]] = []
walk(stops, [False] * len(stops), [], routes)
print(len(routes), "маршрутов:", routes)

живой пример

public class Queens {
    static int solutions;
    static int nodes;

    public static void main(String[] args) {
        place(new int[8], 0);
        System.out.println("расстановок: " + solutions);
        System.out.println("узлов дерева: " + nodes);
    }

    static void place(int[] column, int row) {
        nodes++;
        if (row == column.length) {
            solutions++;
            return;
        }
        for (int c = 0; c < column.length; c++) {
            if (safe(column, row, c)) {
                column[row] = c;
                place(column, row + 1);
            }
        }
    }

    static boolean safe(int[] column, int row, int c) {
        for (int r = 0; r < row; r++) {
            if (column[r] == c || Math.abs(column[r] - c) == row - r) return false;
        }
        return true;
    }
}

живой пример

package main

import "fmt"

var solutions, nodes int

func place(column []int, row int) {
	nodes++
	if row == len(column) {
		solutions++
		return
	}
	for c := 0; c < len(column); c++ {
		if safe(column, row, c) {
			column[row] = c
			place(column, row+1)
		}
	}
}

func safe(column []int, row, c int) bool {
	for r := 0; r < row; r++ {
		diff := column[r] - c
		if diff == 0 || diff == row-r || -diff == row-r {
			return false
		}
	}
	return true
}

func main() {
	place(make([]int, 8), 0)
	fmt.Println("расстановок:", solutions)
	fmt.Println("узлов дерева:", nodes)
}

живой пример

let solutions = 0;
let nodes = 0;

function place(column, row) {
  nodes++;
  if (row === column.length) {
    solutions++;
    return;
  }
  for (let c = 0; c < column.length; c++) {
    if (safe(column, row, c)) {
      column[row] = c;
      place(column, row + 1);
    }
  }
}

function safe(column, row, c) {
  for (let r = 0; r < row; r++) {
    if (column[r] === c || Math.abs(column[r] - c) === row - r) return false;
  }
  return true;
}

place(new Array(8).fill(0), 0);
console.log("расстановок:", solutions);
console.log("узлов дерева:", nodes);

живой пример

solutions = nodes = 0


def place(column: list[int], row: int) -> None:
    global solutions, nodes
    nodes += 1
    if row == len(column):
        solutions += 1
        return
    for c in range(len(column)):
        if safe(column, row, c):
            column[row] = c
            place(column, row + 1)


def safe(column: list[int], row: int, c: int) -> bool:
    for r in range(row):
        if column[r] == c or abs(column[r] - c) == row - r:
            return False
    return True


place([0] * 8, 0)
print("расстановок:", solutions)
print("узлов дерева:", nodes)

Самого перебора в стандартной библиотеке нет — это приём, а не структура. Зато всё его состояние держат готовые коллекции, и выбор класса виден в скорости напрямую: перебор повторяет одни и те же операции миллионы раз, и лишний O(n) внутри шага дорожает вместе со всем деревом.

Текущий набор в примере выше — ArrayDeque: внутри кольцевой массив, addLast и removeLast стоят амортизированно O(1), и обе операции отката попадают в один и тот же конец массива, то есть в горячий кэш. LinkedList умеет то же самое, но создаёт объект-узел на каждый добавленный элемент — на переборе это нагрузка на сборщик мусора и лишние промахи кэша.

Найденные ответы копят в ArrayList, и копия new ArrayList<>(current) стоит O(k) — отдельный массив под каждый набор. Отсюда вывод: память съедает не глубина рекурсии, а число сохранённых ответов; при миллионах ответов задача упрётся в память раньше, чем во время. Сортировка, ради которой номиналы упорядочивают, — обычный Arrays.sort по примитивам, O(N·log N) один раз перед спуском.

Грабля — в проверке «этот элемент уже занят». Соблазн спросить current.contains(x) у самого набора, но contains у списка и у ArrayDeque — линейный поиск за O(n) на каждом шаге дерева, тихо домножающий всю сложность перебора на длину набора. Для такой проверки берут boolean[] used при пронумерованных элементах или HashSet при любых других — там ответ за O(1). И ArrayDeque не принимает null — будет NullPointerException, так что «пустой ход» придётся обозначать явной заглушкой.

Самого перебора в стандартной библиотеке нет — это приём, а не структура. Зато всё его состояние держит срез, и то, как с ним обращаться, видно в скорости напрямую: перебор повторяет одни и те же операции миллионы раз, и лишний O(n) внутри шага дорожает вместе со всем деревом.

Текущий набор в примере выше — обычный срез: append кладёт в конец, current[:len(current)-1] откатывает, обе операции O(1) и попадают в один и тот же конец массива, то есть в горячий кеш. Есть тонкость: append внутри рекурсии может переехать в новый массив, и тогда у вызывающего и вызванного разные срезы. В примере это безопасно, потому что каждая ветка получает срез аргументом и откатывает только своё, но результат append всегда присваивают обратно.

Найденные ответы копят в [][]int, и копия slices.Clone(current) стоит O(k) — отдельный массив под каждый набор. Без копии все ответы смотрели бы в один общий массив и перезаписывали друг друга. Отсюда вывод: память съедает не глубина рекурсии, а число сохранённых ответов; при миллионах ответов задача упрётся в память раньше, чем во время. Сортировка, ради которой номиналы упорядочивают, — обычный slices.Sort, O(N·log N) один раз перед спуском.

Грабля — в проверке «этот элемент уже занят». Соблазн спросить slices.Contains(current, x) у самого набора, но это линейный поиск за O(n) на каждом шаге дерева, тихо домножающий всю сложность перебора на длину набора. Для такой проверки берут []bool при пронумерованных элементах или map[T]struct{} при любых других — там ответ за O(1). Глубина рекурсии в Go не ограничена жёстко, стек горутины растёт, поэтому перебор с глубиной в тысячи шагов проходит; но выигрыш от этого мнимый, дерево такой глубины всё равно не обойти за разумное время.

Самого перебора в стандартной библиотеке нет — это приём, а не структура. Зато всё его состояние держит обычный массив, и то, как с ним обращаться, видно в скорости напрямую: перебор повторяет одни и те же операции миллионы раз, и лишний O(n) внутри шага дорожает вместе со всем деревом.

Текущий набор в примере выше — массив: push кладёт в конец, pop откатывает, обе операции амортизированно O(1) и попадают в один и тот же конец массива, то есть в горячий кеш. Пока в массиве только числа или только строки, движок держит его плотно; смешивать типы в одном наборе не стоит.

Найденные ответы копят в массиве массивов, и копия [...current] стоит O(k) — отдельный массив под каждый набор. Без копии все ответы смотрели бы на один и тот же массив, который к концу перебора опустеет. Отсюда вывод: память съедает не глубина рекурсии, а число сохранённых ответов; при миллионах ответов задача упрётся в память раньше, чем во время, а куча Node по умолчанию ограничена. Сортировка, ради которой номиналы упорядочивают, — обычный sort с числовой функцией сравнения, O(N·log N) один раз перед спуском.

Грабля — в проверке «этот элемент уже занят». Соблазн спросить current.includes(x) у самого набора, но это линейный поиск за O(n) на каждом шаге дерева, тихо домножающий всю сложность перебора на длину набора. Для такой проверки берут массив used при пронумерованных элементах или Set при любых других — там ответ за O(1). Вторая грабля — глубина: рекурсия в V8 упирается в стек примерно на десяти тысячах вложенных вызовов, и перебор с очень глубоким деревом переписывают на явный стек.

Самого перебора с отсечением в стандартной библиотеке нет — это приём, а не структура. Зато перебор без отсечений там есть: itertools.combinations, permutations и product отдают все наборы, перестановки и сочетания лениво, и когда отсекать нечего, свой обход дерева не пишут. Состояние же своего перебора держит обычный list, и то, как с ним обращаться, видно в скорости напрямую: перебор повторяет одни и те же операции миллионы раз, и лишний O(n) внутри шага дорожает вместе со всем деревом.

Текущий набор в примере выше — список: append кладёт в конец, pop() откатывает, обе операции амортизированно O(1) и попадают в один и тот же конец массива, то есть в горячий кеш.

Найденные ответы копят в списке списков, и копия current[:] стоит O(k) — отдельный список под каждый набор. Без копии все ответы ссылались бы на один и тот же список, который к концу перебора опустеет. Отсюда вывод: память съедает не глубина рекурсии, а число сохранённых ответов; при миллионах ответов задача упрётся в память раньше, чем во время. Сортировка, ради которой номиналы упорядочивают, — обычный sorted, O(N·log N) один раз перед спуском.

Грабля — в проверке «этот элемент уже занят». Соблазн спросить x in current у самого набора, но для списка это линейный поиск за O(n) на каждом шаге дерева, тихо домножающий всю сложность перебора на длину набора. Для такой проверки берут список used при пронумерованных элементах или set при любых других — там ответ за O(1). Вторая грабля — глубина: предел рекурсии в Python тысяча вызовов, и дерево глубже сотен уровней переписывают на явный стек, хотя такое дерево всё равно не обойти за разумное время. И третья, на скорость: вызов функции в Python дорог, перебор из миллионов вызовов в десятки раз медленнее, чем в Go, и отсечения здесь не роскошь, а условие, при котором программа вообще дождётся ответа.