Problem - Eingeschränkte Permutationen

[vichente]

Hallo zusammen,

Ich möchte eine Methode schreiben die alle Mögliche Kombinationen von null bis zum Endzahl n erzeugt im aufsteigende Folge, und m Elemente soll jede Kombination erhalten.
Z.b.wenn das Endazhl n = 5 und m = 3 sollen Folgende Kombinationen ausgegeben werden:
012 024 124 234
013 025 125 235
014 034 134 245
015 045 135 345
023 123 145

Habe folgende Methode gebastelt,aber die funktioniert nicht richtig. Bin dankbar für jeden Rat und Hilfe.

import java.util.*;

public class Permutationen
{
    public static ArrayList<int[]> perm(int m , int endZahl)
    {
         ArrayList<int[]> allKomb = new ArrayList<int[]>();
   
         for(int i = 0; i < m; i++){
            int[] temp = new int[m];
            for(int y = i + 1; y <= endZahl; y++){
                temp[i] = y;
            }
            allKomb.add(temp);
         }
         return allKomb;
    }
}

 

[ByeBye 154279]

Hey,

was genau funktioniert nicht?

TIPP:

int[] temp = new int[m];

kannst du eigentlich außerhalb der ersten for-Schleife setzen.

Und die zweite for-Schleife ist m.E. nicht korrekt.

for(int y = 1; y <= endZahl; y++){

sollte genügen; das was du da noch hingeschrieben hast, ist überflüssig.

EDIT:
bzw. initialisiere außerhalb der beiden for-Schleifen einen int-Wert und inkrementiere diesen in der zweiten For-Schleife, dann hättest du einen korrekten Index.

mfg
bo

 

[HonniCilest]

Da du vorher nicht weißt wieviele Stellen m die Lösungen haben sollen, würde ich hier auf jeden Fall mit Rekursion arbeiten. Auf die Weise kann man prima mit Abbruchbedingungen arbeiten.

 

[vichente]

Danke für eure Hilfe,
wenn ich das array außerhalb der ersten for-Schleife setze, und m anstatt Endzahl in zweite for-Schleife ,funktioniert trotzdem nicht richtig. Die verschiedenen Kombinationen sollen genau m Stellen haben. Mit Rekursion fehlt mir die Idee wie das ganze aufgebaut sein soll.
mfg

 

[HonniCilest]

Die rekursive Funktion sollte immer eine Liste zurückgeben und sich von Position zu Position hangeln und meiner Meinung nach gibt es 3 Punkte die beachtet werden sollte:
Abbruchbedingung: aktuelle Position ist die letzte im Array, füllt die Liste mit den noch möglichen Kombinationen und gibt die Liste zurück
Erste Position: aktuelle Position ist die erste, Schleife durchläuft alle Zahlen von Untergrenze bis Obergrenze - (Arraygröße-1) und ruft die rekursive Funktion mit inkrementierter Position auf, fügt die Rückgabewerte komplett an
Sonstige Position: durchläuft Schleife von Vorgängerwert + 1 bis noch möglicher Obergrenze, ruft hier wieder die rekusive Funktion auf und fügt die Liste jeweils komplett an die aktuelle Liste an (addAll)

 

[vichente]

Habe jetzt ein rekursive Methode geschrieben ,aber schon wieder keine korrekte Funktion. Bitte um Rat und Hilfe.

public class Permutationen
{ 
   private ArrayList<int[]> allKomb = new ArrayList<int[]>();

   public ArrayList<int[]> begPerm(int anzahl , int endZahl)
   {
        if(endZahl == 0){
            return allKomb;
        }
        for(int i = 0; i < anzahl; i++){
            int[]temp = new int[anzahl];
            for(int y = 0; y < anzahl; y++){
                temp[i] = y;
            }
            allKomb.add(temp);
        }   
        begPerm(anzahl, endZahl - 1);
        return allKomb;
    }
}

 

[HonniCilest]

Ich hab' die mal versucht einen Rahmen darzustellen, wie ich an das Problem herangehen würde:

public class Permutationen
{ 
	private ArrayList<int[]> allKomb = new ArrayList<int[]>();
	private int zahlenObergrenze;
	private int zahlenUntergrenze;
	private int anzahl;

	public Permutation(int m, int u, int o)
	{
		zahlenobergenze = o;
		zahkenuntergrenze = u;
		anzahl = m;	
	}
 
	public ArrayList<int[]> begPerm(int[] temp, int position)
	{
		ArrayList<int[]> kombis = new ArrayList<int[]>();
        	if(position == m-1) //-1 da position bei 0 beginnend, Abbruchbedingung
		{
			//Schleife über die noch möglichen Zahlen beginnend bei temp[position-1]+1, kombis.add(temp);
			//Achtung Sonderfall m=1
			//return
		}
		if(position == 0) //erster Aufruf
		{
           		//temp[position] Schleife, über die möglichen Werte (u -> o-m+1) und ruft begPerm rekursiv mit inkrementierter 

Position auf
			//	kombis.addAll(rekursiverAufruf); 
        	}
        	else //hat einen Vorgänger
		{
			//...
		}
                //return
	}
	public static void main(String[] arg)
	{
		//...		
	}
}

 

[vichente]

Ich hab versucht rekursive Methode zu implementieren, aber funktioniert immer noch nicht,bitte Rat und Hilfe.

import java.util.*;

public class Permutationen
{ 
    private ArrayList<int[]> allKomb = new ArrayList<int[]>();
    private int zahlenObergrenze;
    private int zahlenUntergrenze;
    private int anzahl;
 
    public Permutationen(int m, int o)
    {
        anzahl = m; 
        zahlenObergrenze = o;
        zahlenUntergrenze = 0;
    }
 
    public ArrayList<int[]> begPerm(int[] temp, int position)
    {
        ArrayList<int[]> kombis = new ArrayList<int[]>();
        
        if(anzahl == anzahl-1)
        {
            for(int i = temp[position-1]+1; i < position; i++){
                kombis.add(temp);
            }
        }
        if(position == 0)
        {
            for(int i = anzahl; i < zahlenObergrenze-anzahl+1; i++){
                kombis.addAll(begPerm(temp,position));
            } 
        }else{
           kombis.add(temp);
        }
        return allKomb;
    }
}