Algorithmus für Kombinatorik

romancer · Gast

Hallo,

ich suche einen (möglichst effizienten) Algorithmus um aus n Elementen
alle möglichen Kombinationen der Reihe nach zu erstellen, wobei die Reihenfolge
der Elemente wichtig ist.

z.B: für 3 Elemente die Tupel (123),(132),(213),(231),(312),(321)

Irgendwie find ich keinen Ansatz, der mir wirklich alle Tupel liefert unglücklich

Für jede Hilfestellung wäre ich dankbar.

Thx

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Hm... Das Problem kommt mir irgendwoher bekannt vor... Augenzwinkern

Falls dir der Code an sich reicht und du dich ansonsten mit eher mittelmäßigen Kommentaren zufriedengibst, kannst du dir das mal anschauen:

http://www.wi.uni-muenster.de/pi/lehre/klausuren/Info1WS02.pdf

Aufgabe 3 dürftest du wohl ganz interessant finden... Augenzwinkern

dast · Anmeldungsdatum: 28.06.2005 Beiträge: 2 Wohnort: Österreich - Tirol

In C++ lässt sich das ganze recht schön mit Hilfe der STL erledigen:

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Na ja... Der Witz an der Sache ist ja eigentlich nicht, das Ergebnis zu kriegen, sondern wie der Algorithmus funktioniert, der so was berechnet...

kurellajunior · Administrator Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow

Falls noch hilfreich:

rekursiver Ansatz:

Bilde eine Menge M mit allen Elementen
nimm das erste Element heraus
fahre mit der verkleinerten Menge fort (Rekursion)
nimm das zweite Element heraus (Schleife)

Nach langer Zeit: fertig.

whitenoise · Anmeldungsdatum: 13.09.2005 Beiträge: 1

Hallo romancer

Auf der Suche nach einem n aus k Kombinatorik Algorithmus habe ich zufällig Deine Frage gelesen. Auch wenn Deine Anfrage schon veralted ist, hier ein effizienter Java code.

Anmerkung:
Das ArrayConverter Interface wird verwendet, um möglichst unabhängig von den eigentlichen Objekten zu sein.

Aufruf Beispiel:

int[] val = new int[] { 1, 2, 3 };
Object[] obj = Permutator.permutate(val, ArrayConverterHelper
.createIntegerArrayConverter());

// die permutaions funktionen Klasse
public class Permutator
{
/*
* hier wird das ganze array p von start bis n-1 um eine stelle nach links
* verschoben. dabei wird erstmal das startelement ge- speichert, und dann
* wieder ganz hinten in das array eingefügt!
*/
private static void push(int i_startIdx, Object[] io_objects)
{
Object temp = io_objects[i_startIdx - 1];
for (int i = i_startIdx - 1; i < io_objects.length - 1; i++)
{
io_objects[i] = io_objects[i + 1];
}
io_objects[io_objects.length - 1] = temp;
}

/**
* This method creates a flat copy of the array
*
* @param i_objs
* @return
*/
private static Object[] copy(Object[] i_objs)
{
Object[] objs = new Object[i_objs.length];
System.arraycopy(i_objs, 0, objs, 0, objs.length);
return objs;
}

/*
* dies ist die eigentliche permutations-fnkt Alle elemente werden genau so
* oft verschoben bis alle kombinationen abgearbeitet wurden! vom aktuellen
* element weg werden dann alle nachfolgenden Elemente weiterpermutiert. am
* schluss sieht die zahl dann wieder genau gleich aus, und muss daher nicht
* mehr ange- zeigt werden!
*/
private static void permu(int i_index, Object[] io_objects, ArrayList o_set)
{
for (int i = i_index; i <= io_objects.length; i++)
{
permu(i_index + 1, io_objects, o_set);
push(i_index, io_objects);
if (i != io_objects.length)
{
o_set.add(copy(io_objects));
}
}
}

private static ArrayList permutate(Object[] i_objects)
{
ArrayList set = new ArrayList();
set.add(copy(i_objects));
permu(1, copy(i_objects), set);
return set;
}

public static Object[] permutate(Object i_object, ArrayConverter i_arrayConverter)
{
Object[] array = i_arrayConverter.toArray(i_object);
ArrayList set = permutate(array);
Object[] objs = new Object[set.size()];
for (int i = 0; i < objs.length; ++i)
{
Object[] a = (Object[]) set.get(i);
objs[i] = i_arrayConverter.toObject(a);
}
return objs;
}
}

// hier das interface für die arrays
public interface ArrayConverter
{
/**
* This method transforms an array of objects into an object.
*
* @param i_objects An array of objects.
* @return An object.
*/
public Object toObject(Object[] i_objects);

/**
* This method transforms an object into an array of objects.
*
* @param i_object The object to transform.
* @return An array of objects.
*/
public Object[] toArray(Object i_object);
}

// hier die implementierung für die Integer array Objekte
public class ArrayConverterHelper
{
public static ArrayConverter createIntegerArrayConverter()
{
return new ArrayConverter()
{
/* (non-Javadoc)
* @see stuff.ArrayConverter#toObject(java.lang.Object[])
*/
public Object toObject(Object[] i_objects)
{
int[] val = new int[i_objects.length];
for(int i = 0; i < val.length; ++i)
{
val[i] = ((Integer)i_objects[i]).intValue();
}
return val;
}

/* (non-Javadoc)
* @see stuff.ArrayConverter#toArray(java.lang.Object)
*/
public Object[] toArray(Object i_object)
{
int[] v = (int[])i_object;
Integer[] val = new Integer[v.length];
for(int i = 0; i < val.length; ++i)
{
val[i] = new Integer(v[i]);
}
return val;
}
};
}
}

Gruss Markus