#include <vector>

using std::vector;

// Таак, тут будет крутое описание.
// Допустим у нас есть вектор их элементов
// {first, second, third, forth, fifth, sixt, seventh, eight, nine, tan}
// Тогда класс позволит получить все ветора,
// где каждый элемент находится в пределах n позиций от начального положения
//
// Т.е. Пример: {1, 2, 3}, position = 1
// Варианты: {1, 2, 3} {2, 1, 3} {1, 3, 2}
// Все символы сдвинулись не более чем на одну позицию от своего начального положения

template <class Type>
class BruteForce {
	vector<Type> _start;

	// Текущее состояние. Будет указывать на
	vector<Type> _state;

	// Дистанция, на которую можно сдвинуть каждый элемент
	size_t _maxDistance;

public:
	// Инициализируем начальное значение и текущее
	BruteForce(vector<Type> start, size_t distance) :
		_start(start), _state(start), _maxDistance(distance) {};

	vector<Type> get() {
		return _state;
	}

	bool checkPosition() {
		// На старте символ _start[i] был на i-той позиции
		// Ищем где он сейчас
		for (int i = 0; i < _start.size(); i++) {
			int pos = std::distance(_state.begin(), find(_state.begin(), _state.end(), _start[i]));
			int distance = std::abs(i - pos);
			if (distance > _maxDistance) return false;
		}
		return true;
	}

	// Формула для генерации перестановок
	// С проверкой на то, что каждый символ удален
	// от начального положения не дальше, чем на _position
    // @return false - если перестановки закончились
	bool next() {
		bool end;
		bool result = false;

		while (result == false) {
			end = nextStep();
			if (end == false) break;

			result = checkPosition();
		}
		return result;
		return true;
	}
	
	// Legacy code. Отправить на переработку в ад.
	bool nextStep() {
		int j = _start.size() - 2;
		while (j != -1 && _state[j] >= _state[j + 1]) j--;
		if (j == -1)
			return false; // больше перестановок нет
		int k = _start.size() - 1;
		while (_state[j] >= _state[k]) k--;
		std::swap(_state[j], _state[k]);
		int l = j + 1, r = _start.size() - 1; // сортируем оставшуюся часть последовательности
		while (l < r)
			std::swap(_state[l++], _state[r--]);
		return true;
	}
};



// ПРИЕМР
int main() {
	std::vector<int> arr = { 1, 2, 3, 4 };

	BruteForce<int> bf(arr, 2);

	while (bf.next()) {
		for (auto a : bf.get()) {
			std::cout << a << " ";
		}
		std::cout << std::endl;
	}
}

/**
 * На выходе получаем:
 * 1 2 4 3
 * 1 3 2 4
 * 1 3 4 2
 * 1 4 2 3
 * 1 4 3 2
 * 2 1 3 4
 * 2 1 4 3
 * 2 3 1 4
 * 2 4 1 3
 * 3 1 2 4
 * 3 1 4 2
 * 3 2 1 4
 * 3 4 1 2
 */