Länka ihop två Arrays/Listor

Hej, jag håller på att skriva algoritmen som kallas Johnson-Trotter för att ange alla permutationer av ett set. Allt är i stort sett klart (tror jag) och jag använder rekursion i min variant. Problemet jag stöter på dock är att jag har två olika Arrayer som jag behöver länka ihop, jag har t.ex:

a = {1, 2, 3, 4, 5}

dir = {false, false, true, false, true}

Där värdet dir[i] hör till a[i], så om jag efter en operation har {3, 1, 2, 4, 5} och värdet för a i dir är samma, alltså false, så ska ju dir se ut på följande sätt: {true, false, false, false, true}. Osv.

Hur brukar man göra i sånna här fall, är det någon form av Map (HashMap?) jag borde använda för att få dom att vara ett par? Problemet med det är väl att en Map inte har någon form av ordning?

(Lägger inte in någon kod, men om det behövs för att kunna hjälpa mig så lägger jag in det)

Tack på förhand!

Kanske lika bra att jag lägger in koden i alla fall. Har lagt in "base" bara för att kunna döda rekursionen. Annars ska den ta slut när metoden getMobilePos retunerar index = -1, för då finns det ingen mobile och då är vi klara. Som jag förstår algoritmen händer detta alltid till slut och det händer precis när vi fått fram alla permutationer.

I algoritmen har man siffror och en riktning, så: <1<2<3 innebär att 3 jämförs med 2, 2 med 1 och 1 med ingenting.

<12><3 innebär att 3 jämförs med 2 och 2 med 3 men 1 med ingenting.

Jag har representerat riktningen genom boolean[] right, som ger true om den pekar höger, false annars.

Den högsta största siffran som är större än siffran den pekar på kallas mobile number, den ska byta plats med den den pekar på:

<1<2<3 blir alltså <1<3<2 som sen blir <3<1<2

I nästa omgång är det 2 som är den största siffran som är större än den den pekar på då 3 inte pekar på något alls. Men en till regel i algoritmen är att alla tal större än det som är mobile number, så byter det talet riktning, alltså blir:

<3<1<2 blir 3><2<1 som sen blir <23><1

Osv.

Min output blir dock som på bilden. Får alltså inte problem första fyra gångerna men det är endast för att alla är false. Sen när jag fått en true, alltså en som pekar höger, då får jag problem. Det här är såklart för att boolean-arrayen och int-arrayen inte hänger ihop. Siffran och dess motsvarande riktning ska ju byta plats samtidigt men gör det inte. Jag kan säkert brute-force igenom detta och hålla mig till koncept som jag är bekväm med, men det känns som det finns någon typ av datastruktur som borde vara avsedd för sådana här fall?

    List<String> permutationSJT(String set) {
        // *** To get it all started (creating initial case) ***
        List<String> listResult = new ArrayList<String>();
        String set1 = set.trim();
        boolean[] right = new boolean[set1.length()];
        Arrays.fill(right, false);
        int[] a = new int[set1.length()];
        for (int i = 0; i < set1.length(); i++){
            int x = Character.getNumericValue(set1.charAt(i));
            a[i] = x;
        }
        // After this the "real" part start with recursion
        listResult.add(Arrays.toString(a));
        out.println(Arrays.toString(a));
        out.println(Arrays.toString(right));
        listResult = sjtRecursion(a, right, listResult, 10);
        return listResult;
    }

    List<String> sjtRecursion(int[] a, boolean[] right, List<String> listResult, int base){
        int index = getMobilePos(a, right);
        if (base == -1){
            return listResult;
        }else {
            base--;
            int mobileElement = a[index];
            a = mobileSwap(index, a, right);
            right = directionSwap(mobileElement, a, right);
            //out.println(Arrays.toString(a));
            //out.println(Arrays.toString(right));
            String result = Arrays.toString(a);
            listResult.add(result);
            return sjtRecursion(a, right, listResult, base);
        }
    }

    int getMobilePos(int[] a, boolean[] right){
        //Start value assuming only positive input. (Should be fixed so it handles all cases)
        int max = -1;
        int index = 0;
        for (int i = 0; i < a.length; i++) {
            if (!right[i] && i > 0) {
                if (a[i] > a[i - 1] && a[i] > max) {
                    max = a[i];
                    index = i;
                }
            } else if (right[i] && i < a.length - 1) {
                //<14><2<3
                if (a[i] > a[i + 1] && a[i] > max) {
                    max = a[i];
                    index = i;
                }
            }
        }
        if(max == -1){
            index = max;
        }
        return index;
    }

    int[] mobileSwap(int index, int[] a, boolean[] right){
        int tmp;
        if(right[index]){
            tmp = a[index+1];
            a[index + 1] = a[index];
            a[index] = tmp;
        } else if(!right[index]){
            tmp = a[index-1];
            a[index - 1] = a[index];
            a[index] = tmp;
        }
        return a;
    }

    boolean[] directionSwap(int mobile, int[] a, boolean[] right){
        for (int i = 0; i < a.length; i++){
            if(a[i] > mobile){
                if(right[i]){
                    right[i] = false;
                } else {
                    right[i] = true;
                }
            }
        }
        return right;
    }

Hej, det finns olika typer av maps som har annan ordning än hashmap, till ex LinkedHashMap. Men man kan lösa det utan maps också. Jag hade ett liknande problem i en Java-kurs. Vi löste det genom att skapa en klass för ett par av värden där värdena var instansvariabler, dvs om man t ex hade paret true och 3 såg det ut

MyObject obj1 = new MyObject (true,3)

Sen skapade vi en lista av MyObjects som vi jobbade med. Blir ungefär som en map där man kan ha elementen i en viss ordning. Hasmaps har ett internt ordningssystem som inte bygger på index och som man inte kan se eller modifiera själv.

Grymt, tack för svar! Det löste sig för mig med en liknande lösning som den du föreslog :)

Svara

Visa senaste svar