L7
Loki 75

Перебор на C++ с вложенными циклами

Пишу программу которая собирает головоломку. Головоломка относится к классу объемных упаковок, т. е. нужно собрать в коробочку размером 2*3*4, 8 деталей.

Каждая деталь состоит из двух целых кубов и двух половинок кубов. Каждая деталь имеет 24 вращения. (Пример детали смотрите на фото)

Я описал каждую деталь так: За целый куб взято число 13, а за половинки кубов числа от 1 до 12, таким образом что если совместить деталь с кодом 7 и кодом 6 (не вращая их соответственно) то получим целый куб, т. е. 13.

Описание детали:

int A1[3][3][3];

for(i=0;i<3;i++){
for(j=0;j<3;j++){
for(l=0;l<3;l++)
A1[j][l]=0;
A1[0][0][0]=13;
A1[0][0][1]=13;
A1[0][0][2]=1;
A1[0][1][0]=9;
}
}

Т. е. Взял трехмерный массив, заполнил его нулями, а потом поместил в него деталь. Для каждой детали 24 массива, т. е
А1,...А24,
В1,...В24,
С1,...С24,
D1,...D24,
E1,...E24,
F1,...F24,
G1,...G24,
H1,...H24.

После этого я создал массив который является этой коробочкой в которую будем укладывать детали.

Теперь мне нужно сделать перебор таким образом: например берем деталь A1, ставим ее на место в массиве [0][0][0], затем берем деталь В1 ставим ее на тоже место, если не противоречит условию что все элементы массива не больше 13, то берем С1 и ставим туда же, иначе сдвигаем ее на один вправо. Если после всех возможных сдвигов условие не срабатывает берем деталь А1 сдвигаем правее, и все повторяется, если так не срабатывает, берем деталь А2 и опять начинаем этот алгоритм. Подскажите- помогите организовать такой перебор.

Nikita
Nikita

http://cppalgo.blogspot.com/2011/02/episode-2.html
Часть 2. Генерация перестановок без повторений. Episode 2

[Все темы по перестановкам]

Теория:
1. Окулов. Программирование в алгоритмах. 2004.
2. Липский. Комбинаторика для программистов. 1988
3. Кнут. Том 4. Выпуск 2. Генерация всех кортежей и перестановок. 2008

Рассмотрим две задачи:
1) Генерация следующей перестановки в лексикографическом порядке
2) Генерация всех перестановок с помощью транспозиции двух соседних элементов.

В книге Липского описан алгоритм, генерирующий все перестановки с помощью транспозиций двух элементов (не обязательно соседних) .

Практика:
Как и в первой части будем решать задачу 2B-Перестановки

1) Генерация следующей перестановки в лексикографическом порядке (next_permutation).
Данный подход очень хорошо описан в книге Окулова, а также его подробное описание можно найти в книге Кнута (алгоритм L).

bool next_permutation(string &a) {

int j = n-2;
while (j!=-1 && a[j] > a[j+1]) j--;
if (j == -1)
return false; // a - last permutation
int k = n - 1;
while (a[j] > a[k]) k--;

swap(a[j],a[k]);

// reverse back [j+1, n-1]
int l = j + 1, r = n - 1;
while (l

Николай
Николай

А почему у вас куб - число 13? По моему не очень логичное число. Вершин у куба к примеру 8, итого 256 вариантов (часть даже не образует фигуры, но да ладно) . Берем, поворачиваем куб или другую фигуру во всех направлениях. Перебираем суммы, если итого 256 - образовался куб, фигуры можно сложить.

Похожие вопросы
как создать цикл для переменной в C#?
Программирование в C#, тема: Циклы
Почему вложенный цикл выполняется только один раз?
Как работает вложенный if в C++?
C++ Классы, вложенные классы
c sharp windows form работа с циклом и разветвлением
Pascal Дан текстовой файл (любой) найти все вложенные циклы while в тексте.
Как заработать в интернете без вложений? Как заработать в интернете без вложений?
C HDR перебор, или приемлемо выглядит? Thanks
Цикл For в C++ Как циклом for вывести на экран такой треугольник: * ** *** *** ***