Оптимизация

Степень вершины

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

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

Для этого создадим два массива сумм:

Java

    // степени вершин
    static int[] sourceSum = new int[SIZE];
    static int[] targetSum = new int[SIZE];

C++

// степени вершин
int sourceSum[SIZE];
int targetSum[SIZE];

Python

// степени вершин
source_sum = [0 for i in range(SIZE)]
target_sum = [0 for i in range(SIZE)]

Заполним степени вершин:

Java

    // главный метод программы
    public static void main(String[] args) {
        // степени вершин
        for (int i = 0; i < SIZE; i++) {
            sourceSum[i] = 0;
            targetSum[i] = 0;
            for (int j = 0; j < SIZE; j++) {
                // в исходном представлении надо не забыть заменить веса единицей
                sourceSum[i] += Math.signum(source[i][j]);
                targetSum[i] += target[i][j];
            }
        }
        // запускаем генерацию перестановок
        permute(new int[]{0, 1, 2, 3, 4, 5, 6}, 0);
    }

C++

// главный метод программы
int main() {
    // степени вершин
    for (int i = 0; i < SIZE; i++) {
        sourceSum[i] = 0;
        targetSum[i] = 0;
        for (int j = 0; j < SIZE; j++) {
            // в исходном представлении надо не забыть заменить ненулевые веса единицей
            sourceSum[i] += source[i][j] > 0 ? 1 : 0;
            targetSum[i] += target[i][j];
        }
    }
    // запускаем генерацию перестановок
    permute(new int[]{0, 1, 2, 3, 4, 5, 6}, 0);

    return 0;
}

Python

# главный метод программы
if __name__ == '__main__':
    # рассчитываем взвешенные степени
    for i in range(SIZE):
        source_sum[i] = 0
        target_sum[i] = 0
        for j in range(SIZE):
            # в исходном представлении надо не забыть заменить ненулевые веса единицей
            source_sum[i] += 1 if source[i][j] > 0 else 0
            target_sum[i] += target[i][j]

    # запускаем генерацию перестановок
    permute([0, 1, 2, 3, 4, 5, 6], 0)

И в обработчике перестановки в самом начале добавим проверку на совпадение степеней вершин:

