Generate all possible paths

Question

In an exercise, I need to print, in a file, all the trajectory possibilities between a number N of cities, each city being represented by coordinates x and y and that the last city should be the first (All cities should be tested as starting point). The output file should be as follows:

(ax,ay)    (bx,by)    (cx,cy)    ...    (ax,ay)
(ax,ay)    (cx,cy)    (bx,by)    ...    (ax,ay)
(bx,by)    (ax,ay)    (cx,cy)    ...    (bx,by)

Where each row of the file displays a possible trajectory and the cities being represented by their coordinates in parentheses.

I have a little difficulty in devising the reasoning of the function that will generate the possibilities. This problem can be considered as a permutation problem?

Not long ago I implemented two functions that generate permutations of a sequence, as can be seen below:

void Troca(char *x, char *y)
{
    char aux;
    aux = *x;
    *x = *y;
    *y = aux;
}

void Permuta(char *sequencia, int inicio, int termino)
{
    int j;
    if(inicio == termino)
        printf("%s\n", sequencia);
    else
    {
        for(j = inicio; j <= termino; j++)
        {
            Troca((sequencia+inicio), (sequencia+j));
            Permuta(sequencia, inicio+1, termino);
            Troca((sequencia+inicio), (sequencia+j));
        }
    }
}

If this problem can be seen as a permutation problem, can I use these functions and develop on top of them? I tried, but I couldn’t use the Cidade within them.

I even thought of creating a sequence that goes from 1 to 1 N and consider as if they were the contents of my vector *Cidades, but also failed to implement.

I would like to know whether the ideas I have proposed are reasonable and/or whether there is any other better way of developing the problem.

Answer 1

Yes. Your idea works in this case. Your code can be written like this:

void Permuta(struct cidade *sequencia, int inicio, int termino)
{
    int j;
    if(inicio == termino) {
        for (int i = 0; i < N; ++i) {
            printf("(%d,%d)\t", sequencia[i].x, sequencia[i].y);
        }
        printf("(%d %d)\n", sequencia[0].x, sequencia[0].y);
    }
    else
    {
        for(j = inicio; j <= termino; j++) {
            Troca((sequencia+inicio), (sequencia+j));
            Permuta(sequencia, inicio+1, termino);
            Troca((sequencia+inicio), (sequencia+j));
        }
    }
}

I don’t think you can do better than that with this description of the problem, because your exit will have the order of a factorial. That is, your algorithm will have to print an output of size N a number N! of times.