c - 如何更改嵌套 for 循环中的行索引和列索引？

Question

我正在尝试计算出这座城市的最短距离。我已经有了一个起点，城市“0”，然后我们将访问每一个城市，而不会重新访问前一个城市。这样的话，我们就不需要回到0号城市了。

假设我们有 4 个城市，那么我们将有一个包含距离的矩阵。我想做的是迭代每条可能的路线并获取每条路线的成本。

所以城市号为 4 的所有可能路线是

city[0][1] + city[1][2] + city[2][3] 
city[0][1] + city[1][3] + city[3][2] 

city[0][2] + city[2][1] + city[1][3] 
city[0][2] + city[2][3] + city[3][1] 

city[0][3] + city[3][1] + city[1][2] 
city[0][3] + city[3][2] + city[2][1] 

我的问题是如何为这些方程制作嵌套 for 循环？我可以看到有一种模式，“列索引”应该转到下一个“行索引”，依此类推。

Answer 1

您正在寻找第一个城市固定的所有城市的排列。如果城市数量固定，您可以编写多个嵌套的 for 循环，但这很快就会变得很麻烦。

相反，递归地排列数组:

• 创建一个包含访问城市顺序的数组path；以 {0, ..., N - 1} 开头。
• 选择一个起始索引。如果您想要所有可能的起始品脱，请选择 0。在这里，第一个城市是固定的，因此从索引 1 开始，因为 path[1] 是第一个应该更改的条目。
• 调用排列函数:
  • 现在，如果仍有城市需要排列，则依次将每个城市交换到下一个位置，使用下一个索引调用排列函数，然后将城市交换回来。当你递归时，记录当前的距离。
  • 如果没有更多城市，则您已到达列表末尾。打印路径和距离或者任何你想做的事情，不要做任何其他事情。

代码如下:

#include <stdlib.h>
#include <stdio.h>

enum {
    N = 4           // number of cities
};

const int city[N][N] = {
    {0, 2, 5, 5},
    {2, 0, 3, 4},
    {5, 3, 0, 6},
    {5, 4, 6, 0},
};

/*
 *      Swap array elements at indices i and j
 */
void swap(int a[], int i, int j)
{
    if (i != j) {
        int swap = a[i]; a[i] = a[j]; a[j] = swap;
    }
}

/*
 *      Permute the subarray of length n, starting at index i
 */
void perm(int path[], int i, int n, int weight)
{
    int j;

    if (i == n) {                                   // path is exhausted:
        for (j = 0; j < n; j++) {                   // print path and distance
            printf("%c ", 'A' + path[j]);
        }

        printf("-> %d\n", weight);
    } else {                                        // more cities to visit:
        for (j = i; j < n; j++) {                   // pick each of them as ...
            int w = 0;                              // ... destination

            if (i > 0) {                            // determine distance ...
                w = city[path[i - 1]][path[j]];     // ... from prev. city,
            }                                       // ... if any

            swap(path, i, j);                       // swap city in;
            perm(path, i + 1, n, weight + w);       // recurse;
            swap(path, i, j);                       // swap city back
        }
    }
}

int main()
{
    int path[N];
    int i;

    for (i = 0; i < N; i++) path[i] = i;            // initial path

    perm(path, 1, N, 0);

    return 0;
}