# Alle Möglichkeiten n Elemente Anzuordnen.



## Gauo (23. Jun 2007)

Mein Problem ist folgendes:
Ich habe n Verschiedene Elemente und eine zahl k.
Ich will nun alle Permutationen dieser n Elemente der Länge k haben.
Ich hab nun schon einige Algorithmen dazu im Internet gefunden und auch ihre implemenationen in Java, aber irgendwie funktionierten sie nur soweit, dass man irgendwie die die Objekte concat konnte...z.bString....
aber ich will nun am besten eine LinkedList<int[]> wo nun alle drin sind und dazu bekomm ich keine rekursion hin.
Ich hoffe jemand kann mir n tip geben oder n Rekursions ansatz


----------



## Marco13 (23. Jun 2007)

Wenn man eine Weile im Web sucht, findet man bestimmt Algorithmen, die das "auf einen Schlag" erledigen können. Vielleicht kannst du auch ein Beispiel für einen Algorithmus angeben, der "prinzipiell" macht, was du willst, und dann genau sagen, warum du den nicht auf dein Problem übertragen konntest.

Bis dahin schreibe ich mal spontane Gedanken :wink:

Ich würde das aufteilen in zwei Aufgaben: 
1. Alle k-Elementigen Teilmengen der gegebenen Menge bestimmen
2. Für jede Teilmenge alle Permutationen bestimmen

Für das zweite bietet sich sowas an wie
http://en.wikipedia.org/wiki/Permutation#Algorithm_to_generate_permutations

Für das erste könnte man, bildlich gesprochen, die n Elemente nebeneinander schreiben, und die k Elemente markieren, die man gerade "ausgewählt" hat. 
Man macht also Kreuzchen unter die ersten k Elemente. 
Dann schiebt man das letzte Kreuzchen Schrittweise nach rechts, bis man am Ende ist.
Dann schiebt man das VORletzte Kreuzchen einen Schritt nach rechts, und setzt das letzte rechts daneben. 
Dann schiebt man das letzte Kreuzchen Schrittweise nach rechts, bis man am Ende ist.
Dann schiebt man das VORletzte Kreuzchen einen Schritt nach rechts, und setzt das letzte rechts daneben. 
...
Dann schiebt man das VOR-VORletzte Kreuzchen einen Schritt nach rechts, und setzt das VOR-letzte rechts daneben, und das letzte rechts daneben.
Dann schiebt man das letzte Kreuzchen Schrittweise nach rechts, bis man am Ende ist.
Dann schiebt man das VORletzte Kreuzchen einen Schritt nach rechts, und setzt das letzte rechts daneben. 
...
Beispiel: 3 aus 6:

```
0 1 2 3 4 5
X X X  
X X   X  
X X     X  
X X       X  
X   X X  
X   X   X  
X   X     X  
X     X X  
X     X   X  
...
      X X X
```
Ugetesteter(!!!), schnell hingeschriebener(!!!) Pseudocode

```
// 'selected' enthält die "Kreuzchen" (am Anfang sind die ersten k kreuzchen gesetzt), x ist am anfang k
boolean nextSubset(boolean selected[], int k, int x) 
{
    if (x==-1) 
    {
        return false;
    }
    else
    {
          int toShift = findeDieStelleAnDerDas_x_teKreuzchenGesetztIst();
          if (toShift == selected.length-1)
          {
               nextSubset(selected, k, x-1);
               setzeDas_x_teKreuzchenRechtsNebenDas_x-1_te();
          }
          else
          {
               schiebeDasKreuzchenBei_toShift_um1nachRechts();
          }
    }
    return true;
}
```
Solange 'true' zurückgeliefert wurde, konnte noch eine neue Teilmenge gefunden werden. Ist aber wirklich nur ins blaue getippt (hab hier gerade kein JDK, kann es nicht testen)

