Array-Elemente

[Iron Monkey]

Hi an alle!

Aus 3 verschiedenen Elementen im Array gibt es 7 verschiedene Wörter!

Als Beispiel:

array[0] = "A"
array[1] = "B"
array[2] = "C"

In der Ausgabe soll es so sein:

"A"
"B"
"C"
"AB"
"AC"
"BC"
"ABC"

Wie kann ich das am besten per Schleife ausgeben?

ACHTUNG: Die Funktion soll auch andere Möglichkeiten geben können, z.B. für 5 verschiedene Array-Elemente sowie:

array[0] = "A"
array[1] = "B"
array[2] = "C"
array[3] = "D"
array[4] = "E"

Je mehr Array-Elemente kommen, desto mehr verschiedene Wörter gibt es!

Gruß
Iron Monkey

 

[SlaterB]

http://www.java-forum.org/java-basics-anfaenger-themen/76849-kombinatorik-algorithmus-gesucht.html

 

[Iron Monkey]

Hi SlaterB!

Super, besten Dank!

Ich wusste gar nicht, dass dieses Algorithmus "Kombinatorik" heisst! Das ist genau das, was ich brauche! 🙂

Gruß
Iron Monkey

 

[SlaterB]

weder geht es um einen speziellen Algorithmus (in dem Thread), noch ist Kombinatorik ein Algorithmus-Name,
sondern eher ein Teilbereich der Mathematik, so wie Analysis, falls dir das was sagt

 

[Iron Monkey]

Ja, da hast du völlig recht! Habe den Name "Kombinatorik" in Wikipedia ( hier ) nachgeschlagen!

Habe schon eine Klasse entwickelt, falls Dich das auch interessiert! 😉

import java.util.*;

//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;
	}
	
	public static void main(String[] args)
	{
		int[] val = new int[] { 1, 2, 3 };
		Object[] obj = Permutator.permutate( val, ArrayConverterHelper.createIntegerArrayConverter() );
	}
}

// hier das interface für die arrays
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
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;
			}
		};
	}
}

Gruß
Iron Monkey

 

[SchonWiederFred]

Wie kann ich das am besten per Schleife ausgeben?

Es ist deutlich flexibler, zu diesem Zweck eine Klasse Permutation zu schreiben, die Iterable<String> implementiert.

Dann müssen die ganzen Kombinationen nicht erst in einer Collection gespeichert werden (wodurch der Arbeitsspeicher schnell zur Neige gehen kann), sondern können sozusagen on-the-fly verarbeitet werden.

Trotzdem hat man noch die Flexibilität mit den erzeugten Strings zu tun, was man möchte (auf der Konsole ausgeben, in eine Collection packen, Filtern etc.)

So würde ich es machen:

import java.util.Iterator;

public class Permutation implements Iterable<String>
{
	private final String wort;

	public Permutation(String wort)
	{
		if (wort == null) throw new NullPointerException();
		if (wort.length() >= 32) throw new IllegalArgumentException();
		this.wort = wort;
	}

	public Iterator<String> iterator()
	{
		return new Iterator<String>()
		{
			private final int laenge = wort.length();
			private final StringBuilder builder = new StringBuilder(laenge);
			private int nummer = 1;
			private final int anzahl = 1 << laenge;

			public boolean hasNext()
			{
				return nummer < anzahl;
			}

			public String next()
			{
				if (!hasNext()) throw new IllegalStateException();
				for (int i = 0; i < laenge; ++i)
				{
					if (((nummer >>> i) & 1) != 0)
					{
						builder.append(wort.charAt(i));
					}
				}
				String result = builder.toString();
				builder.setLength(0);
				++nummer;
				return result;
			}

			public void remove()
			{
				throw new UnsupportedOperationException();
			}
		};
	}
}

public class Main
{
	public static void main(String[] args)
	{
		for (String p : new Permutation("ABCDE"))
		{
			System.out.println(p);
		}
	}
}

 

[SchonWiederFred]

Und wer einen Blick über den Java-Tellerrand wagt, findet deutlich kompaktere Lösungen:

permute = foldr step [[]]
    where step x rest = map (x:) rest ++ rest

 

[Iron Monkey]

Hi SchonWiederFred!

