Anordnungsmöglichkeit

[john]

Hallo!

Ich versuche nachvollzuziehen wie ich dem Computer beibringen soll, dass
er z.B alle möglichen Kombination von einer bestimmten Vorgabe einer Buchstebkette oder Zahlenkette anordnet.
Bsp:
Für ABCD gibt es z.B 4! = 24 versch. Möglichkeiten der Anordnung.

Wenn ich nun dafür ein Algrithmus entwickeln müsste hätte ich Probleme damit
Hat jemand vielleicht eine Idee wie man dieses Problem lösen könnte. Klar ich packe die Bucstaben in ein Array vertausche jeweils pro
Durchlauf innerhalb einer for-Schleife die Plätze. Bloss nach welcher Bedingung
bzw welchem Kriterium????

Grüße

[butterkeks]

Was du suchst nennt sich afaik "Permutation".

Sind Rekursionen ebenfalls erlaubt?
In diesem Fall fiele mir auf die Schnelle nämlich folgendes ein:

m ist die Anzahl der Elemente (also 4 in diesem Fall).

Die Funktion wird zunächst mit n = m aufgerufen.

Jeder Durchlauf fügt das nächste freie Element, das er findet, an Position m-n eines (statischen?) arrays.
Als nächstes wird das soeben gefundene Element als vergeben markiert, dieselbe Funktion mit n-1 aufgerufen und die Markierung nach dem Aufruf gelöscht.

Sollte n 0 sein, so steht in deinem statischen Array eine Variante der Permutation und du kannst damit arbeiten.
Wenn du fertig bist, gib 0 zurück.

Hier mal ein Beispiel in C:

char e[] = "ABCD";

/* ... */

int go(int n, int m, char *e) {

/* ready[i] == 1 -> bereits verwendet */
static int ready[m];

static char result[m];
int i;

if(n == m) /* initialisieren; C-Spezifisch! */
for(i = 0; i < m; i++) ready[i] = 0;

if(n > 0) {
for(i = 0; i < m; i++)
if(!ready[i]) {
result[m - n] = e[i];

ready[i] = 1;
go(n-1, m, e);
ready[i] = 0;
}
} else
/* in result steht nun eine Kombination.
mach damit, was du willst */
}

return 0;
}

/* ... */

/* Aufruf: */
go(n, sizeof(e), e);


Wie gesagt hab ich mir das aus den Fingern gezogen; Es gibt sicher effizientere Methoden, die man vlt. sogar in einer einzelnen for Schleife unterbringen kann.

[john]

Hi!
Danke für deine freundlichen Bemühungen. Kannst du mir vielleicht bitte erklären wie man es schafft eine Reihe von Zeichen so zu vertauschen dass alle möglichen Kombinationen dargestellt werden. Ich verstehe die Logik dahinter nicht. Wodurch wird das "richtige" Vertsuchen bzw. "Anordnen " realisiert.
Was ist der Trick an der Sache (Durch das Vertauschen der Elemente des
Arrays klar). Welche Programmlogik verbirgt sich dahinter???

[butterkeks]

Nun, wie soll ich es erklären...

Ich habe ein Glas mit Kugeln, aus dem ich mir zunächst 4 raus nehme {A, B, C, D}; Ich notiere diese Kombination.

Nun lege ich D zurück und habe nun {A, B, C} sowie {D} im Glas.

Ich schaue, ob ich mir etwas anderes aus dem Glas nehmen kann, um eine neue Kombination zu erhalten.

In diesem Falle nicht, also lege ich {C} auch zurück; In der Hand habe ich nun {A, B} und im Glas {C, D}.

Da ich für {A, B, C} schon alle Möglichkeiten probiert habe, versuche ich D und C zu nehmen; Das ist eine neue Kombination, also notiere ich das.

somit habe ich für {A, B} alle Möglichkeiten ausprobiert und lege B zurück.
zur Auswahl stehe nun noch C und D, da A bereits in der Hand ist und für {A, B} keine Möglichkeiten mehr da sind (wie zuvor erwähnt).

Ich nehme also C und verfahre ähnlich wie anfangs.

Ich glaube, du suchst lieber etwas besser verständliches und effizienteres als das obige aus dem Internet raus; Stichwort "Permutation".

Vlt. kommt auch hier im Forum jemand vorbei, der das gern näher erklären will

//edit:
Denk dran, dass es sich um eine Rekursion handelt; Du sagtest im ersten Post, du willst das in einer for SChleife lösen.

