Trying to implement a kind of traveller algorithm in Java

Question

I'm trying to implement a simple and efficient algorithm for this kind of traveller problem (but this is NOT the "travelling salesman"):

A traveller has to visit N towns, and:
1. each trip from town X to town Y occurs once and only once
2. the origin of each trip is the destination of the previous trip

So, if you have for example towns A, B, C,

A->B, B->A, A->C, **C->A, B->C**, C->B

is not a solution because you can't do C->A and then B->C (you need A->B in between), whereas:

A->B, B->C, C->B, B->A, A->C, C->A

is an acceptable solution (each destination is the origin of the next trip).

Here's below an illustration in Java, with 4 towns, for example.

ItineraryAlgorithm is the interface to implement when providing an algorithm that answers the question. The main() method will test your algorithm for duplicates if you replace new TooSimpleAlgo() by new MyAlgorithm().

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Traveller {

    private static final String[] TOWNS = new String[] { "Paris", "London", "Madrid", "Berlin"};

    public static void main(String[] args) {
        ItineraryAlgorithm algorithm = new TooSimpleAlgo();
        List<Integer> locations = algorithm.processItinerary(TOWNS);
        showResult(locations);
    }

    private static void showResult(List<Integer> locations) {
        System.out.println("The itinerary is:");
        for (int i=0; i<locations.size(); i++) {
            System.out.print(locations.get(i) + " ");
        }
        /*
         * Show detailed itinerary and check for duplicates
         */
        System.out.println("\n");
        System.out.println("The detailed itinerary is:");
        List<String> allTrips = new ArrayList<String>();
        for (int m=0; m<locations.size()-1; m++) {
            String trip = TOWNS[locations.get(m).intValue()] + " to "+TOWNS[locations.get(m+1).intValue()];
            boolean duplicate = allTrips.contains(trip);
            System.out.println(trip+(duplicate?" - ERROR: already done this trip!":""));
            allTrips.add(trip);
        }
        System.out.println();
    }

    /**
     * Interface for interchangeable algorithms that process an itinerary to go
     * from town to town, provided that all possible trips are present in the
     * itinerary, and only once. Note that after a trip from town A to town B,
     * the traveler being in town B, the next trip is from town B.
     */
    private static interface ItineraryAlgorithm {
        /**
         * Calculates an itinerary in which all trips from one town to another
         * are done. Trip to town A to town B should occur only once.
         * 
         * @param the
         *            number of towns to visit
         * @return the list of towns the traveler visits one by one, obviously
         *         the same town should figure more than once
         */
        List<Integer> processItinerary(String[] towns);
    }

    /**
     * This algorithm is too simple because it misses some trips! and generates
     * duplicates
     */
    private static class TooSimpleAlgo implements ItineraryAlgorithm {

        public TooSimpleAlgo() {
        }

        public List<Integer> processItinerary(String[] towns) {
            final int nbOfTowns = towns.length;
            List<Integer> visitedTowns = new ArrayList<Integer>();
            /* the first visited town is town "0" where the travel starts */
            visitedTowns.add(Integer.valueOf(0));
            for (int i=0; i<nbOfTowns; i++) {
                for (int j=i+1; j<nbOfTowns; j++) {
                    /* travel to town "j" */
                    visitedTowns.add(Integer.valueOf(j));
                    /* travel back to town "i" */
                    visitedTowns.add(Integer.valueOf(i));
                }
            }
            return visitedTowns;
        }

    }

}

This example program gives the following output, the first part being the list of town indexes in the order the traveller visits them (0 for "Paris", 1 for "London", 2 for "Madrid", and 3 for "Berlin").

The itinerary is:
0 1 0 2 0 3 0 2 1 3 1 3 2 

The detailed itinerary is:
Paris to London
London to Paris
Paris to Madrid
Madrid to Paris
Paris to Berlin
Berlin to Paris
Paris to Madrid - ERROR: already done this trip!
Madrid to London
London to Berlin
Berlin to London
London to Berlin - ERROR: already done this trip!
Berlin to Madrid

How would you suggest to implement ItineraryAlgorithm?
EDIT: if you prefer, you can propose a solution for a maximum of 4, 5, ..., up to 10 towns as you like.

Answer 1

I think I found what I was looking for:

private static class SylvainSAlgo implements ItineraryAlgorithm {

    @Override
    public List<Integer> processItinerary(String[] towns) {

        List<Integer> itinerary = new ArrayList<Integer>();
        for (int i = 0; i<towns.length; i++) {
            for (int j = i + 1; j < towns.length; j++) {
                itinerary.add(Integer.valueOf(i));
                itinerary.add(Integer.valueOf(j));
            }
        }
        itinerary.add(Integer.valueOf(0));
        return itinerary;
    }
}