Generate all possible permutations in C

Question

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?

Answer 1

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;
}

Answer 2

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;

}