Wie Wert von allen bisherigen Rahmen weitergeben (höhere Frames) zu einem unteren Rahmen während Rekursion

Question

Auf meine Frage zu vereinfachen bitten, lassen Sie uns alle Permutationen eines Arrays Druck betrachten, ohne Wiederholung. Also, wenn {1,2,3} das Array war, wäre die Ausgabe der folgenden

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
count == 6 

Wie kann ich eine Zählung aller Elemente passieren, die niedriger ist an einem Rahmen bereits Teil des Arrays sind. Ich meine, sagen wir, in den ersten beiden Frames der Rekursion habe ich die Elemente 1 und 2 in meinem Stack. Ich muss dem Rahmen unten sagen, dass er alle Elemente außer 1 und 2 verwenden kann, da es bereits verwendet wird.

Bitte siehe meinen Code unten, wo ich ein Array aller auftretenden Elemente als Teil des Funktionsaufrufes für den Rahmen unten passieren. Aber ich muss auch die Elemente des Arrays für andere rekursive Aufrufe im selben Frame speichern und wiederherstellen, da Java keine Kopie des Arrays in jedem Frame speichert und das Übergeben von Referenzen dazu führt, dass das Array überschrieben wird.

import java.util.Arrays; 

public class SendfromHigherFrameToLowerFrame { 
    static int count = 0; 

    public static void main(String[] args) { 
     int[] a = {1,2,3}; 

     int[] stack = new int[3]; 
     fun(a, stack, 0); 

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

    static void fun(int[] a, int[] stack, int frame) 
    { 
     if(a.length == frame) 
     { 
      count++; 
      print(stack); 
      return; 
     } 

     for(int i = 0;i<a.length;i++) 
     { 
      //save stack 
      int[] temp = new int[stack.length]; 
      save(stack, temp); 
      if(isValid(stack, a[i]) == true) 
      { 
       stack[frame] = a[i]; 
       fun(a, stack, frame+1); 
       //restore stack 
       restore(temp, stack); 
      } 
     } 
    } 

    static void save(int[] source, int[] destination) 
    { 
     for(int i = 0;i<source.length;i++) 
      destination[i] = source[i]; 
    } 

    static void restore(int[] source, int[] destination) 
    { 
     for(int i = 0;i<source.length;i++) 
      destination[i] = source[i]; 
    } 

    static boolean isValid(int[] a, int key) 
    { 
     for(int i = 0;i<a.length;i++) 
     { 
      if(a[i] == key) 
       return false; 
     } 
     return true; 
    } 

    static void print(int[] a) 
    { 
     for(int x : a) 
      System.out.print(x + " "); 
     System.out.println(); 
    } 
} 

Bitte schlagen Sie Verbesserungen des Codes vor, oder eine einfachere Methode zum Weiterleiten von Elementen durch den Aufruf.

PS: Bitte beachten Sie, dass Permutationen ist nicht meine ursprüngliche Frage zu erzeugen, und ich verstehe, gibt es einfachere Möglichkeiten, es zu tun, es ist nur für den Zweck meiner Frage der Vermittlung.

Answer 1

Da es keine Möglichkeit gibt, ein Primitiv per Referenz in Java zu übergeben, können Sie nicht einfach einen int erstellen und den Aufrufstapel weiterleiten. Es gibt drei Workarounds für dieses Problem:

• Verwenden Sie eine veränderbare Klasse, wie zum Beispiel einer Anordnung eines einzelnen int oder AtomicInteger. Dieser Ansatz grenzt jedoch an einen Missbrauch von Arrays und veränderbaren Klassen.
• Erstellen Sie eine Instanzvariable oder eine statische Variable, so wie Sie es gemacht haben. Dies ist alles andere als ideal, da Ihre rekursive Funktion nicht einspringt und daher viel schwieriger zu testen ist.
• Geben Sie den geänderten Wert aus der Methode zurück und fügen Sie ihn einer lokalen Variablen innerhalb der rekursiven Methode hinzu, um ihn als eigenen Rückgabewert zu übergeben. Dieser Ansatz ist zwar gut, bietet jedoch nur einen einzigen Rückgabewert und erfordert, dass Sie beim Schreiben Ihres Codes sehr vorsichtig vorgehen.

Hier ist, wie Sie funktionieren kann, die letzte oben beschriebenen Ansatz zu implementieren modifiziert werden:

static int fun(int[] a, int[] stack, int frame) { 
    if(a.length == frame) { 
     print(stack); 
     return 1; 
    } 
    int res = 0; 
    for(int i = 0;i<a.length;i++) { 
     //save stack 
     int[] temp = new int[stack.length]; 
     save(stack, temp); 
     if(isValid(stack, a[i]) == true) { 
      stack[frame] = a[i]; 
      res += fun(a, stack, frame+1); 
      //restore stack 
      restore(temp, stack); 
     } 
    } 
    return res; 
} 

Demo.

Hinweis: Es versteht sich, dass Ihre Übung nicht tun müssen all dies, weil count immer gleich stack.length ist.

Answer 2

ich nicht von einem Rahmen beantworten will Wert vorbei, aber ich habe eine einfache Möglichkeit für Permutationen.

void Calc(String a, String b){ 


    if (a.equals("")) { 
     System.out.println(a); 
     return; 
    } else { 
     for (int i = 0; i < a.length(); i++) { 
      Calc(removeFirst(a, i), b + a.charAt(i)); 
     } 

    } 

    public static void main(String[] args){ 
     Calc("123", ""); 
    } 

Goodluck

Milad