Java

    // обработка перестановки
    static void processPermutation(int[] arr) {
        // проверяем, что в представлениях совпадают степени вершин
        for (int i = 0; i < SIZE; i++) {
            if (sourceSum[arr[i]] != targetSum[i]) {
                return;
            }
        }
        ...

C++

// обработка перестановки
void processPermutation(const int arr[]) {
    // проверяем, что в представлениях совпадают степени вершин
    for (int i = 0; i < SIZE; i++) {
        if (sourceSum[arr[i]] != targetSum[i]) {
            return;
        }
    }
    ...

Python

# обработка перестановки
def process_permutation(arr):
    # проверяем, что в представлениях совпадают степени вершин
    for i in range(SIZE):
        if source_sum[arr[i]] != target_sum[i]:
            return
    ...

Весь код:

Java

public class Problem1 {

    // кол-во вершин (используется для удобства)
    static int SIZE = 7;

    // названия вер
    static char[] names = {'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж'};

    //      П1  П2  П3  П4  П5  П6  П7
    static int[][] source = new int[][]{
            {0, 10, 15,  0,  0,  0,  0}, // П1
            {10, 0,  0, 13, 17,  0,  0}, // П2
            {15, 0,  0,  0, 19,  0,  9}, // П3
            {0, 14,  0,  0, 10, 20, 11}, // П4
            {0, 17, 19, 10,  0,  0, 20}, // П5
            {0,  0,  0, 20,  0,  0, 25}, // П6
            {0,  0,  9, 11, 20, 25,  0}  // П7
    };
    //       А  Б  В  Г  Д  Е  Ж
    static int[][] target = new int[][]{
            {0, 1, 1, 0, 0, 0, 0}, // A
            {1, 0, 0, 1, 1, 0, 0}, // Б
            {1, 0, 0, 1, 0, 1, 0}, // В
            {0, 1, 1, 0, 1, 1, 0}, // Г
            {0, 1, 0, 1, 0, 1, 1}, // Д
            {0, 0, 1, 1, 1, 0, 1}, // Е
            {0, 0, 0, 0, 1, 1, 0}  // Ж
    };

    // степени вершин
    static int[] sourceSum = new int[SIZE];
    static int[] targetSum = new int[SIZE];

    // получить обратную перестановку
    static int[] getReversePermutation(int[] arr) {
        int[] reverse = new int[arr.length];
        for (int i = 0; i < SIZE; i++) {
            reverse[arr[i]] = i;
        }
        return reverse;
    }

    // обработка перестановки
    static void processPermutation(int[] arr) {
        // проверяем, что в представлениях совпадают степени вершин
        for (int i = 0; i < SIZE; i++) {
            if (sourceSum[arr[i]] != targetSum[i]) {
                return;
            }
        }

        // нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
        // обратятся в ноль
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                // если в эталонном представлении связь между вершинами есть,
                // а в данном в задании - нет
                if (target[i][j] > 0 && source[arr[i]][arr[j]] == 0)
                    // заканчиваем выполнение обработчика, потому такая перестановка
                    // создаёт представление, не совместимое с данным, а значит, нас не
                    // интересует
                    return;
            }
        }
        // здесь мы уже выполняем проверку, определённую заданием

        // расстояние между Г и Д
        int gdDistance = source[arr[3]][arr[4]];
        // расстояние между Г и Е
        int geDistance = source[arr[3]][arr[5]];
        // расстояние между А и Б
        int abDistance = source[arr[0]][arr[1]];
        // если расстояние ГД меньше ГЕ, то комбинация нам подходит
        if (gdDistance < geDistance) {
            // получаем обратную перестановку
            int [] reverse = getReversePermutation(arr);
            // выводим названия вершин
            for (int i = 0; i < SIZE; i++) {
                System.out.print(names[reverse[i]] + " ");
            }
            System.out.println();
            // выводим расстояния
            System.out.println(abDistance + " " + gdDistance + " " + geDistance);
        }

    }

    // функция-генератор перестановок
    static void permute(int[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == p.length - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < p.length; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // рассчитываем взвешенные степени
        for (int i = 0; i < SIZE; i++) {
            sourceSum[i] = 0;
            targetSum[i] = 0;
            for (int j = 0; j < SIZE; j++) {
                // в исходном представлении надо не забыть заменить веса единицей
                sourceSum[i] += Math.signum(source[i][j]);
                targetSum[i] += target[i][j];
            }
        }
        // запускаем генерацию перестановок
        permute(new int[]{0, 1, 2, 3, 4, 5, 6}, 0);
    }

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

}

C++

#include <iostream>

// кол-во вершин (используется для удобства)
const int SIZE = 7;

//      П1  П2  П3  П4  П5  П6  П7
const int source[SIZE][SIZE] = {
        {0,  10, 15, 0,  0,  0,  0}, // П1
        {10, 0,  0,  13, 17, 0,  0}, // П2
        {15, 0,  0,  0,  19, 0,  9}, // П3
        {0,  14, 0,  0,  10, 20, 11}, // П4
        {0,  17, 19, 10, 0,  0,  20}, // П5
        {0,  0,  0,  20, 0,  0,  25}, // П6
        {0,  0,  9,  11, 20, 25, 0}  // П7
};;

//       А  Б  В  Г  Д  Е  Ж
const int target[SIZE][SIZE] = {
        {0, 1, 1, 0, 0, 0, 0}, // A
        {1, 0, 0, 1, 1, 0, 0}, // Б
        {1, 0, 0, 1, 0, 1, 0}, // В
        {0, 1, 1, 0, 1, 1, 0}, // Г
        {0, 1, 0, 1, 0, 1, 1}, // Д
        {0, 0, 1, 1, 1, 0, 1}, // Е
        {0, 0, 0, 0, 1, 1, 0}  // Ж
};

// степени вершин
int sourceSum[SIZE];
int targetSum[SIZE];

// получить обратную перестановку
int *getReversePermutation(const int arr[]) {
    static int reverse[SIZE];
    for (int i = 0; i < SIZE; i++) {
        reverse[arr[i]] = i;
    }
    return reverse;
}

// обработка перестановки
void processPermutation(const int arr[]) {
    // проверяем, что в представлениях совпадают степени вершин
    for (int i = 0; i < SIZE; i++) {
        if (sourceSum[arr[i]] != targetSum[i]) {
            return;
        }
    }

    // нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
    // обратятся в ноль
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            // если в эталонном представлении связь между вершинами есть,
            // а в данном в задании - нет
            if (target[i][j] > 0 && source[arr[i]][arr[j]] == 0)
                // заканчиваем выполнение обработчика, потому такая перестановка
                // создаёт представление, не совместимое с данным, а значит, нас не
                // интересует
                return;
        }
    }
    // здесь мы уже выполняем проверку, определённую заданием

    // расстояние между Г и Д
    int gdDistance = source[arr[3]][arr[4]];
    // расстояние между Г и Е
    int geDistance = source[arr[3]][arr[5]];
    // расстояние между А и Б
    int abDistance = source[arr[0]][arr[1]];
    // если расстояние ГД меньше ГЕ, то комбинация нам подходит
    if (gdDistance < geDistance) {
        // получаем обратную перестановку
        int *reverse = getReversePermutation(arr);
        // названия вершин
        const std::string names[SIZE] = {"A", "B", "C", "D", "E", "F", "G"};
        // выводим названия вершин
        for (int i = 0; i < SIZE; i++) {
            std::cout << names[reverse[i]] << " ";
        }
        std::cout << std::endl;
        // выводим расстояния
        std::cout << abDistance << " " << gdDistance << " " << geDistance;
    }

}

