Buchstabenkombinationen

[Dr.Kolm]

Hi,

ich versuche ein Programm zu schreiben das mir aus einer unbegrenzten Zahl an eingegebenen Buchstaben alle möglichen Kombinationen erstellt. Dabei ist es mir egal ob die Sinn ergeben oder nicht.

Die Formel zum Ausrechnen wie viele Kombinationen es gibt habe ich schon (wenn sie stimmt). Nach meiner Formel muss man die Anzahl der Buchstaben mal die Anzahl der Buchstaben - 1 nehmen. Solange bis man bei 2 angekommen ist. Also bei 6 Buchstaben 6 * 5 * 4 * 3 * 2 = 720 möglich Kombinationen.

Mein Problem ist ein Algorithmus zu finden indem java alle Kombinationen erstellen kann.
Dazu habe ich das folgende Programm erstellt.

import java.io.*;

public class woerter
{
	public static void main (String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String wort, eingabe;
		char dumb;		
		
		System.out.print("Geben Sie Ihr Wort ein: ");
		wort = br.readLine();
		
		System.out.println(wort);
		char[] chr = new char[wort.length()];
		
		for(int i=0; i<wort.length(); i++)
		{
			chr[i] = wort.charAt(i);
		}
		
		FileWriter fw = new FileWriter("test.txt");
		
		for(int h=0; h<wort.length(); h++)
		{
			for(int i=0; i<wort.length()-1; i++)
			{
				dumb = chr[i];
				chr[i] = chr[i+1];
				chr[i+1] = dumb;
			
				for(int j=0; j<wort.length(); j++) fw.write(chr[j]);
				fw.write("\r\n");
			}
		}		
		fw.close();
	}
}

In dem Programm soll ein Wort eingegeben werden. Die einzelnen Buchstaben werden in einem char Array geschrieben und dann sollten eigendlich alle Kombinationen in der test.txt abgespeichert werden. Das der Algorithmus falsch sein muss war mir nach dem ausprobieren sofort klar. Er funktioniert nur bei maximal 3 Buchstaben.

Irgendwie scheine ich mich festgefahren zu haben mir fällt einfach keine Möglichkeit ein alle Kombinationen in der Textdatei abzuspeichern. Ich hoffe mir kann jemand helfen.

 

[Campino]

Irgendwie scheine ich mich festgefahren zu haben mir fällt einfach keine Möglichkeit ein alle Kombinationen in der Textdatei abzuspeichern. Ich hoffe mir kann jemand helfen.

Einen StringBuffer erstellen und mit append die grade errechnete Kombination +"\n" einfügen, dannach mit einem BufferedWriter alles in eine Datei schreiben (vorher den StringBufffer mit toString in einen string umwandeln)

Solche Kombinationen nennen sich so weit ich weiß "Anagramm"->google mit "Anagrammeditor Java" oder so was....vielleicht findet man den Algorithmus...

 

[anfänger]

Da es sich um eine Kombinatorik-Aufgabe handelt, hast du die Anzahl aller Möglichkeiten mit n! richitg berechnet.

Um einen String in ein char- array umzuwandlen würde ich lieber die von Java angebotene Methode verwenden.

char [] array = String.toCharArray();

Die Kompinationen selbst würde ich über Schleifen zusammen basteln:

