Permutation

[Snopy_Java]

Hallo Community,

ich bin Java-Wiedereinsteiger und habe im Internet folgenden Coden gefunden. Funktionsweise ist nicht das Problem, sondern die Implemtierung als funktionsfähigen Code in der Class Permute. Wieso funktioniert er nicht - er scheint ein Problem mit List<Integer> l = new ArrayList<Integer>(); zu haben!?

import java.util.*;

public class Permute
{
    public static void main(String[] args)
    {
        int n = Integer.parseInt(args[0]);
        
        // make list 1, ..., n
        List<Integer> l = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++)
            {
                l.add(i);
            }

        // list all the permutations
        listPermutations(l);
    }

    /**
     * Outputs (to System.out) all the permutations of the integers in the
     * given list.
     *
     * @param l a list of integers
     */
    private static void listPermutations(List<Integer> l)
    {
        permute(l, 0);
    }

    /**
     * Outputs (to System.out) all the permutations of the given list
     * of integers that have the same prefix.  The common prefix is the
     * prefix of the list of length given by the <code>int</code> argument.
     *
     * @param a list of integers
     * @param fixed an integer
     */
    private static void permute(List<Integer> l, int fixed)
    {
        if (fixed >= l.size() - 1)
            {
                // nothing left to permute -- 
                System.out.println(l);
            }
        else
            {
                // put each element from fixed+1...EOL in location fixed in turn
                
                // special case (no swaps) for leaving item in loc fixed as is
                permute(l, fixed + 1);

                // now try all the other elements in turn
                int x = l.get(fixed);
                for (int i = fixed + 1; i < l.size(); i++)
                    {
                        // swap elements at locations fixed and i
                        l.set(fixed, l.get(i));
                        l.set(i, x);

                        // find all permutations of the elements after fixed
                        permute(l, fixed + 1);

                        // put things back the way they were
                        l.set(i, l.get(fixed));
                        l.set(fixed, x);
                    }
            }
    }
}

Vielen Dank für eure Hilfe

 

[gescom]

Falls du das in einer IDE ausführst musst du diese Zeile ändern.

 int n = Integer.parseInt(args[0]);

Andernfalls, über cmd line, übergibst du damit ein Wert an die Main.

 

[Snopy_Java]

Danke für die Antwort, hat geholfen!

 

[Snopy_Java]

Eine Verständnisfrage zum Quellcode habe ich doch noch:

Zu Beginn wir ein ArrayList mit Zahlen befüllt. Wenn die ArrayList vollständig befüllt ist werden in der Funktion permut() die letzten beiden Stellen getauscht und ausgegeben. Setter/Getter setzen die ausgewählten Objekte in der ArrayList wieder an ihre ursprüngliche Version. Mir ist allerdings nicht ganz klar, wieso sich der Wert der Variablen fixed ändert?!

 

[X5-599]

Ohne mir den Code genauer angesehen zu haben (oder verstanden zu haben):

In Zeile 62 bzw. 51 der permute() Methode gibt es diese Anweisung:

permute(l, fixed + 1);

Es wird also rekursiv immer wieder diese Methode aufgerufen. Immer mit der Zahl "fixed" +1. d.h. mit jedem Aufruf der Methode hat die Variable "fixed" einen höheren Wert.


Man möge mich verbessern wenn ich falsch liege (Wie gesagt, habe nicht nachvollzogen wie die Methode genau arbeitet). Aber so sieht es für mich aus...

 

[Snopy_Java]

Das mit jedem Aufruf der Methode die Variable "fixed" ein höheren Wert erhält kann ich nachvollziehen. Allerdings nicht, dass sich der Wert verringert...

siehe Ergebnis nach zwei Durchläufen:

[1, 2, 3, 4]
2
[1, 2, 4, 3]
2
2
1

 

[X5-599]

Kann ich dir nicht beantworten. Evtl fängt durch das rekursive Aufrufen die Ausgabe beim "höchsten" fixed an und arbeitet sich dann zum "niedrigsten".

Also in etwa wie diese Methode:

public static void go(int i)
{
  if(i < 9)
  {
    go(i+1);
  }

  System.out.println("i="+i);
}

Wenn man go(0) aufruft bekommt man die Ausgabe:
9
8
7
6
5
4
3
2
1
0

Hab leider momentan nicht die Zeit mir deine Methode genauer anzusehen.