Permutation ohne Wiederholung mit rekursion

[metalfan]

Hi,

in unten stehendem Code(funktioniert) wird change(), permutate() und nochmal change() aufgerufen.
Aber warum das zweite mal?

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


public class CopyOfFullPermut {

	
	int permutate_run = 1;
	
	public void permutate(int N, List<String> elements) {
		System.out.println("permutate(), run: " + permutate_run);
		permutate_run = permutate_run +1;
		if (N == 0) {
			//After each permutation, we are here
			print(elements);
		}
		else
			
			for (int i = 0; i < N; i++) {
				change(elements, i, N-1);
				permutate(N -1, elements);
				change(elements, i, N-1);
			}
	}

	

	//change Element i with Element N
	public void change(List<String> arr, int i, int N) {
		//output
		System.out.println("i: " + i + " N: " + N);
		String output = "";
		for (String x: arr) {
			output = output + x + " ";
		}
		System.out.println("\tList before change:\t" + output);
		////////////////
		
		String tmp = arr.get(i);
		arr.set(i, arr.get(N));
		arr.set(N, tmp);
		
		//output
		output = "";
		for (String x: arr) {
			output = output + x + " ";
		}
		System.out.println("\tList after change:\t" + output);
		////////////////////
	}

	
	public int runs = 1;
	public void print(List<String> arr) {
		
			//System.out.println("Run: " + runs);

			String output = "";
			for (int i = 0; i < arr.size(); i++) {
				output = output + arr.get(i) + " ";

			System.out.println("\n");
			System.out.println("current Permutation: " + output + " - number: " + runs);
			
			runs = runs + 1;

		}
			
	}
	

	public static void main(String args[]) {
		CopyOfFullPermut x = new CopyOfFullPermut();
		List<String> myElements = new ArrayList<>();
		myElements.add("one");
		myElements.add("two");
		//myElements.add("three");
		int tmp = myElements.size();
		x.permutate(tmp, myElements);
	}
}

 

[VfL_Freak]

Moin,

na, womöglich weil Du es zweimal aufrufst 😱 ???:L

for( int i = 0; i < N; i++ )
{
    change( elements, i, N-1 );   // einmal
    permutate( N -1, elements );
    change( elements, i, N-1 );   // zweimal
}

Gruß
Klaus

 

[metalfan]

Das ist nicht mein Code, der Code funktioniert aber. Die Frage ist warum es gerade so funktioniert?

 

[JCODA]

Change vertauscht gerade die Elemente i und N, sodass diese Vertauschung am SchleifenEnde wieder rückgängig gemacht wird.

Für Algebraiker: Transpositionen haben Ordnung 2, also (Transposition)^2 = id

 

[Gucky]

Weil er für eine andere Funktionalität anders aussehen würde. Was meinst du damit? Lass doch mal ein mal weg und guck, was passiert.