1

Я взял алгоритм для перебора перестановок:

Генерация всех перестановок Основная идея алгоритма генерации всех перестановок заключается в следующем. В массиве длины n, содержащем перестановку, будем менять последний элемент с каждым, после чего будем рекурсивно будем делать то же самое для массива длины n-1 и затем возвращать переставленный элемент на старое место. Если достигнута длина массива n=1, то переставлять ничего не нужно, а следует выдавать содержимое всего массива-перестановки на экран. Такой алгоритм позволит сгенерировать все перестановки, что следует из словесного рекурсивного определения: на последнем месте побывает каждый элемент, содержащийся в рассматриваемом массиве, после чего к оставшейся части массива рекурсивно будет применен тот же алгоритм.

Написал код, взятый также из примера. Все работает, но хочу разобраться, как именно. Сложно понять, какая именно запущена функция Perm, порядок их действия. Например, в выводе хочется что-то вроде:

запуск 1, Perm_id 1

запуск 2, Perm_id 2

запуск 3, Perm_id 1

№ запуска посчитать могу, просто счетчик добавить, а с "ид" функции не пойму...

Сам код перестановок:

#include "stdafx.h"
#include <iostream>

using namespace std;
const int n = 4;
int arr[n] = { 1,2,3,4 };
int cnt = 0;    // счетчик

void swap(int *arr, int a, int b);
void printArr(int *arr);
void Perm(int *arr, int k);

int main() {
    Perm(arr, n);
    return 0;
}

void Perm(int *arr, int k) {
    if (k == 1) {
        printArr(arr);
        return;
    }
    else {
        for (int i = 0; i < k; i++) {
            swap(arr, i, k - 1);
            Perm(arr, k - 1);
            swap(arr, i, k - 1);
        }
    }
}
void swap(int *arr, int a, int b) {
    int s = arr[a];
    arr[a] = arr[b];
    arr[b] = s;
}

void printArr(int *arr) {
    cnt++;
    cout << cnt << ".\t";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
6
  • Я не вижу вопроса. Вы хотите разобраться, как работает код. Что Вам мешает это сделать непонятно. Что подразумевается под id функции также не ясно. 7 дек 2017 в 10:35
  • Возможно, вам поможет одна из следующих ссылок: * prog-cpp.ru/permutation * neerc.ifmo.ru/wiki/… * habrahabr.ru/post/248493 7 дек 2017 в 10:36
  • Хочу, чтобы каждый запуск рекурсивной функции сопровождался сообщением: я функция № 4. Да, разобраться как рекурсия, можно и без этого. Но почему вопрос не имеет места быть? Вопрос же не в том, как работает данная функция, а в том, как вывести в консоль порядок выполнения рекурсии. Такой вывод упростит понимание, да и проверить неплохо бы, правильно понял код или нет... Ну и спасибо вам за минус. 7 дек 2017 в 10:53
  • Что вы понимаете под номером функции? 7 дек 2017 в 12:12
  • функция запускает сама себя. Каждый новый ее запуск хочу идентифицировать, если это вообще возможно. То есть все, что именно этот конкретный запуск сделал вывести в консоль с уникальным номером этого запуска. 7 дек 2017 в 12:46

1 ответ 1

2

По сути, вы хотите построить дерево рекурсии. Почему это именно дерево. Довольно очевидно. Давайте условимся, что у нас при каждом новом вызове функции создаётся новая функция (т.е. не может дёрнуться предыдущая или какая-то следующая, которая будет вызвана когда-нибудь потом). Т.е. мы вызываем функцию здесь и сейчас и вызвана в другом месте она быть не может. При этом, без потери общности, будем говорить, что все вызываемые функции будут одинаковыми, т.е. последовательность действий (а точнее правила выполнения действий) в них не отличается друг от друга. Проиллюстрируем

Граф переходов между копиями функции1

Здесь синими стрелками показан выход из рекурсии. Красными -- заглубление по рекурсии. Если обратить внимание только на красные стрелки, то отчётливо проступит дерево. Этому можно дать строгое доказательство. Но думаю, что этого не требуется.

Теперь о том, как поступить в Вашем случае, чтобы понять, где в этом дереве мы находимся. Давайте всякий раз будем выводить на экран глубину рекурсии. В таком случае, мы сможем "примерно" понимать, где мы находимся. Если на каком-то этапе глубина рекурсии будет повторяться, то это означает, что мы зашли в другую ветку дерева рекурсии.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.