public void kombinationenErmitteln(String str, String pfad)
{
  char[] charArray= str.toCharArray();
  
  try{
      FileWriter fw = new FileWriter(pfad);
      
       // Schleife für über deine Buchstaben und i-tes ist Anfang einer neuen Kompination
      for(int i = 0; i<charArray.length; i++)
      {
            StringBuffer buffer = new StringBuffer();
            buff.append(charArray[i]);    // erstes zeichen der Kompination
            for(int j = 0; j< charArray.length; j++)
            {
                 if(i!= j)// Damit nicht das erste zeichen doppelt  eingefügt wird
                {
                    fw.write(buff.toString()+"\n"); // vorherige Kombination in Datei schreiben
                    buff.append(charArray[j]);   // Nächste Kombination mit nächsten Buchstaben
                }          
            }  
     fw.close();
     }catch(IOException e){}
}

ich hoffe ich konnte dir ein wenig damit weiter helfen.

 

[bygones]

@anfaenger
damit schaffst du aber nicht wirklich alle kombinatorischen Ergebnisse....

logisch gesehen hast du zwei for schleifen, die jemals bis n gehen (n = laenge des wortes). wie bekommst du in den 2 schleifen n! ergebnisse her ?

bsp:

1234

bei dir:

1 2 3 4
2 1 3 4
3 1 2 4
4 1 2 3

 

[0xdeadbeef]

Rekursiv kein Problem...

public class Anagramm {

	public static void main(String[] args) {
		kombination("",wort);
	}
	
	static void kombination(String s, String k) {
		int z;
		
		if (k.length() == 2) {
			System.out.println(s+k.charAt(0)+k.charAt(1));
			System.out.println(s+k.charAt(1)+k.charAt(0));
		} else 
		    for (z=0; z<k.length(); z++) 
		    	kombination(s+k.charAt(z), k.substring(0,z)+k.substring(z+1,k.length()));		    				
	}
	
	final static String wort = "ABCD";

}

Wobei man natürlich noch Den Fall gleicher Elemente behandeln müßte. Es ist ja nicht nur die Gesamtanzahl der Buchstaben im Ursprungswort entscheidend, sondern auch wie oft jeder Buchstabe im Wort vorkommt.
Mit diesem verinfachten Ansatz bekommt man bei mehrfach vorkommenden gleichen Buchstaben halt entsprechend viele Ergebnisse doppelt. "AAA" würde z.B. ebenfalls 6 Ergebnisse liefern, die allerdings alle identisch sind.

 

[clemson]

um die anzahl der kombinationen zu ermitteln, welche die anzahl mehrerer gleicher buchstaben berücksichtigt, musst du die anzahl der gesamten kombinationen durch die fakultät* der anzahl der gleichen buchstaben dividieren...

*fakultät: fakultät einer zahl wird folgendermaßen berechnet (fakultät wird als ! angegeben):

n! = n * (n-1) * (n-2) ... * 1

so, wie du es berechnet hast...

bsp.:

gegebenes wort:

haus (n=4)

4! = 4*3*2*1 = 24 mögliche Kombinationen

hallo (n=5), aber mit 2 gleichen buchstaben

4!/2! = Anzahl der Kombinationen (Anzahl der gleichen Buchstaben wurde berücksichtigt)

allgemeines (n=11); mehrere buchstaben "l"=2, "e"=3

11! / (2! * 3!) --> Anzahl der möglichen Kombinationen (Anzahl der gleichen Buchstaben berücksichtigt)

 

[0xdeadbeef]

So, hatt gerade noch ewas Zeit, also noch 'n Version, die mehrfach vorkommende Buchstaben berücksichtigt.

import java.util.ArrayList;

public class Anagramm {

	public static void main(String[] args) {
		combination("",word);
	}
	
	static void combination(String s, String k) {
		int z;
		
		if (k.length() == 2) {
			System.out.println(s+k.charAt(0)+k.charAt(1));
			if (k.charAt(0) != k.charAt(1)) // only one combination ??
				System.out.println(s+k.charAt(1)+k.charAt(0));
		} else {
			ArrayList al = new ArrayList();
		    for (z=0; z<k.length(); z++) {
		    	String leading = s+k.charAt(z);
		    	if (!al.contains(leading)) {
		    		al.add(leading);
		    		combination(s+k.charAt(z), k.substring(0,z)+k.substring(z+1,k.length()));
		    	}
		    }
		}
	}
	
	final static String word = "OTTO";

}

Für große Stringlängen wäre ein Hash wohl performanter als eine ArrayList, aber dann wird's eh unhandlich...

Viel Spaß damit...

 

[MPW]

Mal 'ne andere Idee...
habe soetwas noch nie geamcht und denke gerade auch das erste Mal darüber nach..

Könnte man nicht die Buchstaben in Zahlen verwandeln, dann hochzählen und Rückverwandeln?
Dazu müsste man eine Klasse schreiben, die mit einem n-er System statt dem uns umgänglichen 10er System rechnen kann.
Da der Computer ja auch in echt nur im dual(2er)-System rechnet, müsste das möglich sein...

Um's noch mal zu verdeutlichen:

ABCD //das wurde eingegeben

A=0
B=1
C=2
D=3

0000 = AAAA
0001 = AAAB
usw...
0003 = AAAD
dann kommt
0010 = AABA

oder willst du jeden Buchstaben den n mal vorkommt auch nur n mal verwendent?

 

[0xdeadbeef]

Diese Idee hatte ich interessanterweise auch kurz. Das hat aber ein wesentliches Problem: nicht nur, daß mehrfach vorkommende Zeichen nicht berücksichtigt werden, viel schlimmer: auch einfach vorkommenden Zeichen werden einfach, zweifach usw. bis zu n-fach berücksichtigt.

Beispiel: AB transferiert in Binärsystem 01 (n=2)
Durch "Hochzählen" bekommt man:
00 - falsch
01 - ok
10 - ok
11 - falsch

Bei n=3 würden auch 000, 111, 222, sowie die Kombinationen mit 2mal 0,1,2 (011, 211 usw.) vorkommen.

Insofern halte ich den vorgeschlagenen rekursiven Ansatz nach wie vor für die bessere Lösung - zumal er funktioniert

 

[Gast]

hm..na wenn du so auch alle findest, hatte sonst den Vorschlag einer ist-diese-Variante-überhaupt-möglich-Prüfung die doppelten und falschen wieder zu kicken.

 

[Dr.Kolm]

Danke für eure Zahlreichen Antworten.

Rekursiv kein Problem ... für mich war es eins. Ich habe auch erstmal eine Zeit gebraucht um den Code überhaupt zu verstehen. Dann habe ich mich gleich daran gesetzt ein richtiges Programm daraus zu machen. Hier ist es

import java.io.*;
import java.awt.*;
import java.awt.event.*;

public class Anagramm extends Frame implements ActionListener, WindowListener
{  
	TextField TF1 = new TextField();
	Label Lstatus1 = new Label();
	Label Lstatus2 = new Label();
	
	static String wort;
	static int anzahl_kombi=1, anzahl_verarb, prozent;
	static FileWriter fw;
	
	public void init()
	{
		setTitle("Anagramm");
		setBackground(Color.lightGray);
		setLayout(null);
		addWindowListener(this);
		
		Label Lwort = new Label("Wort: ");
		Lwort.setBounds(4,40,40,23);
		add(Lwort);
		
		TF1.setBounds(40,40,140,23);
		add(TF1);
		
		Button Bberechnen = new Button("Berechnen");
		Bberechnen.setBounds(190,40,100,23);
		Bberechnen.addActionListener(this);
		add(Bberechnen);
		
		Lstatus1.setBounds(4,80,200,23);
		add(Lstatus1);
		
		Lstatus2.setBounds(220,80,80,23);
		add(Lstatus2);
				
		setSize(300,120);
		setVisible(true);
	}
    
	public void kombination(String s, String k)
	{ 
		int z; 
       
		if (k.length() == 2)
		{
			try
			{
				fw.write(s+k.charAt(0)+k.charAt(1)+"\r\n");
				fw.write(s+k.charAt(1)+k.charAt(0)+"\r\n");
			}
			catch(IOException ioe)
			{
				new HinweisDialog(this, "Fehler", "Fehler beim Schreiben in der Datei Kombinationen.txt");
				System.exit(0);
			}
         
			anzahl_verarb += 2;
			prozent = anzahl_verarb * 100 / anzahl_kombi;
			Lstatus1.setText(anzahl_verarb+"/"+anzahl_kombi);
			Lstatus2.setText(prozent+" %");
		}
		else 
		{
			for (z=0; z<k.length(); z++) 
				kombination(s+k.charAt(z), k.substring(0,z)+k.substring(z+1,k.length()));
		}
	}    
	
	public static void main(String[] args)
	{
		Anagramm ag = new Anagramm();
		
		ag.init();
	} 
	
	public void actionPerformed (ActionEvent e) 
	{
		wort = TF1.getText();
		
		anzahl_verarb = 0;
		anzahl_kombi = 1;
		for(int i=wort.length(); i>0; i--)
			anzahl_kombi *= i;
		
		try
		{
			fw = new FileWriter("kombinationen.txt");
		}
		catch (IOException ioe) 
		{ 
			new HinweisDialog(this, "Fehler", "Datei kombinationen.txt kann nicht erstellt werden");
			System.exit(0);
		}
		kombination("",wort);
		try
		{
			fw.close();
		}
		catch(IOException ioe) { }
		
		try 
		{ 
			Runtime.getRuntime().exec("cmd /c kombinationen.txt");
		}
		catch (IOException ioe) { }
	}
	public void windowClosing (WindowEvent e)
	{
		System.exit(0);
	}
	public void windowClosed (WindowEvent e) { }
	public void windowOpened (WindowEvent e) { }
	public void windowIconified (WindowEvent e) { }
	public void windowDeiconified (WindowEvent e) { }
	public void windowActivated (WindowEvent e) { }
	public void windowDeactivated (WindowEvent e) { }
}

und noch ein Unterprogramm was ich im Programm mit einbezogen habe:

import java.awt.*;
import java.awt.event.*;

public class HinweisDialog extends Dialog implements ActionListener
{
	public HinweisDialog(Frame owner, String title, String msg)
	{
		super(owner, title, true);
		//Fenster
		setBackground(Color.lightGray);
		setLayout(new BorderLayout());
		setResizable(false);
		
		//Message
		add(new Label(msg), BorderLayout.CENTER);
		//Buttons
		Panel panel = new Panel();
		panel.setLayout(new FlowLayout(FlowLayout.CENTER));
		Button b1 = new Button("OK");
		b1.addActionListener(this);
		b1.addKeyListener(new MyKeyListener());

		panel.add(b1);
		add(panel, BorderLayout.SOUTH);
		pack();
		
		Dimension d = Toolkit.getDefaultToolkit().getScreenSize();
		setLocation( (d.getSize().width - getSize().width) / 2, (d.getSize().height - getSize().height) / 2 );
		
		setVisible(true);
		
  	}
  	
	class MyKeyListener extends KeyAdapter
	{
		public void keyPressed(KeyEvent event)
		{
			if (event.getKeyCode() == KeyEvent.VK_ENTER) dispose();
		}
	}

	public void actionPerformed(ActionEvent event)
	{
		dispose();
	}
}

So das ist es. Ist sicherlich nicht besonders professionell geschrieben aber es funktioniert wie ich das wollte. Nochmal besten dank an alle.

 

[0xdeadbeef]

Wobei mir nicht 100% einsichtig ist, warum Du die erste Version verwendet hast, die mehrfach vorkommende Zeichen nicht berücksichtigt.