// функция-генератор перестановок
void permute(int p[], int pos) {
    // Если мы дошли до последнего элемента
    if (pos == SIZE - 1) {
        processPermutation(p);
    } else { // иначе
        // Перебираем все оставшиеся элементы
        for (int i = pos; i < SIZE; i++) {
            // меняем местами текущий элемент и перебираемый
            swap(p, pos, i);
            // Вызываем Рекурсию для следующего элемента
            permute(p, pos + 1);
            // меняем местами обратно
            swap(p, pos, i);
        }
    }
}

// главный метод программы
int main() {
    // рассчитываем взвешенные степени
    for (int i = 0; i < SIZE; i++) {
        sourceSum[i] = 0;
        targetSum[i] = 0;
        for (int j = 0; j < SIZE; j++) {
            // в исходном представлении надо не забыть заменить ненулевые веса единицей
            sourceSum[i] += source[i][j] > 0 ? 1 : 0;
            targetSum[i] += target[i][j];
        }
    }
    // запускаем генерацию перестановок
    permute(new int[]{0, 1, 2, 3, 4, 5, 6}, 0);

    return 0;
}

Python

import itertools
# кол-во вершин (используется для удобства)
SIZE = 7

# названия вершин
names = ['А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж']

#   П1  П2  П3  П4  П5  П6  П7
source = [
    [0, 10, 15,  0,  0,  0,  0],  # П1
    [10, 0,  0, 13, 17,  0,  0],  # П2
    [15, 0,  0,  0, 19,  0,  9],  # П3
    [0, 14,  0,  0, 10, 20, 11],  # П4
    [0, 17, 19, 10,  0,  0, 20],  # П5
    [0,  0,  0, 20,  0,  0, 25],  # П6
    [0,  0,  9, 11, 20, 25,  0]  # П7
]
#    А  Б  В  Г  Д  Е  Ж
target = [
    [0, 1, 1, 0, 0, 0, 0],  # A
    [1, 0, 0, 1, 1, 0, 0],  # Б
    [1, 0, 0, 1, 0, 1, 0],  # В
    [0, 1, 1, 0, 1, 1, 0],  # Г
    [0, 1, 0, 1, 0, 1, 1],  # Д
    [0, 0, 1, 1, 1, 0, 1],  # Е
    [0, 0, 0, 0, 1, 1, 0]   # Ж
]

# степени вершин
source_sum = [0 for i in range(SIZE)]
target_sum = [0 for i in range(SIZE)]

# получить обратную перестановку
def getReversePermutation(arr):
    reverse = [0] * len(arr)
    for i in range(len(arr)):
        reverse[arr[i]] = i

    return reverse


# обработка перестановки
def process_permutation(arr):
    # проверяем, что в представлениях совпадают степени вершин
    for i in range(SIZE):
        if source_sum[arr[i]] != target_sum[i]:
            return

    # нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
    # обратятся в ноль
    for i in range(SIZE):
        for j in range(SIZE):
            # если в эталонном представлении связь между вершинами есть,
            # а в данном в задании - нет
            if target[i][j] > 0 and source[arr[i]][arr[j]] == 0:
                # заканчиваем выполнение обработчика, потому такая перестановка
                # создаёт представление, не совместимое с данным, а значит, нас не
                # интересует
                return

    # здесь мы уже выполняем проверку, определённую заданием

    # расстояние между Г и Д
    gd_distance = source[arr[3]][arr[4]]
    # расстояние между Г и Е
    ge_distance = source[arr[3]][arr[5]]
    # расстояние между А и Б
    ab_distance = source[arr[0]][arr[1]]
    # если расстояние ГД меньше ГЕ, то комбинация нам подходит
    if gd_distance < ge_distance:
        # формируем заголовок
        header = ""
        # получаем обратную перестановку
        reverse = getReversePermutation(arr)
        for i in range(SIZE):
            header += names[reverse[i]] + " "
        # выводим названия вершин
        print(header)
        # выводим расстояния
        print(ab_distance, gd_distance,  ge_distance)


