0

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:

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

The code to storage the coordinates.

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

for (i=0; i<4; i++)
    scanf("%f %f", &cidade[i][0], &cidade[i][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].

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

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?

12
  • 1
    "No functions" ? That a very stupid constraint. And solving the Traveling Salesman problem by bruteforce is so as well.
    – Eugene Sh.
    May 13, 2016 at 14:17
  • How would you generate all 1-long combinations for 10 cities? A for-loop that just produced all cities. Now, for 2-long ones, it's a loop over 10 cities to get the first, for each "first" city a loop over the other cities to get the second of the combination. For 3 long, it's each of the 10 cities followed in each case by the 2-long combinations of the other cities.... and so on, up to 10 May 13, 2016 at 14:18
  • 1
    @EugeneSh, it's an assignment. The point is about writing the C, not solving the travelling salesman problem efficiently. May 13, 2016 at 14:19
  • @TheArchetypalPaul Writing C without functions?? How is that? Sometimes I am just wondering what these guys in schools are trying to teach.
    – Eugene Sh.
    May 13, 2016 at 14:20
  • 1
    @Shofukan He should try to teach the exact opposite. Anyway, complete your course and stay away from this guy. And try not to follow his guidelines...
    – Eugene Sh.
    May 13, 2016 at 14:30

2 Answers 2

1

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;

}
9
  • I'm pretty sure the assignment will say "no functions in the body of main", or something or it's going to be an unanswerable assignment! May 13, 2016 at 14:51
  • And, yes, printf is a function, but the real answer won't need printf. Although I do wonder how it will display the result! May 13, 2016 at 14:52
  • Well, OK, horrid. I would have gone with 'gruesome'. May 13, 2016 at 14:57
  • "(informal)= unpleasant, terrible, awful, offensive, nasty, disgusting, horrible, dreadful, obscene, disagreeable, yucky" (collinsdictionary.com/dictionary/english-thesaurus/horrid). Yep, all of them apply. May 13, 2016 at 15:00
  • I guess I expressed myself wrongly. I can use printf, scanf and etc. But I'm not allowed to create a new "int main(SOMETHING_HERE)". By the way, I'm a beginner, I don't even know how to do it, and it's hard for me to talk about a subject which I'm not yet familiar with in a foreign language, hehe.
    – Shofukan
    May 13, 2016 at 15:01
0

This is based on https://stackoverflow.com/a/3928241/5264491

#include <stdio.h>

int main(void)
{
    enum { num_perm = 10 };
    int perm[num_perm];
    int i;

    for (i = 0; i < num_perm; i++) {
        perm[i] = i;
    }

    for (;;) {
        int j, k, l, tmp;

        for (i = 0; i < num_perm; i++) {
            printf("%d%c", perm[i],
                   (i == num_perm - 1 ? '\n' : ' '));
        }

        /*
         * Find largest j such that perm[j] < perm[j+1].
         * Break if no such j.
         */
        j = num_perm;
        for (i = 0; i < num_perm - 1; i++) {
            if (perm[i + 1] > perm[i]) {
                j = i;
            }
        }
        if (j == num_perm) {
            break;
        }

        for (i = j + 1; i < num_perm; i++) {
            if (perm[i] > perm[j]) {
                l = i;
            }
        }

        tmp = perm[j];
        perm[j] = perm[l];
        perm[l] = tmp;

        /* reverse j+1 to end */
        k = (num_perm - 1 - j) / 2; /* pairs to swap */
        for (i = 0; i < k; i++) {
            tmp = perm[j + 1 + i];
            perm[j + 1 + i] = perm[num_perm - 1 - i];
            perm[num_perm - 1 - i] = tmp;
        }
    }
    return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.