Generate all possible paths

Question

Generate all possible paths

Navigation

#1 by (1 votes)

0

In an exercise, I need to print in a file all the possibilities of trajectory between a number% of cities%, with each city being represented by N and x coordinates and that the last city must be the first (All cities should be tested as a 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 line of the file displays a possible trajectory and the cities being represented by their coordinates between parentheses.

I have a bit of difficulty in working out the reasoning of the function that will generate the possibilities. Can this problem be considered as a permutation problem?

I recently 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 build on them? I tried, but I could not use the y struct inside them.

I even thought about creating a sequence that goes from 1 to Cidade and consider it as if it were the indexes of my N vector, but I also could not implement it.

I would like to know if the ideas I have proposed are appropriate and / or if there is any other better way to develop the problem.

c

asked by anonymous 15.09.2017 / 21:52

1 answer

Dependencies with EntityFramework C # Error to popular jtable with database

score 1 · Accepted Answer

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 do not think you can do better than this with this description of the problem, because your output will have the order of a factorial. That is, your algorithm will have to print an output of size N an N number! of times.