# функция-генератор перестановок
def permute(p, pos):
    # Если мы дошли до последнего элемента
    if pos == SIZE - 1:
        process_permutation(p)
    else:  # иначе
        # Перебираем все оставшиеся элементы
        for i in range(pos, SIZE):
            # меняем местами текущий элемент и перебираемый
            p[pos], p[i] = p[i], p[pos]
            # Вызываем Рекурсию для следующего элемента
            permute(p, pos + 1)
            # меняем местами обратно
            p[pos], p[i] = p[i], p[pos]


# главный метод программы
if __name__ == '__main__':
    # рассчитываем взвешенные степени
    for i in range(SIZE):
        source_sum[i] = 0
        target_sum[i] = 0
        for j in range(SIZE):
            # в исходном представлении надо не забыть заменить ненулевые веса единицей
            source_sum[i] += 1 if source[i][j] > 0 else 0
            target_sum[i] += target[i][j]

    # запускаем генерацию перестановок
    permute([0, 1, 2, 3, 4, 5, 6], 0)

На выходе получим:

А Б В Д Г Ж Е
10 10 20

Ответ: 10

С++ оптимизация

В C++ есть готовый метод std::next_permutation(s.begin(),s.end()), который генерирует перестановки за нас, поэтому рекуррентный метод в C++ коде необязателен, мы можем заменить его вызов следующими командами:

    std::vector<int> origin = {0, 1, 2, 3, 4, 5, 6};
    do {
        processPermutation(origin);
    } while(std::next_permutation(origin.begin(), origin.end()));

Тогда весь код будет таким:

#include <iostream>
#include <bits/stdc++.h>

// кол-во вершин (используется для удобства)
const int SIZE = 7;

//      П1  П2  П3  П4  П5  П6  П7
const int source[SIZE][SIZE] = {
        {0,  10, 15, 0,  0,  0,  0}, // П1
        {10, 0,  0,  13, 17, 0,  0}, // П2
        {15, 0,  0,  0,  19, 0,  9}, // П3
        {0,  14, 0,  0,  10, 20, 11}, // П4
        {0,  17, 19, 10, 0,  0,  20}, // П5
        {0,  0,  0,  20, 0,  0,  25}, // П6
        {0,  0,  9,  11, 20, 25, 0}  // П7
};;

//       А  Б  В  Г  Д  Е  Ж
const int target[SIZE][SIZE] = {
        {0, 1, 1, 0, 0, 0, 0}, // A
        {1, 0, 0, 1, 1, 0, 0}, // Б
        {1, 0, 0, 1, 0, 1, 0}, // В
        {0, 1, 1, 0, 1, 1, 0}, // Г
        {0, 1, 0, 1, 0, 1, 1}, // Д
        {0, 0, 1, 1, 1, 0, 1}, // Е
        {0, 0, 0, 0, 1, 1, 0}  // Ж
};

// степени вершин
int sourceSum[SIZE];
int targetSum[SIZE];

// получить обратную перестановку
int *getReversePermutation(std::vector<int> arr) {
    static int reverse[SIZE];
    for (int i = 0; i < SIZE; i++) {
        reverse[arr[i]] = i;
    }
    return reverse;
}

// обработка перестановки
void processPermutation(std::vector<int> arr) {
    // проверяем, что в представлениях совпадают степени вершин
    for (int i = 0; i < SIZE; i++) {
        if (sourceSum[arr[i]] != targetSum[i]) {
            return;
        }
    }

    // нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
    // обратятся в ноль
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            // если в эталонном представлении связь между вершинами есть,
            // а в данном в задании - нет
            if (target[i][j] > 0 && source[arr[i]][arr[j]] == 0)
                // заканчиваем выполнение обработчика, потому такая перестановка
                // создаёт представление, не совместимое с данным, а значит, нас не
                // интересует
                return;
        }
    }
    // здесь мы уже выполняем проверку, определённую заданием

    // расстояние между Г и Д
    int gdDistance = source[arr[3]][arr[4]];
    // расстояние между Г и Е
    int geDistance = source[arr[3]][arr[5]];
    // расстояние между А и Б
    int abDistance = source[arr[0]][arr[1]];
    // если расстояние ГД меньше ГЕ, то комбинация нам подходит
    if (gdDistance < geDistance) {
        // получаем обратную перестановку
        int *reverse = getReversePermutation(arr);
        // названия вершин
        const std::string names[SIZE] = {"A", "B", "C", "D", "E", "F", "G"};
        // выводим названия вершин
        for (int i = 0; i < SIZE; i++) {
            std::cout << names[reverse[i]] << " ";
        }
        std::cout << std::endl;
        // выводим расстояния
        std::cout << abDistance << " " << gdDistance << " " << geDistance;
    }

}


