Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Mein Problem ist folgendes:
Ich habe n Verschiedene Elemente und eine zahl k.
Ich will nun alle Permutationen dieser n Elemente der Länge k haben.
Ich hab nun schon einige Algorithmen dazu im Internet gefunden und auch ihre implemenationen in Java, aber irgendwie funktionierten sie nur soweit, dass man irgendwie die die Objekte concat konnte...z.bString....
aber ich will nun am besten eine LinkedList<int[]> wo nun alle drin sind und dazu bekomm ich keine rekursion hin.
Ich hoffe jemand kann mir n tip geben oder n Rekursions ansatz
Wenn man eine Weile im Web sucht, findet man bestimmt Algorithmen, die das "auf einen Schlag" erledigen können. Vielleicht kannst du auch ein Beispiel für einen Algorithmus angeben, der "prinzipiell" macht, was du willst, und dann genau sagen, warum du den nicht auf dein Problem übertragen konntest.
Bis dahin schreibe ich mal spontane Gedanken :wink:
Ich würde das aufteilen in zwei Aufgaben:
1. Alle k-Elementigen Teilmengen der gegebenen Menge bestimmen
2. Für jede Teilmenge alle Permutationen bestimmen
Für das erste könnte man, bildlich gesprochen, die n Elemente nebeneinander schreiben, und die k Elemente markieren, die man gerade "ausgewählt" hat.
Man macht also Kreuzchen unter die ersten k Elemente.
Dann schiebt man das letzte Kreuzchen Schrittweise nach rechts, bis man am Ende ist.
Dann schiebt man das VORletzte Kreuzchen einen Schritt nach rechts, und setzt das letzte rechts daneben.
Dann schiebt man das letzte Kreuzchen Schrittweise nach rechts, bis man am Ende ist.
Dann schiebt man das VORletzte Kreuzchen einen Schritt nach rechts, und setzt das letzte rechts daneben.
...
Dann schiebt man das VOR-VORletzte Kreuzchen einen Schritt nach rechts, und setzt das VOR-letzte rechts daneben, und das letzte rechts daneben.
Dann schiebt man das letzte Kreuzchen Schrittweise nach rechts, bis man am Ende ist.
Dann schiebt man das VORletzte Kreuzchen einen Schritt nach rechts, und setzt das letzte rechts daneben.
...
Beispiel: 3 aus 6:
Code:
0 1 2 3 4 5
X X X
X X X
X X X
X X X
X X X
X X X
X X X
X X X
X X X
...
X X X
// 'selected' enthält die "Kreuzchen" (am Anfang sind die ersten k kreuzchen gesetzt), x ist am anfang k
boolean nextSubset(boolean selected[], int k, int x)
{
if (x==-1)
{
return false;
}
else
{
int toShift = findeDieStelleAnDerDas_x_teKreuzchenGesetztIst();
if (toShift == selected.length-1)
{
nextSubset(selected, k, x-1);
setzeDas_x_teKreuzchenRechtsNebenDas_x-1_te();
}
else
{
schiebeDasKreuzchenBei_toShift_um1nachRechts();
}
}
return true;
}
Solange 'true' zurückgeliefert wurde, konnte noch eine neue Teilmenge gefunden werden. Ist aber wirklich nur ins blaue getippt (hab hier gerade kein JDK, kann es nicht testen)
WICHTIG: Vermutlich gibt es "elegantere" Ansätze, die beide Teilaufgaben "auf einmal" erledigen. (Man könnte nämlich auch 'int's statt 'booleans' verwenden, und dann irgendwie mit einer abgewandelten Version des Algorithmus aus Wikipedia direkt die ausgewählten Elemente permutieren). Aber als "Meta-Divide-And-Conquer-Ansatz" finde ich so eine Aufteilung in Teilprobleme ganz hilfreich - solange sie die Anforderungen erfüllt, und nicht zeitaufwändiger ist, als andere Ansätze.
Danke, ich hab bis jetzt immer nur hinbekommen, wenn k==n ist also ich nur durchnummeriere...
cih werd ma das hier durchkauen und schaun ob ichs hinbekomm.
Zur Not hatte ich vor mit eine Art n-k Baum zu basteln und dann einfach die Wege auszulesen...aber als eigene Datenstruktur, weil ich einfach die übertrag leistung in ne Reksursive Funktion hinbekommen hab ^^
public boolean nextSubset(boolean[] selected, int k, int x){
if(x==-1){
return false;
}else{
int toShift=positionofXthX(selected,x);
if(toShift==selected.length-1){
nextSubset(selected,k,x-1);
shiftX(x);
}else{
selected[toShift]=false;
selected[toShift+1]=true;
}
}
return true;
}
public void shiftX(int x){
int tmp=x;
for(int i=0;i<selected.length;i++){
if(selected[i]){
if(tmp-1==0){
selected[i+1]=true;
for(int k=i+2;k<selected.length;k++){
if(selected[k]){
selected[k]=false;
break;
}
}
}else{
tmp--;
}
}
}
}
public int positionofXthX(boolean[] selected, int x){
int tmp=x;
for(int i=0;i<selected.length;i++){
if(selected[i]){
if(tmp==1){
return i;
}else{
tmp-=1;
}
}
}
return 0;
}
Hier mal meine Umsätzung des Pseudocodes...aber klappt irgendwie noch nicht, sobald halt das True hinten ankommt will er nochmal schieben...ich versuch das mal mit dem Baum -.-
Das Hier Sollte mir doch nun eigentlich das gewünschte Liefern(Achtung n die länge Permutationen und n nun die Anzahl der Objekte)
nun brauche ich ja nur noch die LinkedList zerlegen in Mengen ||=n oda?
Code:
public class Tree {
private class TreeNode{
LinkedList<TreeNode> nodes=new LinkedList();
int key;
public TreeNode(int keys,int n,int key){
this.key=key;
if(n>0){
for(int i=0;i<keys;i++){
nodes.add(new TreeNode(keys,n-1,i));
}
}
}
public LinkedList<Integer> getKeys(){
LinkedList<Integer> muh= new LinkedList();
muh.add(key);
for(int i=0;i<nodes.size();i++){
LinkedList<Integer> temp=nodes.get(i).getKeys();
while(!temp.isEmpty()){
muh.add(temp.poll());
}
}
return muh;
}
}
private LinkedList<TreeNode> anker=new LinkedList();
public Tree(int keys, int n){
for(int i=0;i<keys;i++){
anker.add(new TreeNode(keys,n-1,i));
}
}
public LinkedList<Integer> getKeys(){
LinkedList<Integer> muh= new LinkedList();
for(int i=0;i<anker.size();i++){
LinkedList<Integer> temp=anker.get(i).getKeys();
while(!temp.isEmpty()){
muh.add(temp.poll());
}
}
return muh;
}
}
Das Problem hab ich gestern noch erkannt aber wieder kein Plan wie ich es Löse ^^...die blätter lese ich nähmlich nicht so aus wie ich es tuen sollte, da ich jeden Zwei nur einmal auslese, dabei sollte ich ja jeden Pfad auslesen also die Verzweigungen mehrmals
Hm. Eine Permutation der Ziffern ist das aber nicht. Du müßtest da ja jetzt noch die wegwerfen, die eine Ziffer mehrmals enthalten. Das, was du im Moment machst, ist ziemlich trivial: Du zählst :roll:
Code:
public class Permnator2
{
static int k = 6;
static int n = 4;
public static void main(String[] args)
{
for (int i=0; i<1296; i++)
{
System.out.println(pad(Integer.toString(i, k)));
}
}
private static String pad(String s) // Von vorne mit '0'en auffüllen
{
while (s.length() < n) s="0"+s;
return s;
}
}
Na also dann - (das ist jetzt aber schon was GANZ anderes - mein Kreuzchen-Gewurschtel ist damit überflüssig, weil das NUR dem Zweck diente, zu verhindern, dass man alle k^n Kombinationen aufstellen muss - das können nämlich (im Vergleich zu denen, in denen jede Ziffer nur einmal vorkommt) verdammt viele sein)
Ich habe deine Lösung jetzt nicht nachvollzogen, aber vielleicht ist sie schon effizient. Kann gut sein. Letztendlich macht man damit aber - wie gesagt - nichts anderes als zu zählen. Schau vielleicht auch mal in http://www.java-forum.org/de/viewtopic.php?p=293731&highlight=
... das könntest du bestimmt leicht anpassen. Wenn nicht, sag einfach bescheid.