Wenn du das einfach so gesagt hast, dann kannste meine Idee verwenden.
War das aber eine Hausaufgabe o.ä., dann würdeste mit der Rekusrion warshc. nicht durch kommen

[john]

Hallo!
Sorry ich muss noch mal etwas nachfragen:
Ich verstehe beispilesweise überhaupt nicht was die Methode getNext () der Klasse "PermutationGenerator " macht ?
Was genau will man z.B damit erreichen?
while (a[j] > a[k])
{
k--;
}

Oder wodurch wird letztlich erreicht dass man die Elemente des Arrays
so vertauscht dass alle Kombis dargestell werden




(Java Code)
import java.math.BigInteger;

public class PermutationGenerator {

private int[] a;
private BigInteger numLeft;
private BigInteger total;

public PermutationGenerator (int n)
{
if (n < 1)
{
throw new IllegalArgumentException ("Min 1");
}
a = new int[n];
total = getFactorial (n);
reset ();
}

public void reset ()
{
for (int i = 0; i < a.length; i++)
{
a[i] = i;
}
numLeft = new BigInteger (total.toString ());
}


public BigInteger getNumLeft () {
return numLeft;
}



public BigInteger getTotal () {
return total;
}


public boolean hasMore () {
return numLeft.compareTo (BigInteger.ZERO) == 1;
}



private static BigInteger getFactorial (int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply (new BigInteger (Integer.toString (i)));
}
return fact;
}

//--------------------------------------------------------
// Generate next permutation (algorithm from Rosen p. 284)
//--------------------------------------------------------

public int[] getNext () {

if (numLeft.equals (total)) {

numLeft = numLeft.subtract (BigInteger.ONE);

return a;
}

int temp;

// Find largest index j with a[j] < a[j+1]

int j = a.length - 2;
//System.out.print ("j " + j+ "\t");
while (a[j] > a[j+1]) {

--j;

}

// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]

int k = a.length - 1;
//System.out.print ("k " + k + "\t");
while (a[j] > a[k]) {
k--;


}

// Interchange a[j] and a[k]

temp = a[k];
a[k] = a[j];
a[j] = temp;

int r = a.length - 1;
int s = j + 1;

while (r > s) {
temp = a[s];
a[s] = a[r];
a[r] = temp;
r--;
s++;
// System.out.print ("tempNeu " + temp + "\t");
//System.out.print ("a[s] " + a[s] + "\t");
//System.out.print ("a[r] " + a[r] + "\t");
}

numLeft = numLeft.subtract (BigInteger.ONE);

return a;

}

public static void main(String[] args)
{
int[] indices;
String[] elements = {"A","B","C"};
PermutationGenerator x = new PermutationGenerator (elements.length);
StringBuffer permutation;
while (x.hasMore ()) {
permutation = new StringBuffer ();
indices = x.getNext ();
for (int i = 0; i < indices.length; i++) //indices.length 3 i= 0,1,2
{

System.out.print (indices[i] + "\t");
}
for (int i = 0; i < indices.length; i++)
{
permutation.append (elements[indices[i]]);
}
System.out.println (permutation.toString ());

}

}
}

[DarkTom]

Ich verstehe beispilesweise überhaupt nicht was die Methode getNext () der Klasse "PermutationGenerator " macht ?Das wurde hier (bei Spotlight) (http://www.spotlight.de/zforen/jav/m/jav-1112956073-19514.html) schon mal versucht zu beantworten.

[john]

Aber DarkTom, findest du dass es ausreicht ??

[DarkTom]

Inwiefern ausreicht? Zum Verständnis? Ja. Als Antwort für eine Hausaufgabe (die ich hier stark vermute)? Wohl eher nicht.
Wenn es mich interessieren würde und ich Probleme mit dem Verständnis hätte, würde ich wohl versuchen, an das Original von Rosen ranzukommen. Google liefert auch direkt eine konkrete QuellenangabeThe algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284. Aber natürlich hat nicht jeder eine Unibibliothek in der Nähe. (Jemand, der das als Hausaufgabe bekommt i.a. aber schon ;))

Sollte ich einen Permutationengenerator schreiben, würde ich das vermutlich anders machen. Nur mal kurz angedacht: Man hat bei x Elementen nur n=(x-1 + x-2 + ... + 1) Möglichkeiten, zwei Elemente zu vertauschen. Dies induziert eine Hypercube-Struktur der Dimension n. Es findet sich einfach eine Strategie, auf dem Hypercube einen Hamiltonkreis zu finden.
Aber ich habe mir keine Details überlegt. Und auch keine Lust, die genannten Stichworte hier weiter zu erläutern.