// главный метод программы
int main() {
    // рассчитываем взвешенные степени
    for (int i = 0; i < SIZE; i++) {
        sourceSum[i] = 0;
        targetSum[i] = 0;
        for (int j = 0; j < SIZE; j++) {
            // в исходном представлении надо не забыть заменить ненулевые веса единицей
            sourceSum[i] += source[i][j] > 0 ? 1 : 0;
            targetSum[i] += target[i][j];
        }
    }

    std::vector<int> origin = {0, 1, 2, 3, 4, 5, 6};
    do {
        processPermutation(origin);
    } while(std::next_permutation(origin.begin(), origin.end()));

    return 0;
}

Python оптимизация

В Python тоже есть готовый метод, формирующий все перестановки itertools.permutations():

    permutations = list(itertools.permutations([0, 1, 2, 3, 4, 5, 6]))
    for permutation in permutations:
        process_permutation(permutation)

Тогда весь код будет таким:

import itertools
# кол-во вершин (используется для удобства)
SIZE = 7

# названия вершин
names = ['А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж']

#   П1  П2  П3  П4  П5  П6  П7
source = [
    [0, 10, 15,  0,  0,  0,  0],  # П1
    [10, 0,  0, 13, 17,  0,  0],  # П2
    [15, 0,  0,  0, 19,  0,  9],  # П3
    [0, 14,  0,  0, 10, 20, 11],  # П4
    [0, 17, 19, 10,  0,  0, 20],  # П5
    [0,  0,  0, 20,  0,  0, 25],  # П6
    [0,  0,  9, 11, 20, 25,  0]  # П7
]
#    А  Б  В  Г  Д  Е  Ж
target = [
    [0, 1, 1, 0, 0, 0, 0],  # A
    [1, 0, 0, 1, 1, 0, 0],  # Б
    [1, 0, 0, 1, 0, 1, 0],  # В
    [0, 1, 1, 0, 1, 1, 0],  # Г
    [0, 1, 0, 1, 0, 1, 1],  # Д
    [0, 0, 1, 1, 1, 0, 1],  # Е
    [0, 0, 0, 0, 1, 1, 0]   # Ж
]

# степени вершин
source_sum = [0 for i in range(SIZE)]
target_sum = [0 for i in range(SIZE)]

# получить обратную перестановку
def get_reverse_permutation(arr):
    reverse = [0] * len(arr)
    for i in range(len(arr)):
        reverse[arr[i]] = i

    return reverse

# обработка перестановки
def process_permutation(arr):
    print(arr)
    # проверяем, что в представлениях совпадают степени вершин
    for i in range(SIZE):
        if source_sum[arr[i]] != target_sum[i]:
            return

    # нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
    # обратятся в ноль
    for i in range(SIZE):
        for j in range(SIZE):
            # если в эталонном представлении связь между вершинами есть,
            # а в данном в задании - нет
            if target[i][j] > 0 and source[arr[i]][arr[j]] == 0:
                # заканчиваем выполнение обработчика, потому такая перестановка
                # создаёт представление, не совместимое с данным, а значит, нас не
                # интересует
                return

    # здесь мы уже выполняем проверку, определённую заданием

    # расстояние между Г и Д
    gd_distance = source[arr[3]][arr[4]]
    # расстояние между Г и Е
    ge_distance = source[arr[3]][arr[5]]
    # расстояние между А и Б
    ab_distance = source[arr[0]][arr[1]]
    # если расстояние ГД меньше ГЕ, то комбинация нам подходит
    if gd_distance < ge_distance:
        # формируем заголовок
        header = ""
        # получаем обратную перестановку
        reverse = get_reverse_permutation(arr)
        for i in range(SIZE):
            header += names[reverse[i]] + " "
        # выводим названия вершин
        print(header)
        # выводим расстояния
        print(ab_distance, gd_distance,  ge_distance)


# главный метод программы
if __name__ == '__main__':
    # рассчитываем взвешенные степени
    for i in range(SIZE):
        source_sum[i] = 0
        target_sum[i] = 0
        for j in range(SIZE):
            # в исходном представлении надо не забыть заменить ненулевые веса единицей
            source_sum[i] += 1 if source[i][j] > 0 else 0
            target_sum[i] += target[i][j]

    permutations = list(itertools.permutations([0, 1, 2, 3, 4, 5, 6]))
    for permutation in permutations:
        process_permutation(permutation)