WICHTIG: Vermutlich gibt es "elegantere" Ansätze, die beide Teilaufgaben "auf einmal" erledigen. (Man könnte nämlich auch 'int's statt 'booleans' verwenden, und dann irgendwie mit einer abgewandelten Version des Algorithmus aus Wikipedia direkt die ausgewählten Elemente permutieren). Aber als "Meta-Divide-And-Conquer-Ansatz" finde ich so eine Aufteilung in Teilprobleme ganz hilfreich - solange sie die Anforderungen erfüllt, und nicht zeitaufwändiger ist, als andere Ansätze.


----------



## Gauo (23. Jun 2007)

Danke, ich hab bis jetzt immer nur hinbekommen, wenn k==n ist also ich nur durchnummeriere...
cih werd ma das hier durchkauen und schaun ob ichs hinbekomm.

Zur Not hatte ich vor mit eine Art n-k Baum zu basteln und dann einfach die Wege auszulesen...aber als eigene Datenstruktur, weil ich einfach die übertrag leistung in ne Reksursive Funktion hinbekommen hab ^^


----------



## Gauo (23. Jun 2007)

```
public boolean nextSubset(boolean[] selected, int k, int x){
    if(x==-1){
        return false;
    }else{
        int toShift=positionofXthX(selected,x);
        if(toShift==selected.length-1){
            nextSubset(selected,k,x-1);
            shiftX(x);
        }else{
            selected[toShift]=false;
            selected[toShift+1]=true;
        }
        
    }
    return true;
}

public void shiftX(int x){
    int tmp=x;
    for(int i=0;i<selected.length;i++){
        if(selected[i]){
            if(tmp-1==0){
                selected[i+1]=true;
                for(int k=i+2;k<selected.length;k++){
                    if(selected[k]){
                        selected[k]=false;
                        break;
                    }
                }
            }else{
               tmp--;
            }
        }
    }
}
public int positionofXthX(boolean[] selected, int x){
    int tmp=x;
    for(int i=0;i<selected.length;i++){
        if(selected[i]){
            if(tmp==1){
                return i;
            }else{
                tmp-=1;
            }
        }
    }
    return 0;
}
```

Hier mal meine Umsätzung des Pseudocodes...aber klappt irgendwie noch nicht, sobald halt das True hinten ankommt will er nochmal schieben...ich versuch das mal mit dem Baum -.-


----------



## Guest (23. Jun 2007)

Das Hier Sollte mir doch nun eigentlich das gewünschte Liefern(Achtung n die länge Permutationen und n nun die Anzahl der Objekte)
nun brauche ich ja nur noch die LinkedList zerlegen in Mengen ||=n oda?


```
public class Tree {
    private class TreeNode{
        LinkedList<TreeNode> nodes=new LinkedList();
        int key;
        public TreeNode(int keys,int n,int key){
            this.key=key;
            if(n>0){
            for(int i=0;i<keys;i++){
            nodes.add(new TreeNode(keys,n-1,i));
            }
            }
        }
        
        public LinkedList<Integer> getKeys(){
            LinkedList<Integer> muh= new LinkedList();
            muh.add(key);
            for(int i=0;i<nodes.size();i++){
                LinkedList<Integer> temp=nodes.get(i).getKeys();
                while(!temp.isEmpty()){
                    muh.add(temp.poll());
                }
            }
            return muh;
        }
    }

    private LinkedList<TreeNode> anker=new LinkedList();
    public Tree(int keys, int n){
        for(int i=0;i<keys;i++){
            anker.add(new TreeNode(keys,n-1,i));
        }
    }
        public LinkedList<Integer> getKeys(){
            LinkedList<Integer> muh= new LinkedList();
            
            for(int i=0;i<anker.size();i++){
                LinkedList<Integer> temp=anker.get(i).getKeys();
                while(!temp.isEmpty()){
                    muh.add(temp.poll());
                }
            }
            return muh;
        }    
}
```


----------



## Gauo (23. Jun 2007)

hm...irgendwas mach ich falsch ich bekomm bei Tree(6,4) nur 388 möglichkeiten als |Leaves|/4...aber da sollten 1296 rauskommen :/