Respekt! Es ist wirklich noch flexibler und ich habe deinen Code ein wenig geändert, so dass man nicht nur die Buchstaben vertauscht, sondern auch die Wörter! Siehe unten:

Vielen Dank für den Supertipp 🙂

import java.util.*;

public class Permutation implements Iterable<String>
{
	private final String[] wort;

	public Permutation(String[] wort)
	{
		if (wort == null)
			throw new NullPointerException();

		if (wort.length >= 32)
			throw new IllegalArgumentException();

		this.wort = wort;
	}

	public Iterator<String> iterator()
	{
		return new Iterator<String>()
		{
			private final int laenge = wort.length;
			private final StringBuilder builder = new StringBuilder(laenge);
			private int nummer = 1;
			private final int anzahl = 1 << laenge;

			public boolean hasNext()
			{
				return nummer < anzahl;
			}

			public String next()
			{
				if (!hasNext())
					throw new IllegalStateException();
				
				for (int i = 0; i < laenge; ++i)
					if (((nummer >>> i) & 1) != 0)
						builder.append(wort[i] + " ");

				String result = builder.toString().trim();
				builder.setLength(0);
				++nummer;

				return result;
			}

			public void remove()
			{
				throw new UnsupportedOperationException();
			}
		};
	}

	public static void main(String[] args)
	{
//		String[] wort = { "A", "B", "C", "D", "E" };
		String[] wort = { "Max", "Mustermann", "programmiert", "mit", "Java" };
		Permutation p = new Permutation( wort );
		Iterator<String> it = p.iterator();

		int row = 0;
		while( it.hasNext() )
		{
			System.out.println( "[ " + (row+1) + " ] = " + (String) it.next() );
			row++;
		}
		System.out.println( "" );
		System.out.println( wort.length + " Wörter = " + ( (int) Math.pow( 2, wort.length ) - 1 ) + " verschiedene Möglichkeiten!" );
	}
}

Gruß
Iron Monkey

 

[SchonWiederFred]

Streng genommen handelt es sich hierbei übrigens nicht um Permutationen, sondern um die Elemente der Potenzmenge 🙂

Wenn Du Buchstaben und Wörter verarbeiten willst, kann man ja auch gleich beliebige Objekte verarbeiten:

import java.util.Iterator;

public class Potenzmenge implements Iterable<String>
{
	private final Object[] menge;
	private final String trenner;
	
	public Potenzmenge(Object... menge)
	{
		if (menge == null) throw new NullPointerException();
		if (menge.length >= 32) throw new IllegalArgumentException();

		this.menge = menge.clone();
		trenner = " ";
	}
	
	public Potenzmenge(String wort)
	{
		if (wort == null) throw new NullPointerException();
		int laenge = wort.length();
		if (laenge >= 32) throw new IllegalArgumentException();

		menge = new Object[laenge];
		for (int i = 0; i < laenge; ++i)
			menge[i] = wort.charAt(i);
		trenner = "";
	}

	public Iterator<String> iterator()
	{
		return new Iterator<String>()
		{
			private final int laenge = menge.length;
			private final StringBuilder builder = new StringBuilder();
			private int nummer = 1;
			private final int anzahl = 1 << laenge;
			
			public boolean hasNext()
			{
				return nummer < anzahl;
			}

			public String next()
			{
				if (!hasNext()) throw new IllegalStateException();
				String trenner = "";
				for (int i = 0; i < laenge; ++i)
				{
					if (((nummer >>> i) & 1) != 0)
					{
						builder.append(trenner);
						builder.append(menge[i]);
						trenner = Potenzmenge.this.trenner;
					}
				}
				String result = builder.toString();
				builder.setLength(0);
				++nummer;
				return result;
			}

			public void remove()
			{
				throw new UnsupportedOperationException();
			}
		};
	}
	
	public static void main(String[] args)
	{
		for (String p : new Potenzmenge("ABCDE"))
		{
			System.out.println(p);
		}
		for (String p : new Potenzmenge("Max", "Mustermann", "programmiert", "mit", "Java"))
		{
			System.out.println(p);
		}
	}
}

 

[Marco13]

Da hatte ich auch mal was gebastelt http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html aber ist ja inzwischen erledigt.