生成C中所有可能的排列 [英] Generate all possible permutations in C

问题描述

我正在尝试开发代码来解决C语言中的旅行推销员"问题，但是我有一些限制:我只能使用"for"，"while"，"do"，数组，矩阵和诸如此类的简单内容，因此，没有任何功能或递归(不幸的是).

I'm trying to develop a code to solve the Travelling salesman problem in C, but I have some restrictions: I can only use "for, "while", "do", arrays, matrix and simple things like that, so, no functions or recursion (unfortunately).

到目前为止我所拥有的:

What I've got so far:

用户将像这样输入城市坐标X和Y:

The user will will type the city coordinates X and Y like this:

8.15    1.58
9.06    9.71
1.27    9.57
9.13    4.85

用于存储坐标的代码.

float city[4][2];
int i;

for (i=0; i<4; i++)
    scanf("%f %f", &cidade[i][0], &cidade[i][1]);

有4个城市，因此"i"从0到3.X和Y存储在矩阵的第二维[0]和[1]上.

There are 4 cities, so "i" goes from 0 to 3. X and Y are storaged on the second dimension of the matrix, [0] and [1].

现在的问题是，我必须生成矩阵第一维的所有可能排列.仅有4个城市似乎很容易，因为所有可能的路线都是(每次都必须从A城市开始):

The problem now is that I have to generate ALL POSSIBLE permutations of the first dimension of the matrix. It seems easy with just 4 cities, because all possible routes are (it must starts with city A everytime):

A B C D
A B D C
A C B D
A C D B
A D C B
A D B C

但是我必须将其扩展到10个城市.人们告诉我，它将使用9个嵌套的foor循环，但是我无法开发它=(

But I'll have to expand it for 10 cities. People have told me that it will use 9 nested foor loops, but I'm not being able to develop it =(

有人可以给我一个主意吗?

Can somebody give me an idea?

推荐答案

扩展至10(并查找城市名称)作为练习.这很可怕，但这就是你在教授的限制下得到的结果

Extending to 10 (and looking up city names) as an exercise for the reader. And it's horrid, but that's what you get with your professor's limitations

#include <stdio.h>

int main(void) {
    for (int one = 0; one < 4; one++) {
        for (int two = 0; two < 4; two++) {
            if (two != one) {
                for (int three = 0; three < 4; three++) {
                    if (one != three && two != three) {
                        for (int four = 0; four < 4; four++)
                            if (one != four && two != four && three != four) {
                                printf("%d %d %d %d\n", one, two, three, four);
                            }
                    }
                }
            }
        }
    }
    return 0;

}

这篇关于生成C中所有可能的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！