----------



## Leroy42 (24. Jun 2007)

Gauo hat gesagt.:
			
		

> hm...irgendwas mach ich falsch ich bekomm bei Tree(6,4) nur 388 möglichkeiten als |Leaves|/4...aber da sollten 1296 rauskommen :/




lass mich morgen mal basteln, 
weile wegen
heut bn ivh zu brdoffen..............


----------



## Gauo (24. Jun 2007)

Das Problem hab ich gestern noch erkannt aber wieder kein Plan wie ich es Löse ^^...die blätter lese ich nähmlich nicht so aus wie ich es tuen sollte, da ich jeden Zwei nur einmal auslese, dabei sollte ich ja jeden Pfad auslesen also die Verzweigungen mehrmals


----------



## Gauo (24. Jun 2007)

ich hab mal die Methode der Nodes geändert

```
public LinkedList<Integer> getKeys(LinkedList<Integer> mau){
            System.out.println("test");
            System.out.println(mau);
            
            if(nodes.size()>0){
            for(int i=0;i<nodes.size();i++){
                int tmp=key;
                mau.add(tmp);
                mau=nodes.get(i).getKeys(mau);
            }}else{
                int tmp=key;
                mau.add(tmp);
                mau.add(null);
            }
            
            return mau;
        }
```
Jedoch verschluckt er nun immer welche und kommt bei 3,3 auf 21 bei 6,4 auf irgendwas mit 700


----------



## Guest (24. Jun 2007)

Hokay, ein neuer Ansatz und ist wohl nun auch das geworden das ich suche:

```
public class Permnator {
    static int k = 6;
    static int n = 4;
    static int[] perm=new int[n];
    
    public static void kElem(int level){
        if(level<n){
        for(int i=0; i<k; i++){
            perm[level]=i;
            kElem(level+1);
            
            
        }
        }else{
            for(int i=0;i<n;i++){
                System.out.print(perm[i]);
            }
            System.out.println();
        }
        
    }
    

    public static void main(String[] args){
        kElem(0);
    }
    
}
```


----------



## Marco13 (25. Jun 2007)

Hm. Eine Permutation der Ziffern ist das aber nicht. Du müßtest da ja jetzt noch die wegwerfen, die eine Ziffer mehrmals enthalten. Das, was du im Moment machst, ist ziemlich trivial: Du zählst :roll:

```
public class Permnator2
{
    static int k = 6;
    static int n = 4;

    public static void main(String[] args)
    {
        for (int i=0; i<1296; i++)
        {
            System.out.println(pad(Integer.toString(i, k)));
        }
    }

    private static String pad(String s) // Von vorne mit '0'en auffüllen
    {
        while (s.length() < n) s="0"+s;
        return s;
    }

}
```


----------



## Gauo (25. Jun 2007)

naja sry, Permutation war dan wohl etwas vergriffen mit dem Begriff,  es dürfen die k elemente doppelt verwendet werden...
also k^n möglichkeiten


----------



## Gauo (25. Jun 2007)

Sollt mich mal reggen sry -.-....
gibt es vielleicht noch eine effizientere möglichkeit?


----------



## Marco13 (25. Jun 2007)

Na also dann - (das ist jetzt aber schon was GANZ anderes - mein Kreuzchen-Gewurschtel ist damit überflüssig, weil das NUR dem Zweck diente, zu _verhindern_, dass man alle k^n Kombinationen aufstellen muss - das können nämlich (im Vergleich zu denen, in denen jede Ziffer nur einmal vorkommt) verdammt viele sein)

Ich habe deine Lösung jetzt nicht nachvollzogen, aber vielleicht ist sie schon effizient. Kann gut sein. Letztendlich macht man damit aber - wie gesagt - nichts anderes als zu zählen. Schau vielleicht auch mal in
http://www.java-forum.org/de/viewtopic.php?p=293731&highlight=
... das könntest du bestimmt leicht anpassen. Wenn nicht, sag einfach bescheid.


----------

