Permutationen

[lisali]

Hallo,

wenn ich folgende Aufgabe habe: "Given the three letters "CAT" list all possible permutations."

Dann heißt es doch erstmal, weil es 3 Buchstaben sind, dass es 3! (Fakultät) = 6 ist. Also 6 Ergebnisse.

Die dürften dann aber nicht doppelt vorkommen, oder?

Das wäre doch dann CAT, CTA, ACT, ATC, TCA, TAC ... oder?

Ich habe nämlich eine Mitschrift von jemanden, der CAT, CTA, ACT, ATC, CTA, CAT hat... aber da kommt ja einiges doppelt vor. Oder ist es nicht erlaubt, dass da T am Anfang steht oder was gibt's da für Regeln?

 

[FrankBooth]

Hallo,

Du hast es schon richtig verstanden.
Alle Permutationen bedeutet, alle Möglichkeiten ein mal. Keine Doppelten und das T darf natürlich am Anfang stehen.

Gruß

Edit: "Hallo" und "Gruß" eingefügt

 

[lisali]

Dankeschön.

Jetzt habe ich eine zusätzliche Aufgabe, dazu und die Mitschrift im Anhang als Lösung. Nur kann ich das alles nicht ganz nachvollziehen. Was genau wurde da gemacht? Und wieso steht da manches leer, also in 2 Anführungszeichen?

 

[rd4eva]

Wie schon drüber steht wurden ganz einfach alles subsets ermittelt. Man könnte auch sagen das das Power set ermittelt wurde da dies ja ein set aus allen subsets ist.

Hier das Beispiel von Wikipedia:

If S is the set {x, y, z}, then the subsets of S are:

    * {} (also denoted \emptyset, the empty set)
    * {x}
    * {y}
    * {z}
    * {x, y}
    * {x, z}
    * {y, z}
    * {x, y, z}

Und hier noch eins:

Array = [Hund, Katze, Maus]

Alle mögl. subsets
[,,]
[,,Maus]
[,Katze,]
[,Katze,Maus]
[Hund,,]
[Hund,,Maus]
[Hund,Katze,]
[Hund,Katze,Maus]

 

[Thomas Darimont]

Hallo,

schau mal hier:

package de.tutorials.training;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class PermutationExample {
    public static void main(String[] args) {
     Object[] o = {'C','A','T'};
       
      for(Object[] permutation : new Permutations().computePermutations(o)){
        System.out.println(Arrays.toString(permutation));
      }
    }
 
    static class Permutations{
      
      List<Object[]> permutations;
      
      public List<Object[]> computePermutations(Object[] values){
       this.permutations = new ArrayList<Object[]>();
       permut(values,values.length-1);
       return permutations;
      }
      
      void permut(Object[] values, int endIndex) {
        if (endIndex==0){
          this.permutations.add(values.clone());
        }else{
          permut(values, endIndex-1);
          for (int i=0; i<=endIndex-1; i++){
            swap(values, i, endIndex);
            permut(values, endIndex-1);
            swap(values, i, endIndex);
          }
        }
      }
      
      static void swap(Object[] values, int i, int j) {
        Object temp = values[i];
        values[i] = values[j];
        values[j] = temp;
      }
    }
}

Ausgabe:

[C, A, T]
[A, C, T]
[T, A, C]
[A, T, C]
[C, T, A]
[T, C, A]

Gruß Tom

 

[rd4eva]

@Thomas

Das sind jetzt aber wieder alle möglichen Permutationen und nicht subsets.
Ich erwähne das nur damit sie jetzt nicht durcheinander kommt.

 

[lisali]

Danke dir rd4eva, das leuchtet mir ein. Jedoch unterscheidet sich das doch von der Mitschrift... was mich momentan noch verwirrt...

 

[rd4eva]

Auch wenn ich bei der Mitschrift auch nicht ganz durchblicke sieht zumindest alles was rechts unten steht wie die einzelnen subsets aus.

Subsets von CAT =>
[C,A,T]
[C,A,""]
[C,"",T]
["",A,T]
[C,"",""]
["",A,""]
["","",T]
["","",""]

 

[lisali]

Okay, danke dir.

Vielleicht habe ich eins vergessen zu erwähnen warum mich das so verwirrte. Also, erstmal weil ich in der Vorlesung nicht dabei war und die Lösung vom Dozenten selbst von der Tafel abgeschrieben wurde.
Und zweitens ist dies die exakte Aufgabenstelluing dazu:

Write pseudo-code that will list all possible subsets of a give string.

Dann setze ich wohl immer nur eine pseudo-Methode wie z.B.

recursiveSub("C","A","T");

davor, oder?

 

[Thomas Darimont]

Hallo,

@Thomas

Das sind jetzt aber wieder alle möglichen Permutationen und nicht subsets.
Ich erwähne das nur damit sie jetzt nicht durcheinander kommt.

Huch, das hab ich leider nicht gesehen...

Schau mal hier:

package de.tutorials;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class SubSets {

	public static void main(String[] args) {
		Set<String> set = new HashSet<String>();
		set.add("C");
		set.add("A");
		set.add("T");

		Set<Set<String>> powerSet = powerSet(set);
		System.out.println(powerSet);
	}

	private static <T> Set<Set<T>> powerSet(Set<T> set) {
		Set<Set<T>> powerSet = new LinkedHashSet<Set<T>>();
		List<T> items = new ArrayList<T>(set);
		
		int numberOfItems = items.size();
		int numberOfSets = (int) Math.pow(2, set.size());
		
		for (int i = 0; i < numberOfSets; i++) {
			Set<T> subSet = new HashSet<T>();
			for (int j = 0; j < numberOfItems; j++) {
				boolean bitIsSet = ((i >> j) & 1) == 1;
				if (bitIsSet) {
					T item = items.get(j);
					subSet.add(item);
				}
			}
			powerSet.add(subSet);
		}
		
		return powerSet;
	}
}

Ausgabe:

[[], [T], [A], [T, A], [ C], [T, C], [A, C], [T, A, C]]

Gruß Tom